明天补DE
B1. Tokitsukaze and Good 01-String (easy version)
一看到字符串还要求最小变换次数，总会想到dp，然后就觉得做不出来。本题要求所有连续的段为偶数，则很容易想到若是一段长为奇数，那么肯定会有一个字符要变动。
eg：0110
最直接的想将连续段周围的奇数段个跳出一个字符变化。
思路：从头遍历到尾，步长为2，若两个字符不等，则累计加1。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
int main()
{
int t;cin>>t;
while(t--)
{
int ans=0;
int n;cin>>n;
string s;cin>>s;
for(int i=0;i<n;i+=2)
{
if(s[i]!=s[i+1])
ans++;
}
cout<<ans<<endl;
}
return 0;
}
B2. Tokitsukaze and Good 01-String (hard version)
在简单版本的基础上，要求组数最少。
特判：如果所有的数组相邻不相等，则处理后无连续的段，但实际上是有一条的。
思路：在简易版中已得出需要处理个数，对于不满足要求的组进行标记，可以删去不影响段数；再遍历统计组的个数。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
bool vis[N];
int main()
{
int t;cin>>t;
while(t--)
{
memset(vis,0,sizeof(vis));
int ans1=0,ans2=0;
int n;cin>>n;
string s;cin>>s;
for(int i=0;i<n;i+=2)
{
if(s[i]!=s[i+1])
{
ans1++;
vis[i]=vis[i+1]=1;
}
}
char ch;
for(int i=0;i<n;i++)
{
if(!vis[i]&&ans2==0)
{
ans2++;
ch=s[i];
}
else if(!vis[i]&&s[i]!=ch)
{
ans2++;
ch=s[i];
}
}
if(!ans2) ans2++;
cout<<ans1<<" "<<ans2<<endl;
}
return 0;
}
