Educational Codeforces Round 120 (Rated for Div. 2) vp补题

C 贪心 策略

基本策略：操作1改小的，让大的数进行操作2变成小的

voidsolve(){intn,k;cin>>n>>k;vector<int>a(n+1),pre(n+1,0);intsm=0;forr(i,1,n)cin>>a[i];sort(a.begin()+1,a.end());forr(i,1,n){pre[i]=pre[i-1]+a[i];}if(pre[n]+a[1]<=k)cout<<0<<endl;else{intmn=inf;reforr(i,1,n){intaftsm=k-pre[i]+a[1];// 修改的部分最后得到的和intaim;// aim*(n-i+1)<=aftsmif(aftsm>=0)aim=aftsm/(n-i+1);// aim是a[1]要改成的数elseaim=(aftsm-n+i)/(n-i+1);// 负数向下取整mn=min(mn,max(a[1]-aim,0ll)+n-i);}cout<<mn<<endl;}}

D 组合数学 容斥原理

constintN=1e5,M=1e5;constdoublePI=acos(-1);constlonglongmod=998244353,inf=1e9+10;intfac[N+10],ifac[N+10];intqpow(inta,intb,intp){intres=1;while(b){if(b&1)(res*=a)%=p;b>>=1;(a*=a)%=p;}returnres%p;}intinv(intx){returnqpow(x,mod-2,mod)%mod;}voidinit(){fac[0]=1;forr(i,1,N){fac[i]=fac[i-1]*i%mod;}ifac[N]=inv(fac[N]);reforr(i,0,N-1){ifac[i]=ifac[i+1]*(i+1)%mod;}}intC(intn,intm){returnfac[n]*ifac[m]%mod*ifac[n-m]%mod;}voidsolve(){intn,k;string s;cin>>n>>k>>s;s=' '+s;/* 双指针 拓展最长的有k个1的段 任意取的最长段 1的数量都不变 */vector<int>pre(n+1,0);forr(i,1,n){pre[i]=pre[i-1]+(s[i]-'0');}if(pre[n]<k||k==0)returncout<<1<<endl,void();// 不操作// 该题 问的是最多进行一次操作 不操作也可以得到1// ICPC南昌邀请赛I 问的是进行一次操作intans=0;if(k==1){vector<int>cnt;intz=0;forr(i,1,n){if(s[i]=='1'){cnt.push_back(z);z=0;if(cnt.size()>1){inttp=cnt.size();ans+=cnt[tp-1]+cnt[tp-2];}}elsez++;}cnt.push_back(z);inttp=cnt.size();ans+=cnt[tp-1]+cnt[tp-2]+1;// 进行一次操作也可以不修改}else{intnowl=1,nowr=0,lstr=-1;while(nowr<n){while(nowr<n&&pre[nowr+1]-pre[nowl-1]<=k)nowr++;if(pre[nowr]-pre[nowl-1]<k)break;// 判断区间1的个数intlap=0;// 和上一段重叠部分if(lstr>=nowl)lap=C(lstr-nowl+1,pre[lstr]-pre[nowl-1]);// nowl~lstr这一段的1数量不变 就是两段都会算的部分(ans+=C(nowr-nowl+1,pre[nowr]-pre[nowl-1])-lap+mod)%=mod;while(nowl<=nowr&&pre[nowr]-pre[nowl-1]>=k)nowl++;// 摆脱1数量=k的这一段lstr=nowr;}}cout<<ans<<endl;}

E 状压 绝对值 贪心

题意：r [ i ] = ∑ j = 1 m p [ j ] s [ i ] [ j ] r[i] = \sum_{j = 1} ^m p[j] s[i][j]r[i]=∑j=1m​p[j]s[i][j]。给定 x[i] ，问∑ i = 1 n ∣ r [ i ] − x [ i ] ∣ \sum_{i = 1}^n |r[i] - x[i]|∑i=1n​∣r[i]−x[i]∣的最大值

无论实际情况如何，总有：∣ r i − x i ∣ = sign i ⋅ ( r i − x i ) |r_i - x_i| = \text{sign}_i \cdot (r_i - x_i)∣ri​−xi​∣=signi​⋅(ri​−xi​)其中sign i \text{sign}_isigni​的取值取决于r i r_iri​和x i x_ixi​的大小关系。
由于n ≤ 10 n \leq 10n≤10，我们可以枚举所有2 n 2^n2n种符号组合( sign 1 , sign 2 , … , sign n ) (\text{sign}_1, \text{sign}_2, \ldots, \text{sign}_n)(sign1​,sign2​,…,signn​)。

对于固定的符号组合，目标函数变为：
∑ i = 1 n sign i ( r i − x i ) = ∑ i = 1 n sign i r i − ∑ i = 1 n sign i x i \sum_{i=1}^n \text{sign}_i(r_i - x_i) = \sum_{i=1}^n \text{sign}_i r_i - \sum_{i=1}^n \text{sign}_i x_ii=1∑n​signi​(ri​−xi​)=i=1∑n​signi​ri​−i=1∑n​signi​xi​
这里的关键是：我们不是在猜测实际的符号，而是在尝试所有可能的符号分配方式。并且符合r i r_iri​和x i x_ixi​的大小关系的符号一定能取到最大值。
因此可以把绝对值符号去掉。

对于每一种符号组合，我们计算：

• 固定值：− ∑ i = 1 n sign i x i -\sum_{i=1}^n \text{sign}_i x_i−∑i=1n​signi​xi​（这部分与p pp无关）
• 可变值：∑ i = 1 n sign i r i = ∑ j = 1 m p j ( ∑ i = 1 n sign i s i , j ) \sum_{i=1}^n \text{sign}_i r_i = \sum_{j=1}^m p_j \left(\sum_{i=1}^n \text{sign}_i s_{i,j}\right)∑i=1n​signi​ri​=∑j=1m​pj​(∑i=1n​signi​si,j​)

然后我们通过排序找到使可变值最大的排列p pp。

voidsolve(){intn,m;cin>>n>>m;vector<int>x(n+1);vector<string>s(n+1);forr(i,1,n)cin>>x[i];forr(i,1,n)cin>>s[i];intmx=-1;vector<int>ans;/* 因为枚举正负号，绝对值的情况被包含在内，并且肯定是最大值 如果枚举的正负号不贴合去掉绝对值的情况，必然得不到最大值 */forr(b,0,(1<<n)-1){// 状压// 枚举正负符号情况 1:r_i>x_i |r_i-x_i|=r_i-x_i 0:r_i<x_i |r_i-x_i|=-r_i+x_ivector<int>tp(m+1);vector<pii>v(m+1);// 每个位置的系数 需要记录下标forr(j,1,m)v[j]={0,j};intxsm=0;forr(i,1,n){if(b>>(i-1)&1){xsm-=x[i];forr(j,1,m){if(s[i][j-1]-'0')v[j].fir++;}}else{xsm+=x[i];forr(j,1,m){if(s[i][j-1]-'0')v[j].fir--;}}}// cout<<"xsm"<<xsm<<endl;// 因为是排列 待填p_i是固定的 系数大的分配大的p_isort(v.begin()+1,v.end());intrsm=0;forr(j,1,m){tp[v[j].sec]=j;rsm+=j*v[j].fir;}// cout<<"rsm"<<rsm<<endl;if(rsm+xsm>mx){mx=rsm+xsm;ans=tp;}}forr(i,1,m)cout<<ans[i]<<' ';cout<<endl;}