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

文章目录C 贪心 策略D 组合数学 容斥原理E 状压 绝对值 贪心参考Ander 的题解C 贪心 策略基本策略操作1改小的让大的数进行操作2变成小的voidsolve(){intn,k;cinnk;vectorinta(n1),pre(n1,0);intsm0;forr(i,1,n)cina[i];sort(a.begin()1,a.end());forr(i,1,n){pre[i]pre[i-1]a[i];}if(pre[n]a[1]k)cout0endl;else{intmninf;reforr(i,1,n){intaftsmk-pre[i]a[1];// 修改的部分最后得到的和intaim;// aim*(n-i1)aftsmif(aftsm0)aimaftsm/(n-i1);// aim是a[1]要改成的数elseaim(aftsm-ni)/(n-i1);// 负数向下取整mnmin(mn,max(a[1]-aim,0ll)n-i);}coutmnendl;}}D 组合数学 容斥原理constintN1e5,M1e5;constdoublePIacos(-1);constlonglongmod998244353,inf1e910;intfac[N10],ifac[N10];intqpow(inta,intb,intp){intres1;while(b){if(b1)(res*a)%p;b1;(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[i1]*(i1)%mod;}}intC(intn,intm){returnfac[n]*ifac[m]%mod*ifac[n-m]%mod;}voidsolve(){intn,k;string s;cinnks;s s;/* 双指针 拓展最长的有k个1的段 任意取的最长段 1的数量都不变 */vectorintpre(n1,0);forr(i,1,n){pre[i]pre[i-1](s[i]-0);}if(pre[n]k||k0)returncout1endl,void();// 不操作// 该题 问的是最多进行一次操作 不操作也可以得到1// ICPC南昌邀请赛I 问的是进行一次操作intans0;if(k1){vectorintcnt;intz0;forr(i,1,n){if(s[i]1){cnt.push_back(z);z0;if(cnt.size()1){inttpcnt.size();anscnt[tp-1]cnt[tp-2];}}elsez;}cnt.push_back(z);inttpcnt.size();anscnt[tp-1]cnt[tp-2]1;// 进行一次操作也可以不修改}else{intnowl1,nowr0,lstr-1;while(nowrn){while(nowrnpre[nowr1]-pre[nowl-1]k)nowr;if(pre[nowr]-pre[nowl-1]k)break;// 判断区间1的个数intlap0;// 和上一段重叠部分if(lstrnowl)lapC(lstr-nowl1,pre[lstr]-pre[nowl-1]);// nowl~lstr这一段的1数量不变 就是两段都会算的部分(ansC(nowr-nowl1,pre[nowr]-pre[nowl-1])-lapmod)%mod;while(nowlnowrpre[nowr]-pre[nowl-1]k)nowl;// 摆脱1数量k的这一段lstrnowr;}}coutansendl;}E 状压 绝对值 贪心题意r [ i ] ∑ j 1 m p [ j ] s [ i ] [ j ] r[i] \sum_{j 1} ^m p[j] s[i][j]r[i]∑j1m​p[j]s[i][j]。给定 x[i] 问∑ i 1 n ∣ r [ i ] − x [ i ] ∣ \sum_{i 1}^n |r[i] - x[i]|∑i1n​∣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_{i1}^n \text{sign}_i(r_i - x_i) \sum_{i1}^n \text{sign}_i r_i - \sum_{i1}^n \text{sign}_i x_ii1∑n​signi​(ri​−xi​)i1∑n​signi​ri​−i1∑n​signi​xi​这里的关键是我们不是在猜测实际的符号而是在尝试所有可能的符号分配方式。并且符合r i r_iri​和x i x_ixi​的大小关系的符号一定能取到最大值。因此可以把绝对值符号去掉。对于每一种符号组合我们计算固定值− ∑ i 1 n sign i x i -\sum_{i1}^n \text{sign}_i x_i−∑i1n​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_{i1}^n \text{sign}_i r_i \sum_{j1}^m p_j \left(\sum_{i1}^n \text{sign}_i s_{i,j}\right)∑i1n​signi​ri​∑j1m​pj​(∑i1n​signi​si,j​)然后我们通过排序找到使可变值最大的排列p pp。voidsolve(){intn,m;cinnm;vectorintx(n1);vectorstrings(n1);forr(i,1,n)cinx[i];forr(i,1,n)cins[i];intmx-1;vectorintans;/* 因为枚举正负号绝对值的情况被包含在内并且肯定是最大值 如果枚举的正负号不贴合去掉绝对值的情况必然得不到最大值 */forr(b,0,(1n)-1){// 状压// 枚举正负符号情况 1:r_ix_i |r_i-x_i|r_i-x_i 0:r_ix_i |r_i-x_i|-r_ix_ivectorinttp(m1);vectorpiiv(m1);// 每个位置的系数 需要记录下标forr(j,1,m)v[j]{0,j};intxsm0;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{xsmx[i];forr(j,1,m){if(s[i][j-1]-0)v[j].fir--;}}}// coutxsmxsmendl;// 因为是排列 待填p_i是固定的 系数大的分配大的p_isort(v.begin()1,v.end());intrsm0;forr(j,1,m){tp[v[j].sec]j;rsmj*v[j].fir;}// coutrsmrsmendl;if(rsmxsmmx){mxrsmxsm;anstp;}}forr(i,1,m)coutans[i] ;coutendl;}