更差的阅读体验
经典套路，我个人认为是橙题。
相邻相等不好刻画，我们直接把偶数位置反转，这样一组相邻相等中恰好有一个被反转，变成删除相邻不同。
那么假设没有 \(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;
}