题解：CF1678B2 Tokitsukaze and Good 01-String (hard version)

因为最后对于一个合法的串，要求连续段长度为偶数，所以，我们只关心一个偶数位二元组 (1,2),(3,4) \dots 两个对应的数是否相等。

若不相等，我们只能把这个数对全改为 0/1，但是我们并不知道怎么改更优。

若相等，这个对就是不能改变的，因为把两个数都改变一定不优。

所以对于第一问的答案，我们观察有多少个不相等的对即可。

对于第二问的答案，我们会把中间不相等的段都改成其左或其右一段相等的段的数值，所以对于两个相邻的相等的二元组，若相同则对答案没有贡献，若相等则有 1 的贡献。

特殊的，对于第一个相等的二元组也对答案有 1 的贡献，若所有二元组都不相等则整个串必须变为一个相等的 0/1，所以答案为 1。

代码。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int t,n;
int a[N];
char s[N];
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        scanf("%s",s+1);
        for(int i=1;i<=n;i++){
            a[i]=s[i]-'0';
        }
        int lst=a[1],num=1,ans=0;
        for(int i=2;i<=n;i++){
            // printf("%d\n",lst);
            if(a[i]!=lst){
                if(num&1){
                    num++;
                    ans++;
                }
                else{
                    num=1;
                    lst=a[i];
                }
            }
            else{
                num++;
                lst=a[i];
            }
        }
        int l=0,ans2=0;
        for(int i=1;i<n;i+=2){
            if(a[i]==a[i+1]&&(!ans2||l!=a[i])){
                ans2++;
                l=a[i];
            }
        }
        if(ans2==0)  ans2++;
        printf("%d %d\n",ans,ans2);
    }
}