Div. 1/Div. 2 Codeforces Round #829 1753 A B C D 题解 _生活百科

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();}

1B / 2D. Factorial Divisibility?发现两个\(1!\)可以合成一个\(2!\)，三个\(2!\)可以合成一个\(3!\)…… 我们从1枚举到p-1，每次尽量地把i合并到i+1，最后如果\(1!,2!\cdots (p-1)!\)还有剩余的话，仔细想想发现是不可能整除的。\(p!\)及以上如果有剩余那当然是可以整除的了。
时间复杂度\(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();}

1C / 2E. Wish I Knew How to Sort脑筋急转弯，感觉非常类似于atcoder的风格。好像有不少人会D但不会这个C
令序列中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();}

1D / 2F. The Beach我咋就fst呢了?。?