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

· · 题解

在比赛现场，因为我这个题写了一个假做法，浪费了整个队 1h+ 的时间，最终 B 也没调出来，K 也没写完，5 题变 3 题，Ag 变 Cu。最后我为队伍贡献了 0 个题。

最初我只是以为我没见过这个 trick，直到某天翻阅自己写过的题解时，当时发现我在大半年做过一个几乎一模一样的 trick 题。

我再也不会忘记这个 trick 了。

考虑对原串翻转偶数位，这样第二个操作就变成了删去一个子串 \tt01 或 \tt10。那么最后整个串一定是全 \tt0 或全 \tt1 的形式。

设字符串原来 \tt0,1,2 的个数为 c_0,c_1,c_2。由于删子串的操作不会改变 |c_0-c_1|，因此对 c_2 和 |c_0-c_1| 的大小关系讨论即可。

若 c_2<|c_0-c_1|，那么贪心地将 \tt 2 改为 \tt 0,1 中个数更少的那个，答案即为 |c_0-c_1|-c_2。

否则，按上述贪心会多下来一些 \tt 2，自然是 \tt 0,1 交替改，去抵消，答案即为 (|c_0-c_1|+c_2)\bmod 2。

时间复杂度 O(n)。

#include<bits/stdc++.h>
using namespace std;

string s;

void sol()
{
    cin>>s;
    for(int i=1;i<s.size();i+=2)
    {
        s[i]=s[i]=='0'?'1':s[i]=='1'?'0':'2';
    }
    int s0=0,s1=0,s2=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='0') s0++;
        else if(s[i]=='1') s1++;
        else s2++;
    }
    int d=abs(s0-s1);
    if(s2>=d) cout<<(s2+d&1)<<endl;
    else cout<<d-s2<<endl;
}

int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int t;
    cin>>t;
    while(t--) sol();
    return 0;
}