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

BlackPanda · 2025-09-17 20:58:32 · 题解

很厉害的 trick。

考虑对原串所有偶数位翻转，这样后两个操作可以转化为删除子串 \verb!01! 或 \verb!10!，并将剩下的部分拼接起来。

不难发现，这样会把所有相邻不同的元素删掉，最后剩下的一定是若干个 0 或若干个 1。

设串串原来 0,1,2 的个数分别为 c_0,c_1,c_2，不难发现，由于删除操作删除的是一对 0 和 1，所以 |c_0-c_1| 恒不变。因此我们只需要考虑 c_2 和 |c_0-c_1| 的关系即可。

• 若 c_2 < |c_0-c_1|，我们可以将 2 全部改为 0 和 1 中数量最少的，这样可以保证消除的 01 对数量最大化。
• 若 c_2 \ge |c_0-c_1|，多余的 2 可以两两抵消，最后答案就是 (|c_0-c_1| + c_2)\operatorname{mod}2 。

void Solve() {
    cin >> s;
    for (int i = 1; i < s.length(); i += 2) {
        if (s[i] == '2') continue;
        s[i] = (s[i] == '1') ? '0' : '1';
    }
    // cout << s << endl;
    int c[3] = { 0, 0, 0 };
    for (auto i : s) {
        c[i - '0']++;
    }
    int res = abs(c[0] - c[1]);
    if (c[2] >= res) cout << ((c[2] + res) & 1) << endl;
    else cout << (res - c[2]) << endl;
    return;
}