Codeforces Round 1114 (Div. 3)前言本周的cf简直是疯狂一周连着4场比赛我会吃不消的不过幸亏是Div 3的题目还能写一些。但是这是怎么回事头好疼回忆已成过去逝去的永远都是逝去的我们无法挽回也无法阻止有的只有惋惜与怀念更多的是在床边倾听“精华”。本周这场的题目也是相当之简单了纯思维逻辑推理。但是这种题也是一样的恶心啊你要是想不出来那就是想不出来基本也就锁死不会了。所以这种题也还得多练练了。A题Problem - A - CodeforcesAlice, Bob, and Charlie are playing a game with tokens. They start with a, b, and c tokens, respectively.The game is played in rounds. Before the beginning of each round, they check the number of tokens everyone has:If any two players have the exact same number of tokens, the game immediately ends.Otherwise, the round begins, all three players have a strictly different number of tokens. The player with the strictly most tokens gives exactly 1 token to the player with the strictly fewest tokens.Given the starting tokens a, b, and c, determine exactly how many rounds the game will last before it ends.、InputThe first line contains a single integer t (1≤t≤103) — the number of test cases.Each test case consists of a single line containing three integers a, b, and c (1≤a,b,c≤10).OutputFor each test case, output a single integer — the number of rounds the game will last before it ends.ExampleInput61234613371710619111Output120330思路纯签到先排序然后直接就是判断两两之间的差值最小值输出就行了。AC代码#includebits/stdc.husingnamespacestd;#defineIOSios::sync_with_stdio(0),cin.tie(0),cout.tie(0)#defineintlonglong#defineendl\n#definepiipairint,int#definefifirst#definesesecond#defineYEScoutYESendl#defineNOcoutNOendlvoidsolve(){inta[5];for(inti1;i3;i)cina[i];sort(a1,a4);// couta[1]a[2]a[3];// coutendl;if(a[1]a[2]||a[2]a[3]){cout0endl;return;}intshu1a[2]-a[1],shu2a[3]-a[2];intansmin(shu1,shu2);coutansendl;// coutfixedsetprecision(x)}signedmain(){IOS;int_1;cin_;while(_--)solve();return0;}B题Problem - B - CodeforcesLet f(s) be the compressed version of a string s, formed by replacing every maximal contiguous block of identical characters with a single copy of that character. For example, f(“aabbcc”) “abc”.Let |s| denote the length of a string s. Following this, |f(s)| denotes the length of the compressed string. For example:|f(“aabbcc”)| |“abc”| 3If the string is empty, its length is 0.Yousef has given you a string s consisting of n lowercase Latin letters. You must delete exactly one character si (2≤i≤n−1) to form a new string s′, and then find the minimum possible value of |f(s′)|.Note that you cannot delete s1 or sn.InputThe first line contains an integer t (1≤t≤104) — the number of test cases.The first line of each test case contains an integer n (3≤n≤2⋅105) — the length of the string.The second line of each test case contains a string s (|s|n), consisting of lowercase Latin letters.It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.OutputFor each test case, output a single integer — the minimum possible length of the resulting compressed string after deleting one character.ExampleInput93abb3aab3abc4abaa4abba5eeeee6yyssee7abacaba18goodluckandhavefunOutput2221313516思路我们通过分析可以得出来答案就是压缩后得长度减1或i这减2那么这到底怎么判断呢我们这里是先删除再压缩所以我们就得找到一个合适得位置让删除最大化那我们就先把连着得重复的先压缩在一起在说然后我们发现如果压缩完之后的数组长度如果有单个出现的然后就像这样 1 2 1 两个一隔着一个出现那么我们肯定就选择这个2嘛答案就是现在数组长度减去2但是要是没有我们就看看有没有单独出现的就像是111 2 333这个2就是单独出现的有那么我们的答案就是现在数组长度减去1那要是都是成2个以上出现的那么我们的答案就是现在的数组长度。AC代码#includebits/stdc.husingnamespacestd;#defineIOSios::sync_with_stdio(0),cin.tie(0),cout.tie(0)#defineintlonglong#defineendl\n#definepiipairint,int#definefifirst#definesesecond#defineYEScoutYESendl#defineNOcoutNOendlvoidsolve(){intn;string s;cinns;vectorpairchar,intst;for(charc:s){if(!st.empty()st.back().fic){st.back().se;}else{st.push_back({c,1});}}intlenst.size();intansLLONG_MAX;for(inti1;ilen-2;i){intres;if(st[i].se1){reslen;}else{if(st[i-1].fist[i1].fi){reslen-2;}else{reslen-1;}}ansmin(ans,res);}if(ansLLONG_MAX){anslen;}coutansendl;// coutfixedsetprecision(x)}signedmain(){IOS;int_1;cin_;while(_--)solve();return0;}C1题Problem - C1 - CodeforcesThis is the easy version of the problem. In this version, you are only asked to determine whether string a can be transformed into string b.Yousef has given you two binary strings, a and b, of the same length n.You are allowed to perform any of the following operations:Choose a substring∗ in a equal to 001 and replace it with 100, or vice versa (i.e., 001→100 or 100→001).Choose a substring in a equal to 110 and replace it with 011, or vice versa (i.e., 011→110 or 110→011).Your task is to determine whether it is possible to transform string a into string b using a finite number of operations.InputThe first line contains a single integer t (1≤t≤104) — the number of test cases.The first line of each test case contains a single integer n (1≤n≤2⋅105) — the length of each string.The second line of each test case contains a binary string a (|a|n), consisting of only characters 0 and/or 1.The third line of each test case contains a binary string b (|b|n), consisting of only characters 0 and/or 1.It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.OutputFor each test case, output “YES” if the string a can be transformed into string b using a finite number of operations, and “NO” otherwise.You can output the answer in any case (upper or lower). For example, the strings “yEs”, “yes”, “Yes”, and “YES” will be recognized as positive responses.Input9 1 0 0 2 01 10 3 001 100 4 1010 0101 4 1100 1000 5 01001 10010 6 110000 000011 6 111000 000111 7 1001100 0000111OutputYES NO YES NO NO YES YES NO YES思路这个题乍一看我们是毫无思绪的怎么通过移动来变成一样的呢赛时确实有点懵但是我们通过看样例其实能观察出来一个十分重要的特点那就是“奇偶性”我们看看这个奇数位置上的1是不是只会在奇数位置上面蹦跶偶数位置上的1只能在偶数位置上蹦跶如果看懂了这个我们就了解到这个题的精髓了我们单独统计偶数位置的1的个数单独统计奇数位置上的1的个数看看两者是不是相等要是相等就可以转化为b不想等就不可能AC代码#includebits/stdc.husingnamespacestd;#defineIOSios::sync_with_stdio(0),cin.tie(0),cout.tie(0)#defineendl\n#defineintlonglong#definepiipairint,int#definefifirst#definesesecond#defineYEScoutYESendl;#defineNOcoutNOendl;constintINF1e65;voidsolve(){intn;cinn;string a,b;cinab;intans10,ans20;intcnt10,cnt20;for(inti0;ia.size();i){if((i1)%21){if(a[i]1)ans1;}else{if(a[i]1)ans2;}}for(inti0;ib.size();i){if((i1)%21){if(b[i]1)cnt1;}else{if(b[i]1)cnt2;}}if(cnt1cnt2ans1ans2cnt1ans1cnt2ans2){YES}elseNO// coutfixedsetprecision(x)}signedmain(){IOS;int_1;cin_;while(_--)solve();return0;}C2题Problem - C2 - Codeforces这个题就不贴题目了相比上面的easy版本这个版本在于问我们最少转化为b的次数不能转化就输出-1思路区别不多如果你了解了上面一题的精髓那么我们就能理解到这个1只能一个一个对位110-011实质还是一个1在跳跃所以我们就贪心的想我们就让a第一个1对应b的第一个a的第i个对应b的第i个然后这个1是依次跳跃两个所以我们就比较距离/2就行了(还是偶数位置对应偶数位置奇数位置对应奇数位置)因为相互对应关系距离一定是2的倍数最终我们累加起来就行了AC代码#includebits/stdc.husingnamespacestd;#defineIOSios::sync_with_stdio(0),cin.tie(0),cout.tie(0)#defineendl\n#defineintlonglong#definepiipairint,int#definefifirst#definesesecond#defineYEScoutYESendl;#defineNOcoutNOendl;constintINF1e65;voidsolve(){intn;cinn;string a,b;cinab;intans10,ans20;intcnt10,cnt20;for(inti0;ia.size();i){if((i1)%21){if(a[i]1)ans1;}else{if(a[i]1)ans2;}}for(inti0;ib.size();i){if((i1)%21){if(b[i]1)cnt1;}else{if(b[i]1)cnt2;}}if(cnt1cnt2ans1ans2cnt1ans1cnt2ans2){intshu0;vectorintarr1,brr1,arr2,brr2;for(inti0;ia.size();i2){if(a[i]1)arr1.push_back(i);}for(inti1;ia.size();i2){if(a[i]1)arr2.push_back(i);}for(inti0;ib.size();i2){if(b[i]1)brr1.push_back(i);}for(inti1;ib.size();i2){if(b[i]1)brr2.push_back(i);}for(inti0;iarr1.size();i){shu(abs(arr1[i]-brr1[i])/2);}for(inti0;iarr2.size();i){shu(abs(arr2[i]-brr2[i])/2);}coutshuendl;}elsecout-1endl;// coutfixedsetprecision(x)}signedmain(){IOS;int_1;cin_;while(_--)solve();return0;}总结后面几场加油吧起码思维题尽量得打满。