Codeforces Round 1114 (Div. 3)

Codeforces Round 1114 (Div. 3)

前言

本周的cf简直是疯狂，一周连着4场比赛，我会吃不消的！不过幸亏是Div 3的题目还能写一些。
但是这是怎么回事，头好疼！

回忆已成过去，逝去的永远都是逝去的，我们无法挽回，也无法阻止，有的只有惋惜与怀念，更多的是在床边倾听“精华”。

本周这场的题目也是相当之简单了，纯思维逻辑推理。但是这种题也是一样的恶心啊，你要是想不出来那就是想不出来，基本也就锁死不会了。所以这种题也还得多练练了。

A题

Problem - A - Codeforces

Alice, 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.、

Input

The 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).

Output

For each test case, output a single integer — the number of rounds the game will last before it ends.

Example

Input

61234613371710619111

Output

120330

思路：纯签到，先排序，然后直接就是判断两两之间的差值最小值输出就行了。

AC代码

#include<bits/stdc++.h>usingnamespacestd;#defineIOSios::sync_with_stdio(0),cin.tie(0),cout.tie(0)#defineintlonglong#defineendl'\n'#definepiipair<int,int>#definefifirst#definesesecond#defineYEScout<<"YES"<<endl#defineNOcout<<"NO"<<endlvoidsolve(){inta[5];for(inti=1;i<=3;i++)cin>>a[i];sort(a+1,a+4);// cout<<a[1]<<a[2]<<a[3];// cout<<endl;if(a[1]==a[2]||a[2]==a[3]){cout<<0<<endl;return;}intshu1=a[2]-a[1],shu2=a[3]-a[2];intans=min(shu1,shu2);cout<<ans<<endl;// cout<<fixed<<setprecision(x)}signedmain(){IOS;int_=1;cin>>_;while(_--)solve();return0;}

B题

Problem - B - Codeforces

Let 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”| =3
• If 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.

Input

The 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.

Output

For each test case, output a single integer — the minimum possible length of the resulting compressed string after deleting one character.

Example

Input

93abb3aab3abc4abaa4abba5eeeee6yyssee7abacaba18goodluckandhavefun

Output

2221313516

思路：我们通过分析可以得出来答案就是压缩后得长度减1或i这减2，那么这到底怎么判断呢？我们这里是先删除再压缩，所以我们就得找到一个合适得位置让删除最大化，那我们就先把连着得重复的先压缩在一起在说，然后我们发现如果压缩完之后的数组长度如果有单个出现的然后就像这样 1 2 1 两个一隔着一个出现，那么我们肯定就选择这个2嘛，答案就是现在数组长度减去2，但是要是没有，我们就看看有没有单独出现的就像是111 2 333这个2就是单独出现的，有那么我们的答案就是现在数组长度减去1，那要是都是成2个以上出现的那么我们的答案就是现在的数组长度。

AC代码

#include<bits/stdc++.h>usingnamespacestd;#defineIOSios::sync_with_stdio(0),cin.tie(0),cout.tie(0)#defineintlonglong#defineendl'\n'#definepiipair<int,int>#definefifirst#definesesecond#defineYEScout<<"YES"<<endl#defineNOcout<<"NO"<<endlvoidsolve(){intn;string s;cin>>n>>s;vector<pair<char,int>>st;for(charc:s){if(!st.empty()&&st.back().fi==c){st.back().se++;}else{st.push_back({c,1});}}intlen=st.size();intans=LLONG_MAX;for(inti=1;i<=len-2;i++){intres;if(st[i].se>1){res=len;}else{if(st[i-1].fi==st[i+1].fi){res=len-2;}else{res=len-1;}}ans=min(ans,res);}if(ans==LLONG_MAX){ans=len;}cout<<ans<<endl;// cout<<fixed<<setprecision(x)}signedmain(){IOS;int_=1;cin>>_;while(_--)solve();return0;}

C1题

Problem - C1 - Codeforces

This 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.

Input

The 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.

Output

For 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.

Input

9 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 0000111

Output

YES NO YES NO NO YES YES NO YES

思路：这个题乍一看我们是毫无思绪的，怎么通过移动来变成一样的呢？赛时确实有点懵，但是我们通过看样例其实能观察出来一个十分重要的特点，那就是“奇偶性”，我们看看这个奇数位置上的1是不是只会在奇数位置上面蹦跶？偶数位置上的1只能在偶数位置上蹦跶？

如果看懂了这个我们就了解到这个题的精髓了，我们单独统计偶数位置的1的个数，单独统计奇数位置上的1的个数，看看两者是不是相等，要是相等就可以转化为b，不想等就不可能

AC代码

#include<bits/stdc++.h>usingnamespacestd;#defineIOSios::sync_with_stdio(0),cin.tie(0),cout.tie(0)#defineendl'\n'#defineintlonglong#definepiipair<int,int>#definefifirst#definesesecond#defineYEScout<<"YES"<<endl;#defineNOcout<<"NO"<<endl;constintINF=1e6+5;voidsolve(){intn;cin>>n;string a,b;cin>>a>>b;intans1=0,ans2=0;intcnt1=0,cnt2=0;for(inti=0;i<a.size();i++){if((i+1)%2==1){if(a[i]=='1')ans1++;}else{if(a[i]=='1')ans2++;}}for(inti=0;i<b.size();i++){if((i+1)%2==1){if(b[i]=='1')cnt1++;}else{if(b[i]=='1')cnt2++;}}if(cnt1+cnt2==ans1+ans2&&cnt1==ans1&&cnt2==ans2){YES}elseNO// cout<<fixed<<setprecision(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代码

#include<bits/stdc++.h>usingnamespacestd;#defineIOSios::sync_with_stdio(0),cin.tie(0),cout.tie(0)#defineendl'\n'#defineintlonglong#definepiipair<int,int>#definefifirst#definesesecond#defineYEScout<<"YES"<<endl;#defineNOcout<<"NO"<<endl;constintINF=1e6+5;voidsolve(){intn;cin>>n;string a,b;cin>>a>>b;intans1=0,ans2=0;intcnt1=0,cnt2=0;for(inti=0;i<a.size();i++){if((i+1)%2==1){if(a[i]=='1')ans1++;}else{if(a[i]=='1')ans2++;}}for(inti=0;i<b.size();i++){if((i+1)%2==1){if(b[i]=='1')cnt1++;}else{if(b[i]=='1')cnt2++;}}if(cnt1+cnt2==ans1+ans2&&cnt1==ans1&&cnt2==ans2){intshu=0;vector<int>arr1,brr1,arr2,brr2;for(inti=0;i<a.size();i+=2){if(a[i]=='1')arr1.push_back(i);}for(inti=1;i<a.size();i+=2){if(a[i]=='1')arr2.push_back(i);}for(inti=0;i<b.size();i+=2){if(b[i]=='1')brr1.push_back(i);}for(inti=1;i<b.size();i+=2){if(b[i]=='1')brr2.push_back(i);}for(inti=0;i<arr1.size();i++){shu+=(abs(arr1[i]-brr1[i])/2);}for(inti=0;i<arr2.size();i++){shu+=(abs(arr2[i]-brr2[i])/2);}cout<<shu<<endl;}elsecout<<-1<<endl;// cout<<fixed<<setprecision(x)<<}signedmain(){IOS;int_=1;cin>>_;while(_--)solve();return0;}

总结

后面几场加油吧，起码思维题尽量得打满。