CF2093F Hackers and Neural Networks这是个大水题由于每次都随机选一个位置所以我们考虑先选一个和文本串最接近的模式串计算它们的相似度即它们相同的部分记作x xx这显然好求然后总操作次数就是先用n nn次操作把空串变成这个模式串然后现在有n − x n-xn−x位与原串不同一位一位操作先把它变成空白然后因为只剩这一个空白了用一个这一位与文本串相同的模式串填补即可。也就是修补一位需要的代价是2 22一共需要修补n − x n-xn−x位加上最初的n nn次操作总操作次数即为n 2 ( n − x ) n2(n-x)n2(n−x)注意判无解如果某一位所有模式串中没有一个与文本串相同的那么肯定无解。code:#includebits/stdc.husingnamespacestd;#define_for(i,a,b)for(inti(a);i(b);i)#definefor_(i,a,b)for(inti(a);i(b);i--)#definelsk1#definersk1|1#defineinf0x3f3f3f3fintn,m;constintmaxn2e310;string a[maxn];intvis[maxn];string t[maxn];intmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);intT;cinT;while(T--){cinnm;_for(i,1,n){cina[i];vis[i]0;}intmaxx0;_for(i,1,m){intcnt0;_for(j,1,n){cint[j];if(a[j]t[j]){cnt;vis[j]1;//第j位是否相同}}maxxmax(maxx,cnt);//寻找相似度最高的串}boolflg0;_for(i,1,n){if(!vis[i]){//判无解flg1;break;}}if(flg)cout-1\n;elsecoutn(n-maxx)*2\n;}return0;}CF2042C Competitive Fishing考虑每次分断点对前面没有贡献对后面的贡献是每个数 1 11对答案的贡献就是n u m 0 − n u m 1 num_0-num_1num0​−num1​n u m numnum表示后缀数量那么由于每次操作都是独立的直接按照对答案的贡献从大到小排序计算某一次s u m ≥ k sum \ge ksum≥k时直接输出答案如果s u m k sum ksumk时当前对答案的贡献b x b_xbx​已经小于0 00了那后面一定凑不到k kk了输出无解。code:#includebits/stdc.husingnamespacestd;#defineintlonglong#define_for(i,a,b)for(inti(a);i(b);i)#definefor_(i,a,b)for(inti(a);i(b);i--)#definelsk1#definersk1|1#defineinf0x3f3f3f3fintn,k;string s;constintmaxn2e510;inta[maxn],sum0[maxn],tmp[maxn];//sum0是后缀0数量tmp则是对答案贡献boolcmp(intx,inty){returnxy;}signedmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);intT;cinT;while(T--){cinnk;cins;memset(sum0,0,sizeofsum0);memset(tmp,0,sizeoftmp);_for(i,1,n)a[i]s[i-1]-0;for_(i,n,1)sum0[i]sum0[i1](!a[i]);_for(i,1,n){tmp[i]2*sum0[i]-(n-i1);tmp[i]-tmp[i];}sort(tmp2,tmp1n,cmp);intsum0;boolflg0;_for(i,2,n){if(sumktmp[i]0){flg1;break;}sumtmp[i];if(sumk){couti\n;break;}}if(flg||sumk)cout-1\n;//无解}return0;}