B – Reverse Binary Strings(思维)

大家好，欢迎来到IT知识分享网。

B – Reverse Binary Strings

题意：给定一个长度为偶数的01串，0和1个数相等。每次可以选定一个子串进行翻转操作。要求最后翻转成一个0,1交替的串（相邻不同即可）。
思路：这道题要从相邻不同来考虑，如果存在一个相邻相同的串，如：

 ， 那我们一定可以把 00 这对点对通过和后边的串交换变成01交替的合法串。 

那么这个结论可以暂时记作$☆$

 - 。 

再给出几组多个相邻相同的串：

 此处可见有2对相邻 1 ， 3对相邻的0. 

又比如一个比较一般的串:xxx00xxx00xxx00xxx，此处及以下的x代表相邻不同的子串 

是不可以的，0和1 个数要相等，所以只能是1这一类。 

总结规律可以发现 0 和 1 相邻点对的对数，相差不会超过 1 。
那么如果我们可以使得 每一对相邻的0 和 相邻 1 两两匹配， 最后一定可以变成
$☆$处的结论，一步就可以转化成合法串。
所以答案就是匹配每一对 相邻0 和 相邻1 的答案再加上这 1 步 。 即$ans+1$。
现在问题就是如何求 匹配每一对 相邻0 和 相邻1 ？
对于一个序列来说 ， 它的分布一定是：

xxx00xxx00xxx11xxx00xxxx11xxx00xxxx11 诸如此类 

我们希望使得匹配每一对 00和11， 使得某个字串相邻不相同。
就比如从序列的内部向外看，一定会找到最里面的一对区间$[l,r],00xxxx11$，我们可以操作$[l+1,r-1]，0xxxx1$使这一段翻转，我们一定可以得到这个 $01xxxx01$ 这段区间相邻不同。那么这一对00和11匹配完之后，这一个区间$[l,r]$变成了新的相邻不同的子段xxxxx，再向外找新的一对00和11，继续重复上述过程，最终一定可以使得每个子段相邻不同，操作次数就是匹配的对数。加上$☆$处的结论处理一下结尾，最后的答案就是 $匹配数(ans)+1。$
很多题解写成max(ans1,ans2)，这应该是一个意思。

#include<bits/stdc++.h> using namespace std; int main() { 
    int t ; cin >> t; while(t--) { 
    int n ; cin >> n ; string st; cin >> st; int ans1 = 0; int ans2 = 0 ; for(int i = 0 ; i < n ;i ++) { 
    if(st[i] == '1' && st[i-1] == '1') ans1++; if(st[i] == '0' && st[i-1] == '0') ans2++; } if(ans1>ans2) { 
    cout<<ans2 + 1<<endl; } else if(ans2>ans1)cout<<ans1 + 1<<endl; else cout<<ans1<<endl; //cout<<max(ans1,ans2)<<endl; } }