傳送門

$A?DialUp$ $貪心$

首先當$b$有$a$沒有的元素的時候顯然無解，否則我們可以找到離$a_1$最近的一個$!a_1$，讓后交替著來構造$b$即可。

int n,m; int a[N],b[N];int main() { // ios::sync_with_stdio(false); // cin.tie(0);int ans=0;scanf("%d%d",&n,&m);int dx,dy,dxx,dyy; dx=dy=dxx=dyy=0;for(int i=1;i<=n;i++) scanf("%d",&a[i]),dx+=a[i]==1,dy+=a[i]==0;for(int i=1;i<=m;i++) scanf("%d",&b[i]),dxx+=b[i]==1,dyy+=b[i]==0;dx=dx>0; dy=dy>0; dxx=dxx>0; dyy=dyy>0;if(dx<dxx||dy<dyy) {puts("-1");return 0;}ans+=m;int change=0;for(int i=2;i<=m;i++) if(b[i]!=b[i-1]) change++;if(a[1]==b[1]) {int cnt=INF;for(int i=2;i<=n;i++) if(a[i]!=a[1]) {cnt=min(cnt,i-1);cnt=min(cnt,n-i+1);}if(change) {ans+=cnt,ans+=change-1;if(cnt==INF) ans=-1;} } else {int cnt=INF;for(int i=2;i<=n;i++) if(a[i]!=a[1]) {cnt=min(cnt,i-1);cnt=min(cnt,n-i+1);}ans+=cnt;ans+=change;if(change&&cnt==INF) ans=INF; }printf("%d\n",ans);return 0; }

$B?Squares$ $數學+推式子$

考慮題面中的式子就是$x^2?y=z^2$，其中$x\in [1,10^{12}]$，也就是找$x^2$減去一個$[1,10^{12}]$內的數仍是一個平方數，由于得到的平方數都$\le x^2$，所以我們不妨先看看$(x?1{)}^2$，化開就是$x^2?(2x?1)$，此時$y=2x?1$，當$x$取遍若干值的時候，也就是數列$1,3,5,...$，就是找這個數列中$\le n$的數有多少個，這個是等差數列顯然可以$O(1)$算。讓后再看$(x?2{)}^2=x^2?(4x?4)$，此時$y=4x?4$，數列就是$4,8,12,...$，依次找下去，可以發現就找以$i^2$開頭，$2i$為公差的等比數列，有多少個$\le n$的數，由于首項是平方的形式，顯然可以$\sqrt{n}$枚舉來算。

還可以將初始的式子移項，也就是$x^2?z^2=y$，由于$y\in [1,n]$，所以$x^2?z^2\le n$，換句話就是求$[0,1,4,9,...,n^2]$這個數列中，有多少對不同的數差$\le n$，將其差分之后得到$[1,3,5,...]$，也就是差分后的數列中有多少段非空區間的和$\le n$，讓后根據區間長度不同，可以分成$[1,3,5,...],[4,8,12,...],[9,15,21,...]$這些區間跟上面的分析一樣。

復雜度$O(\sqrt{n})$

LL n; cin>>n;LL ans=0;for(LL i=1;;i++) {LL a=i*i;if(a>n) break;LL d=i*2;ans+=(n-a)/d+1;ans%=mod;}cout<<ans<<endl;

$C?LIStoOriginalSequence$ $貪心+構造$

考慮為什么這個東西一定有解，我們找個例子，比如$n=5,k=2,a_1=3,a_2=5$，我們可以構造$3,2,1,5,4$，也就是在$a_i,a_i+1$之間以遞減的方式填上$[a_i+1,a_{i+1}?1]$這個區間中的數，顯然這樣一定可以構造出一個答案，下面考慮字典序最小。

我們上面實際上就是將其分成了$k$塊，每塊只能選一個，我們依舊是按照這個思想來，考慮$a_1$之后最小的數能填多少？如果$a_1$不是$1$的話，顯然我們可以將$1$放在$a_1$的后面，這個是最優的，一旦放了別的數，顯然是沒有這個優。但是我們放了$1$之后，還能放別的嗎？顯然也是不能的，因為如果放了別的顯然能將最長上升序列變長，所以我們就得到了這個題的做法，在每個數后面嘗試放第一個小于它的并且沒有被選擇的數，最后的時候直接遞減的輸出沒有選擇的數即可。

int n,k; int a[N],st[N];int main() { // ios::sync_with_stdio(false); // cin.tie(0);scanf("%d%d",&n,&k);for(int i=1;i<=k;i++) scanf("%d",&a[i]);int j=1;for(int i=1;i<k;i++) {printf("%d ",a[i]);st[a[i]]=1;while(st[j]) j++;if(j<a[i]) {st[j]=1;printf("%d ",j++);}}for(int i=n;i>=1;i--) if(!st[i]) printf("%d ",i);return 0; }

$D?UniqueSubsequence$ $樹狀數組+dp$

考慮$dp$，設$f[i]$表示前$i$個能構成答案的子序列有多少，不難發現不合法的子序列是因為出現了相同的數，比如說$2,1,1$，$2,1$這個子序列就是不合法的。所以需要將每個數分開來看，假設當前到了$i$，上一次出現$a_i$的位置是$pre$，那么我們顯然可以從$[pre,i?1]$這些位置轉移過來，也就是在這些狀態的子序列末尾加上$a_i$，這樣是合法的。對于$[1,pre?1]$這些位置的狀態顯然是不能轉移過來的，因為$f[pre]$這個位置已經包含了$[1,pre?1]$這些位置后面加$a_i$的方案數了，正如前面的例子$2,1,1$，$f[1]=1,f[2]=2$，對于$f[3]$如果我們從$f[2]$轉移會得到$[2,1,1],[1,1]$這兩個序列，如果我們再從$f[1]$轉移過來會得到$[2,1]$這個序列，這個顯然不合法，應該舍去。

經過上面的討論，我們需要實現區間求和以及單點修改的數據結構，顯然樹狀數組即可勝任。

注意某個數字第一次出現的時候需要加一，因為可能只選他一個。

int n; int a[N]; int pre[N],last[N]; LL tr[N];void add(int x,LL c) {c+=mod; c%=mod;for(int i=x;i<=n;i+=lowbit(i)) (tr[i]+=c)%=mod; }LL sum(int x) {LL ans=0;for(int i=x;i;i-=lowbit(i)) (ans+=tr[i])%=mod;return ans; }int main() { // ios::sync_with_stdio(false); // cin.tie(0);scanf("%d",&n);for(int i=1;i<=n;i++) {scanf("%d",&a[i]);pre[i]=last[a[i]];last[a[i]]=i;}LL ans=0;for(int i=1;i<=n;i++) {LL now;if(pre[i]) {now=(sum(i)-sum(pre[i]-1))%mod; now+=mod; now%=mod;add(pre[i],-(sum(pre[i])-sum(pre[i]-1)));} else now=(sum(i)+1)%mod;add(i,now);}printf("%lld\n",sum(n));return 0; }

$E?Snack$ $網絡流轉最小割+貪心+推公式$

考慮經典網絡流建圖：

我們規定$S$為源點，$T$為匯點，$X$為左部點，$Y$為右部點。

$(1)S?>X$，容量為$a_i$。

$(2)X?>Y$，對于左部的每個點與右部的每個點都連邊，設右部的某個點為$j$，容量為$b_j$。

$(3)Y?>T$，容量為$c_j$。

建圖是$n^2$的，而且也沒有什么優化的地步，由于這個圖的性質比較特殊，我們不妨轉換成最小割來求，也就是割掉邊權總和最少的邊使其不連通。

先考慮第一類邊，假設我們割掉$x$條，由于我們割那條邊與我們右邊割的代價是互相獨立的，所以我們只需要關注切掉了多少條邊，也就是可以貪心的切掉$a_i$最小的$x$條邊。

對于第二類邊和第三類邊，他們剩下了$n?x$條與$Y$相連的第二類邊以及$m$條與$T$相連的第三類邊，想要不連通只能割掉第二類和第三類其中的一類邊，也就是$min((n?i)?b_i,c_i)$。我們按照$\frac{c_i}{b_i}$排序，當$n?i$增大的時候，一定是一部分取$c_i$，一部分取$(n?i)?b_i$，用一個指針維護一下即可，或者可以偷懶寫個二分。

int n,m; LL a[N],prec[N],preb[N];struct Node {LL b,c;bool operator < (const Node &W) const {return c*W.b<W.c*b;} }node[N];int main() { // ios::sync_with_stdio(false); // cin.tie(0);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);for(int i=1;i<=m;i++) scanf("%lld%",&node[i].b);for(int i=1;i<=m;i++) scanf("%lld%",&node[i].c);sort(node+1,node+1+m);sort(a+1,a+1+n); for(int i=1;i<=m;i++) {prec[i]=prec[i-1]+node[i].c;preb[i]=preb[i-1]+node[i].b;}LL ans=inf,pre=0,suma=0;for(int i=1;i<=n;i++) suma+=a[i];for(int i=0,j=0;i<=n;i++) { pre+=a[i];int l=0,r=m,anss;while(l<=r) {int mid=(l+r)>>1;if(node[mid].c<=node[mid].b*(n-i)) anss=mid,l=mid+1;else r=mid-1;}LL now=prec[anss]+(preb[m]-preb[anss])*(n-i)+pre;ans=min(ans,now);}cout<<ans<<endl;return 0; }

$F?TreeDegreeSubsetSum$ 貌似是個性質題 待補

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的AtCoder Regular Contest 125的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。