题解：CF2241F A Bit Odd

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

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

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

:::info[证明] 定义 \operatorname{inv}(s) 表示字符串 s 的逆序对数。假设初始时处于状态三，Alice 选择删除子序列 a，且剩下了子序列 b。由于 s 处于状态三，s 中任何一个 0 前面都有偶数个 1，任何一个 1 后面都有偶数个 0；并且根据题目要求，必须有 \operatorname{inv}(a)\equiv1\pmod2。我们需要证明子序列 b 不可能处于状态三。

记 \operatorname{inv}(a,b) 表示 a,b 之间的交叉逆序对数量。交叉逆序对分为两种：

将 s 拆分为 a 和 b 时，总逆序对数满足 \operatorname{inv}(s)=\operatorname{inv}(a)+\operatorname{inv}(b)+\operatorname{inv}(a,b)。

我们使用反证法，先假设 b 也处于状态三。考察 \operatorname{inv}(a,b) 的奇偶性：

对于第一种类型的交叉逆序对，考虑 b 中每个 0：原序列 s 中它前面有偶数个 1；而在 b 中，由于 b 也处于状态三，故在 b 中它前面也有偶数个 1。由于两偶数相减得到的仍然为偶数，故在 a 中且在它前面的 1 的数量也为偶数。将 b 中所有 0 贡献的偶数个交叉逆序对求和，得到的仍然是偶数。
对于第二种类型的交叉逆序对，考虑 b 中每个 1：原序列 s 中它后面有偶数个 0；而在 b 中，由于 b 也处于状态三，故在 b 中它后面也有偶数个 0。由于两偶数相减得到的仍然为偶数，故在 a 中且在它后面的 0 的数量也为偶数。将 b 中所有 1 贡献的偶数个交叉逆序对求和，得到的仍然是偶数。

既然两种类型的交叉逆序对数量都是偶数，那么二者之和，即 \operatorname{inv}(a,b) 也是偶数。

将这些奇偶性代入之前的式子：

\operatorname{inv}(s)&=\operatorname{inv}(a)+\operatorname{inv}(b)+\operatorname{inv}(a,b)\\ 0&\equiv1+\operatorname{inv}(b)+0\pmod2\\ \operatorname{inv}(b)&\equiv1\pmod2 \end{aligned}

这说明 \operatorname{inv}(b) 一定是奇数，也就是 b 处于状态一，与假设矛盾，故子序列 b 不可能处于状态三，即 Alice 操作后剩下的序列一定是状态一或状态二，所以初始时若 s 处于状态三，则 Bob 必胜。 :::

由于是 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;
}