题解：CF2241F A Bit Odd

W_C_B_H · 2026-07-03 13:38:33 · 题解

Upd 2026.08.30：换了一个更简洁的证明，感谢 PhirainEX 的启发。

显然若剩余序列长度 \le1，则个序列的逆序对数为 0，当前玩家必败。接下来考虑以下三种状态：

• 若初始时逆序对数为奇数，则 Alice 可以直接把整个序列扔掉，剩下一个空序列，Alice 必胜。
• 若初始时逆序对数为偶数，且存在一个下标 i 使得 s 去掉 s_i 后逆序对数为奇数（等价于 s_i 贡献的逆序对数为奇数），则 Alice 可以直接把除了 s_i 之外的整个序列扔掉，剩下一个长度为 1 的序列，Alice 必胜。
• 如果以上两种情况都不满足，我们发挥自己的注意力，猜测此时 Bob 必胜。

:::info[证明] 显然一个逆序对由一个 1 和它后方的一个 0 构成，一次操作使序列逆序对数减少的量等于这其中的 0 或 1 被删除的逆序对个数。根据容斥原理可知，这等于「1 被删除的逆序对个数」加上「0 被删除的逆序对个数」再减去「0,1 都被删除的逆序对个数」。考察这三项的奇偶性：

由于是 01 串，维护逆序对数只需要前缀和，不需要树状数组之类的。

Submission & Code：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200005;
int _, n, sum[N], tot;
string s;
bool flag;
signed main() {
    cin >> _;
    while (_--) {
        cin >> n >> s;
        s = " " + s;
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (s[i] ^ 48);
        tot = 0;
        for (int i = 1; i <= n; i++) if (s[i] == '0') tot += sum[i];
        if (tot & 1) {
            puts("Alice");
            continue;
        }
        flag = 0;
        for (int i = 1; i <= n; i++) {
            if (s[i] == '0' && (sum[i] & 1)) {
                flag = 1;
                break;
            } else if (s[i] == '1' && ((n - i - sum[n] + sum[i]) & 1)) {
                flag = 1;
                break;
            }
        }
        puts(flag ? "Alice" : "Bob");
    }
    return 0;
}