A.

解

分類討論。

Code

#include<bits/stdc++.h> using namespace std; const int maxn=100003; int main(){int a1,a2,k1,k2,n;cin>>a1>>a2>>k1>>k2>>n;if(k1>k2)swap(a1,a2),swap(k1,k2);int ans1=n/k1;if(ans1>a1)ans1=a1+(n-a1*k1)/k2;int tmp=n/a2,ans2;if(tmp<k2-k1)ans2=0;else{int m=n-a2*(k2-k1);tmp=(m+a1+a2-1)/(a1+a2);if(tmp<k1)ans2=0;else if(tmp==k1)ans2=(m%(a1+a2)==0?a1+a2:m%(a1+a2));else ans2=a1+a2;}cout<<ans2<<' '<<ans1;return 0; }

B.

解

考慮前綴和的正負性。

C.

解

\(^{a\;a}_{b\;b}\rightarrow ^{a\;b}_{a\;b}\)
\(^{a\;b}_{b\;a}\rightarrow ^{a\;a}_{b\;b}\rightarrow ^{a\;b}_{a\;b}\)

執(zhí)行完以上轉換后，如果還沒相等，那就不可能。

Code

#include<bits/stdc++.h> using namespace std; const int maxn=200003; int n; char s[maxn],t[maxn]; vector<int> u,v; int main(){scanf("%d%s%s",&n,s+1,t+1);for(int i=1;i<=n;i++){if(s[i]=='a'&&t[i]=='b')u.push_back(i);if(s[i]=='b'&&t[i]=='a')v.push_back(i);}if(u.size()%2+v.size()%2==1){puts("-1");return 0;}int cnt=u.size()/2+v.size()/2+u.size()%2+v.size()%2;printf("%d\n",cnt);for(int i=0;i+1<int(u.size());i+=2){printf("%d %d\n",u[i],u[i+1]);}for(int i=0;i+1<int(v.size());i+=2){printf("%d %d\n",v[i],v[i+1]);}if(u.size()%2+v.size()%2){printf("%d %d\n%d %d\n",u.back(),u.back(),u.back(),v.back());}return 0; }

D.

解

被叉掉了

Code

#include<bits/stdc++.h> using namespace std; const int maxn=200003; int n,cnt0,cnt1,sum0,sum1; char s[maxn]; int main(){scanf("%d%s",&n,s+1);for(int i=1;i<=n/2;i++){if(s[i]=='?')cnt0++;else sum0+=s[i]-48;}for(int i=n/2+1;i<=n;i++){if(s[i]=='?')cnt1++;else sum1+=s[i]-48;}if(sum0<sum1)swap(cnt0,cnt1),swap(sum0,sum1);int game=(cnt0+cnt1)/2;for(int i=1;i<=game;i++){if(cnt0){sum0+=9;cnt0--;}else{cnt1--;if(sum1+9>sum0)sum1+=9,swap(sum0,sum1),swap(cnt0,cnt1); // important}if(cnt1){sum1+=min(9,sum0-sum1);cnt1--;}else{cnt0--;}}puts(sum0==sum1?"Bicarp":"Monocarp");return 0; }

E.

解

看到20，4s，考慮狀壓。
先預處理出 \(pre[i][j]\) 表示位置1到i有多少個元素等于j，然后在用其處理出 \(sum[i][j]\) 表示序列中每個等于i的元素的pre[j]之和。
然后 \(O(2^n*n^2)\) 狀壓dp，對于已處理的集合S和不在S中的i，我們的目標是把所有等于i的元素移到未處理元素的左邊，S中元素的右邊。這樣它的貢獻就是 \(\sum sum[i][j](j≠i,j?S)\) 。
有點類似統(tǒng)計逆序對。

Code

#include<bits/stdc++.h> using namespace std; typedef long long D; const int maxn=400003,maxm=20,maxb=1<<maxm; const D INF=0x3f3f3f3f3f3f3f3fll; int n,a[maxn],pre[maxn][maxm]; D dp[maxb],sum[maxm][maxm]; int main(){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",a+i),a[i]--;for(int i=1;i<=n;i++){for(int j=0;j<maxm;j++)pre[i][j]=pre[i-1][j];pre[i][a[i]]++;}for(int i=1;i<=n;i++){for(int j=0;j<maxm;j++){sum[a[i]][j]+=pre[i][j];}}memset(dp,0x3f,sizeof(dp));dp[0]=0;for(int S=0;S<maxb;S++){for(int i=0;i<maxm;i++){if(!((S>>i)&1)){D res=0;for(int j=0;j<maxm;j++){if(i!=j&&!((S>>j)&1)){res+=sum[i][j];}}dp[S|(1<<i)]=min(dp[S|(1<<i)],dp[S]+res);}}}printf("%lld\n",dp[maxb-1]);return 0; }

轉載于:https://www.cnblogs.com/BlogOfchc1234567890/p/11559535.html

總結

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

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