Div1A / 2C. Make Nonzero Sum令最后每个\(a_i\)的系数为\(c_i\)(\(c_i=1/-1\)) , 发现只要满足\(c_1=1\)(下标从1开始) , 且c中没有两个-1相连,就一定能找出一种划分方式 。那我们先令所有\(c_i\)都为1,再进一步把一些1改成-1 。如果全是1时序列的和sum已经是0,那么就已经找到一个答案了 。否则我们只会把\(a_i=1/-1\)的位置的系数改成-1,当\(sum>0\)时改\(a_i=1\)的i的系数,否则改\(a_i=-1\)的i的系数 。发现每改变一个位置的系数,sum的变化量都是2,所以sum也必须是偶数,否则无解 。然后就是把尽量多的能修改系数的位置的系数改成-1,最后保留其中的\(|\frac{sum}2|\)个就可以了 。可以用贪心或一个简单的dp完成 。
时间复杂度\(O(n)\) 。
#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<n;++i)#define repn(i,n) for(int i=1;i<=n;++i)#define LL long long#define pii pair <int,int>#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){#ifdef LGSfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endif}void termin(){#ifdef LGSstd::cout<<"\n\nPROGRAM TERMINATED";#endifexit(0);}using namespace std;int t,n,a[200010],good[200010],swit[200010];pii dp[200010][2];int main(){fileio();cin>>t;rep(tn,t){cin>>n;int sum=0;rep(i,n) scanf("%d",&a[i]),sum+=a[i],good[i]=0;if(sum%2!=0){puts("-1");continue;}if(sum>0){rep(i,n) if(a[i]==1)good[i]=1;}else{sum=-sum;rep(i,n) if(a[i]==-1)good[i]=1;}sum/=2;rep(i,n+3) rep(j,2) dp[i][j]=mpr(-1,-1);dp[0][0]=mpr(0,-1);rep(i,n) rep(j,2) if(dp[i][j].fi>-1){dp[i+1][0]=max(dp[i+1][0],mpr(dp[i][j].fi,j));if(j==0&&good[i]&&i>0) dp[i+1][1]=max(dp[i+1][1],mpr(dp[i][j].fi+1,j));}if(dp[n][0].fi<sum&&dp[n][1].fi<sum) puts("-1");else{int i=n,j=(dp[n][0].fi>=sum ? 0:1);while(true){swit[i-1]=j;if(i==1) break;j=dp[i][j].se;--i;}int cnt=0;rep(i,n){cnt+=swit[i];if(cnt>sum) swit[i]=0;}vector <pii> ans;rep(i,n){int p=i;while(p+1<n&&swit[p+1]==(swit[p]^1)) ++p;ans.pb(mpr(i,p));i=p;}cout<<ans.size()<<endl;rep(i,ans.size()) printf("%d %d\n",ans[i].fi+1,ans[i].se+1);}}termin();}
时间复杂度\(O(p)\) 。
#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<n;++i)#define repn(i,n) for(int i=1;i<=n;++i)#define LL long long#define pii pair <int,int>#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){#ifdef LGSfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endif}void termin(){#ifdef LGSstd::cout<<"\n\nPROGRAM TERMINATED";#endifexit(0);}using namespace std;int n,x,a[500010];int main(){fileio();cin>>n>>x;int xx;rep(i,n){scanf("%d",&xx);++a[xx];}repn(i,x-1){if(a[i]%(i+1)>0){puts("No");termin();}a[i+1]+=a[i]/(i+1);}puts("Yes");termin();}
令序列中0的数量为x,则我们想要的序列是前x个为0 , 后n-x个为1,也就是要把初始序列中前x个位置中的1 , 以及后n-x个位置中的0都干掉 。这两种类型的数量永远是相同的 。假设前x个位置中有k个1(初始的k用一次遍历求出),则一次操作能把k减1的概率是\(\frac{k^2}{\binom n2}\),所以期望\(\frac{\binom n2}{k^2}\)次操作才能把k减1 。所以枚举所有可能的k,对这个值求和即可 。
时间复杂度\(O(nlogn)或O(n)\) 。
#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<n;++i)#define repn(i,n) for(int i=1;i<=n;++i)#define LL long long#define pii pair <int,int>#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){#ifdef LGSfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endif}void termin(){#ifdef LGSstd::cout<<"\n\nPROGRAM TERMINATED";#endifexit(0);}using namespace std;const LL MOD=998244353;LL qpow(LL x,LL a){ LL res=x,ret=1; while(a>0) {if((a&1)==1) ret=ret*res%MOD;a>>=1;res=res*res%MOD; } return ret;}LL t,n,a[200010];int main(){fileio();cin>>t;rep(tn,t){cin>>n;rep(i,n) scanf("%lld",&a[i]);LL c0=0;rep(i,n) if(a[i]==0) ++c0;LL bad=0;rep(i,c0) if(a[i]==1) ++bad;LL full=n*(n-1)/2%MOD,ans=0;for(LL i=bad;i>0;--i){LL goods=i*i%MOD,add=full*qpow(goods,MOD-2)%MOD;(ans+=add)%=MOD;}printf("%lld\n",ans);}termin();}
![Div. 1/Div. 2 Codeforces Round #829 1753 A B C D 题解](http://img.zhejianglong.com/231018/21320633J-0.png)
推荐阅读
- Rated for Div. 2 Educational Codeforces Round 137 A-F
- Codeforces 1682 D Circular Spanning Tree
- Codeforces 1684 E. MEX vs DIFF
- Rated for Div. 2 Educational Codeforces Round 138 A-E
- [题解] Codeforces Dytechlab Cup 2022 1737 A B C D E 题解
- Div. 2 Codeforces Round #822 A-F
- Div. 2 Codeforces Round #823 A-D
- [题解] Codeforces Global Round 22 1738 A B C D E F 题解
- round函数怎么用 python的round函数怎么用
- turn around英语怎么读 round英语怎么读