Codeforces Round 1112 (Div. 2)

A. You Delete, I Delete地址跳转赛时代码#includebits/stdc.h#defineintlonglong#defineendl\nusingnamespacestd;voidsolve(){string s;cins;boolf11,f21;for(inti0;is.size();i){if(s[i]1f1){f10;s[i]A;}if(s[i]0f2){f20;s[i]A;}}string ans;for(inti0;is.size();i)if(s[i]A)continue;elseanss[i];coutansendl;return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intt;cint;while(t--)solve();return0;}Alice删0使字典序最大Bob删1使字典序最小最后剩下的位数是相同的删去最前面的0后面的1会前进一位删去最前面的1前排会少一位1所以Alice和Bob的最优策略都是删掉最前面的0和1一边找一边输出关闭输入输出流后不要用putchar函数boolc00,c10;for(inti0;is.size();i){if(!c0s[i]0){c01;continue;}if(!c1s[i]1){c11;continue;}couts[i];}coutendl;题解代码#includebits/stdc.h#defineintlonglong#defineendl\nusingnamespacestd;voidsolve(){string s;cins;intns.size();s s;boolc00,c10;for(inti1;in;i){if(!c0s[i]0){c0true;continue;}if(!c1s[i]1){c1true;continue;}couts[i];}coutendl;return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intt;cint;while(t--)solve();return0;}B. Merge to Match地址跳转如果a数组的数字都变成b数组的数字后还剩余很多数这些数可以找任意一个数结合删掉对于b数组中的每个数需要在a数组中有一个比它大的数和一个比它小的数才可以变出来找比b数组小的数字是否够用sort(a.begin()1,a.end());sort(b.begin()1,b.end());intl1;for(inti1;im;i){if(a[l]b[i]ln)l;else{coutNOendl;return;}}找比b数组大的数字是否够用l--;intrn;for(intim;i;i--){if(a[r]b[i]rl)r--;else{coutNOendl;return;}}coutYESendl;赛时代码#includebits/stdc.h#defineintlonglong#defineendl\nusingnamespacestd;intn,m;voidsolve(){cinnm;vectorinta(n1),b(m1);for(inti1;in;i)cina[i];for(inti1;im;i)cinb[i];sort(a.begin()1,a.end());sort(b.begin()1,b.end());intl1;for(inti1;im;i){if(a[l]b[i]ln)l;else{coutNOendl;return;}}l--;intrn;for(intim;i;i--){if(a[r]b[i]rl)r--;else{coutNOendl;return;}}coutYESendl;return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intt;cint;while(t--)solve();return0;}C. Maximize the Score地址跳转设dp[i]表示前i位能产生分数的最大值状态转移dp[i]dp[i-1]1;dp[i]dp[pos-1](i-pos1)*(i-pos1)pos是第i位的数字上一次出现的位置标记每一位数字第一次出现的位置vectorintvis(n1);for(inti1;i2*n;i){intxa[i];if(!vis[x])vis[x]i;}根据状态转移写dpfor(inti1;i2*n;i){intxa[i];intjvis[x];dp[i]max(dp[i-1]1,dp[j-1](i-j1)*(i-j1));}coutdp[2*n]endl;赛时代码#includebits/stdc.h#defineintlonglong#defineendl\nusingnamespacestd;intn;voidsolve(){cinn;vectorinta(2*n1);for(inti1;i2*n;i)cina[i];vectorintdp(2*n1),vis(n1);for(inti1;i2*n;i){intxa[i];if(!vis[x])vis[x]i;}for(inti1;i2*n;i){intxa[i];intjvis[x];dp[i]max(dp[i-1]1,dp[j-1](i-j1)*(i-j1));}coutdp[2*n]endl;return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intt;cint;while(t--)solve();return0;}D. Good Pair Queries地址跳转01表示a[i]0,b[i]1;10表示a[i]1,b[i]0;00和11很容易删掉主要问题是处理01和10min(cnt01,cnt10)容易删掉让他们结合就行如果cnt01cnt10多出来的cnt10必须和00或11结合才能删掉此时剩余的cnt10的数量必须小于等于00 11和的数量cnt10m/2同理cnt01m/2统计一下前缀01和10的数量string a,b;cinab;a a;b b;vectorintp1(n1),p2(n1);for(inti1;in;i){p1[i]p1[i-1](a[i]0b[i]1);p2[i]p2[i-1](a[i]1b[i]0);}对于每次询问利用前缀和求出区间内01和10的数量进行判断while(q--){intx,y;cinxy;intmy-x1;intc1p1[y]-p1[x-1];intc2p2[y]-p2[x-1];if(c1*2mc2*2m)coutYESendl;elsecoutNOendl;}赛时代码#includebits/stdc.h#defineintlonglong#defineendl\nusingnamespacestd;intn,q;voidsolve(){cinnq;string a,b;cinab;a a;b b;vectorintp1(n1),p2(n1);for(inti1;in;i){p1[i]p1[i-1](a[i]0b[i]1);p2[i]p2[i-1](a[i]1b[i]0);}while(q--){intx,y;cinxy;intmy-x1;intc1p1[y]-p1[x-1];intc2p2[y]-p2[x-1];if(c1*2mc2*2m)coutYESendl;elsecoutNOendl;}return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intt;cint;while(t--)solve();return0;}