1. 首頁 > 生活百科 > >

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呢了?。?
Div. 1/Div. 2 Codeforces Round #829 1753 A B C D 題解

推薦閱讀