[数据结构与算法]B - Reverse Binary Strings(思维)

B - Reverse Binary Strings

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

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

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

10101001 -10101010 。

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

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

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

我们假设这个串里的0一共就当前的这 6 个。
那么我们最多可以构造多少相邻的 1 ？
很容易看出：

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

总结规律可以发现 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;
    }
}