CF2123A Blackboard Game

原题链接：A. Blackboard Game

Tag：博弈

题目描述

初始时，黑板上有从 \(0\) 到 \(n-1\) 的所有整数。

每一轮的操作如下：

• Alice 选择黑板上的一个整数 \(a\) 并将其擦除；
• 随后 Bob 必须选择一个黑板上的整数 \(b\)，使得 \(a + b \equiv 3 \pmod 4\)，并将其擦除。

游戏依次进行，直到某一方无法执行操作——第一个无法操作的一方判负。 假设双方都采取最优策略，试确定哪一方会获胜。

数据说明：

• \(1\leq t \leq 100\)
• \(1\leq n \leq 100\)

分析

因为数字是从 \(0\) 开始的，所以数字是形如 \(\{0,1,2,3,4,5,6,7,8,9,\cdots\}\) 的。 注意到题目的讨论的是在 \(\bmod 4\) 意义下的。所以我们把这个数组放在 \(\bmod 4\) 意义下去讨论。 数组就变成了 \(\{0,1,2,3,0,1,2,3,0,1,\cdots\}\)， 不难发现存在 \(\{0,1,2,3\}\) 这样的循环节。

因为后手要找到一个和在 \(\bmod 4\) 意义下 \(\equiv 3\) 的数字， 因此我们讨论单个循环节，如果先手选择了 \(3\)，后手就可以选择 \(0\) 来保证和为 \(3 \pmod 4\)。

也就是说对于每一个 \(\{0,1,2,3\}\) 的循环节内部，先手无论从中选择哪个数字， 后手都必然存在一个策略选择一个数字让和为 \(3\)，而且这样的操作可以发生两次。

因此我们只需要考虑有没有若干个完整的这样的循环节来给后手操作。 显然当且仅当 \(n \bmod 4 = 0\) 的时候，后手才能每次都找到一个数字使得和满足条件。

那么结论就是，当 \(n \bmod 4 = 0\) 时，后手必胜。反之先手必胜。

代码实现

void NeverSayNever() {
    int n;
    cin >> n;
    if(n % 4 != 0) cout << "Alice" << endl;
    else cout << "Bob" << endl;
}

日志

本页面创建于 2025/7/4 22:52