更差的閱讀體驗

經典套路，我個人認為是橙題。

相鄰相等不好刻畫，我們直接把偶數位置反轉，這樣一組相鄰相等中恰好有一個被反轉，變成刪除相鄰不同。

那么假設沒有 \(2\)，最終序列中一定只有 \(0\) 或 \(1\)。所以假設 \(0,1\) 個數分別是 \(c_0, c_1\)，那么由于一次消除一個 \(0\) 一個 \(1\)，所以答案是 \(|c_0 - c_1|\)。

有 \(2\) 之后，其實也不用推式子，直接枚舉 \(c_2\) 個 \(2\) 幾個分給 \(0\) 幾個分給 \(1\) 就行了。

那么這道題就做完了，復雜度 \(O(T|A|)\)。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 500006
using namespace std;
int T,n,ans;
char ch[N];
vector<int> cnt(3);
main()
{
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%s",ch+1),n=strlen(ch+1),cnt={0,0,0},ans=1e15;
		for(int i=2;i<=n;i+=2)if(ch[i]=='0')
			ch[i]='1';
		else if(ch[i]=='1')ch[i]='0';
		for(int i=1;i<=n;i++)cnt[ch[i]^48]++;
		for(int i=0;i<=cnt[2];i++)
			ans=min(ans,abs(cnt[0]+i-cnt[1]-(cnt[2]-i)));
		printf("%lld\n",ans);
	}
	return 0;
}