题目题解

问题理解

黑板上初始有 $0, 1, 2, \dots, n-1$ 共 $n$ 个整数。
每轮 Alice 先擦除一个数 $a$，然后 Bob 擦除一个数 $b$，要求 $a + b \equiv 3 \pmod{4}$。
无法行动的玩家输。双方最优，判断谁获胜。

---

第一步：核心观察

Alice 只有在她的回合开始时没有数字可擦除时才会输。
这意味着如果 $n$ 是奇数，Alice 至少会在最后一轮先手擦除最后一个数，之后 Bob 无法行动，因此 Alice 必胜。
实际上，更精确地说，Bob 只有在能够将全部数字配成满足条件的对 $(a, b)$ 时才能赢。

---

第二步：模 4 等价性

条件 $a + b \equiv 3 \pmod{4}$ 只取决于 $a \bmod 4$ 和 $b \bmod 4$。
因此，我们可以将所有数字按模 $4$ 的余数分类，余数相同的数字在游戏中视为等价。

设 $c_0, c_1, c_2, c_3$ 分别表示余数为 $0,1,2,3$ 的数的个数。

---

第三步：配对条件

要使 Bob 能每次都回应 Alice 的选择，他必须能对所有数字进行完美配对，使得每对 $(a, b)$ 满足 $a \bmod 4$ 与 $b \bmod 4$ 配对为：

• $0$ 与 $3$ 配对（因为 $0+3 \equiv 3$）
• $1$ 与 $2$ 配对（因为 $1+2 \equiv 3$）

因此，Bob 获胜的充要条件是：

$$c_0 = c_3 \quad \text{且} \quad c_1 = c_2.$$

否则，Alice 可以选一个无法配对的数（比如多出来的 $0$ 或 $1$），使得 Bob 无法行动，Alice 立即获胜。

---

第四步：计数余数个数

对于 $n$ 个数 $0, 1, \dots, n-1$，它们的余数分布为：

• $c_0 = \left\lfloor \frac{n+3}{4} \right\rfloor$
• $c_1 = \left\lfloor \frac{n+2}{4} \right\rfloor$
• $c_2 = \left\lfloor \frac{n+1}{4} \right\rfloor$
• $c_3 = \left\lfloor \frac{n}{4} \right\rfloor$

---

第五步：化简条件

$c_0 = c_3$ 当且仅当 $n \bmod 4 = 0$。
$c_1 = c_2$ 当且仅当 $n \bmod 4 = 0$。

因此，$c_0 = c_3$ 且 $c_1 = c_2$ 等价于

$$n \equiv 0 \pmod{4}.$$

此时 Bob 获胜；否则 Alice 获胜。

---

第六步：最终结论

$$\text{winner} = \begin{cases} \text{Bob}, & \text{if } n \equiv 0 \pmod{4}, \\ \text{Alice}, & \text{otherwise}. \end{cases} $$

---

代码实现

O(n) 版本（按余数计数）

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

void solve() {
    int n;
    cin >> n;
    vector<int> cnt(4);
    for (int i = 0; i < n; i++) {
        cnt[i % 4]++;
    }
    cout << (cnt[0] == cnt[3] && cnt[1] == cnt[2] ? "Bob" : "Alice") << '\n';
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
}

O(1) 版本（直接判断）

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

void solve() {
    int n;
    cin >> n;
    cout << (n % 4 == 0 ? "Bob" : "Alice") << '\n';
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
}

---

验证样例

$n$	$n \bmod 4$	输出
2		Alice
4	0	Bob
5	1	Alice
7	3
100	0	Bob

与题目输出一致。

---

总结

本题的关键在于：

1. 将数字按模 $4$ 等价分类。
2. 认识到 Bob 获胜的唯一方式是能完美配对 $0$ 与 $3$、$1$ 与 $2$。
3. 推导出该条件等价于 $n$ 是 $4$ 的倍数。
4. 从而得到简单的 $O(1)$ 解法。