You are given a string $s$ of even length $n$. String $s$ is binary, in other words, consists only of 0's and 1's.
String $s$ has exactly $\frac{n}{2}$ zeroes and $\frac{n}{2}$ ones ($n$ is even).
In one operation you can reverse any substring of $s$. A substring of a string is a contiguous subsequence of that string.
What is the minimum number of operations you need to make string $s$ alternating? A string is alternating if $s_i \neq s_{i + 1}$ for all $i$. There are two types of alternating strings in general: 01010101... or 10101010...
思路：
可以注意到，每次交换必定会使某对10成功匹配，因此答案为连续相邻为1的对数和连续相邻为0的对数取最大值。
通过样例也能猜出来（bushi）
1 #include <bits/stdc++.h> 2 #define fi first 3 #define se second 4 #define mm(a,b) memset(a,b,sizeof(a)) 5 #define PI acos(-1) 6 #define int long long 7 #define no cout<<"NO\n"; 8 #define yes cout<<"YES\n"; 9 using namespace std; 10 typedef long long LL; 11 typedef pair<int, int> PII; 12 const int N = 1e6+10; 13 const int mod=998244353; 14 int n,m,a[N],b[N]; 15 signed main() 16 { 17 ios::sync_with_stdio(false); 18 cin.tie(0),cout.tie(0); 19 int T=1; 20 cin>>T; 21 while(T--) 22 { 23 string s; 24 cin>>n; 25 cin>>s; 26 int ans=0; 27 int num1=0; 28 for(int i=0;i<s.size()-1;i++) 29 { 30 if(s[i]==s[i+1]&&s[i]=='1') 31 { 32 num1++; 33 } 34 } 35 ans=max(ans,num1); 36 int num2=0; 37 for(int i=0;i<s.size()-1;i++) 38 { 39 if(s[i]==s[i+1]&&s[i]=='0') 40 { 41 num2++; 42 } 43 } 44 ans=max(ans,num2); 45 cout<<ans<<"\n"; 46 } 47 return 0; 48 } 49