题意

一个01字符串，可对其非空子序列进行操作：如果任意两个相邻的两位不同，可将其01反置；至少几次操作可让该01字符串任意相邻两位都不同。

关键词

构造，

题解

如果想让01字符串任意相邻的两位不相同，也就两种结果：010101...01,101010...10。 那就举1010...10：

10111001111101
10101010101010

观察这两个字符串，首先与1010...10相同的部位，就可以不用看。因为我们要求最少操作次数，对正确的部分实现两次操作，结果是毫无变化，所以没意义。所以只需要看错误的地方，将其组成原字符串的一个子序列。

1011101

因为想要进行01反置，需要其子序列也要任意相邻两位不同。从第一个看（‘1’），构成一个子序列，数量加1。

1

第二个0，需要接在1后面，恰好有一个1结尾的，第三个1，同理

101

第四个1，需要接在0结尾的，但是并没有，所以新开一个子序列，数量加1

101
1

接下来同理

10101
1
1

因为子序列数量，就是操作的数量，其次子序列是因为看是否满足条件而被迫慢慢加的，所以数量一定是最少的。 代码实现：观察子序列，只要末尾是0还是1重要，前面对于是否能接上0或1没关系，其次我们只需要记住以0结尾的数量，和以1结尾的数量就行，数量大于0，就说明有，可以接上0或1。因此用c1,c0来表示，如果为1且c0!=0,则c0--,c1++，否则只要c1++，0则同理，最后ans=c1+c0。

#include<bits/stdc++.h>
using namespace std;
int cord(string s){
    int c1=0,c0=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='1'){
            if(c0==0) c1++;
            else {
                c1++;c0--;
            }
        }
        else{
            if(c1==0) c0++;
            else{
                c1--;c0++;
            }
        }
    }
    return c1+c0;
}
void slove(string k,int n){
    string s1,s2;
    for(int i=0;i<n;i++){
        if(i%2==1&&k[i]!='1') s1+=k[i];
        else if(i%2==0&&k[i]!='0') s1+=k[i];
    }
    for(int i=0;i<n;i++){
        if(i%2==1&&k[i]!='0') s2+=k[i];
        else if(i%2==0&&k[i]!='1') s2+=k[i];
    }
    int ans=min(cord(s1),cord(s2));
    cout<<ans<<endl;
}
int main(){
    int t;
    cin>>t;
    for(int i=1;i<=t;i++){
        int n;
        cin>>n;
        string k;
        cin>>k;
        slove(k,n);
    }
}