CF1363B Subsequence Hate 题解

description：

将一个 01 串变为不含 010 和 101 子串的字符串。

solution：

仔细分析一下性质就可以发现，我们大部分情况下需要将整个字符串都变成 0 或 1。

但是如果整个字符串中只有一个 0/1 在字符串的两端，那么情况也是合法的。

所以我们只需要在变字符串的时候每次都更新一下两种数字的最小值就行了。

其最小值就意为最小可以获取的步数。

code：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		char s[1005];
		int cnt1=0,cnt2=0;
		scanf("%s",s);
		for(int i=0;i<strlen(s);i++)
		{
			if(s[i]=='0')
			cnt1++;
			else
			cnt2++;
		}
		int ans=1000000;
		for(int i=0;i<strlen(s);i++)
		{
			ans=min(ans,min(cnt1,cnt2));
			if(s[i]=='0')
			{
				cnt1--;
				cnt2++;
			}
			else
			{
				cnt1++;
				cnt2--;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}