专栏文章

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

BBlackPanda
P14015题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minvegjm
此快照首次捕获于
2025/12/02 08:59
3 个月前
此快照最后确认于
2025/12/02 08:59
3 个月前
查看原文
很厉害的 trick。
考虑对原串所有偶数位翻转，这样后两个操作可以转化为删除子串 01\verb!01! 或 10\verb!10!，并将剩下的部分拼接起来。
不难发现，这样会把所有相邻不同的元素删掉，最后剩下的一定是若干个 00 或若干个 11。
设串串原来 0,1,20,1,2 的个数分别为 c0,c1,c2c_0,c_1,c_2，不难发现，由于删除操作删除的是一对 00 和 11，所以 ∣c0−c1∣|c_0-c_1| 恒不变。因此我们只需要考虑 c2c_2 和 ∣c0−c1∣|c_0-c_1| 的关系即可。
  • 若 c2<∣c0−c1∣c_2 < |c_0-c_1|，我们可以将 22 全部改为 00 和 11 中数量最少的，这样可以保证消除的 0101 对数量最大化。
  • 若 c2≥∣c0−c1∣c_2 \ge |c_0-c_1|，多余的 22 可以两两抵消，最后答案就是 (∣c0−c1∣+c2)mod⁡2(|c_0-c_1| + c_2)\operatorname{mod}2 。
CPP
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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...