题解：P14015 [ICPC 2024 Nanjing R] 生日礼物

· · 题解

更好的阅读体验

经典套路，我个人认为是橙题。

相邻相等不好刻画，我们直接把偶数位置反转，这样一组相邻相等中恰好有一个被反转，变成删除相邻不同。

那么假设没有 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;
}