4B 博弈第一课

基础习题

Lasker’s Nim

操作：(1) 取石子 (2) 将某堆石子（≥2）拆成两堆非空石子。请分析 Sg 函数有规律（模 4）。

规律：\(\operatorname{SG}(n)\) 是以 \(4x + 1, 4x + 2, 4x + 4, 4x + 3\) 为一段，不断循环构成的序列。（\(\operatorname{SG}(0) = 0\)）

证明：归纳后按模 \(4\) 分类讨论即可。

2 的幂取石子

规定每次只能取的石子数为 2 的幂。找规律。

规律：P-set 当且仅当 \(3 \ | \ n\)。

AT_arc087_c \(\mathrm{(3, 3, 5)}\)

考虑深度为 \(L\) 的满二叉树，去掉所有在 \(S\) 中的点 \(x\) 到根的路径。容易发现会剩下若干颗满二叉树。

那么问题会被拆成若干个独立的游戏，每个游戏都是一颗满二叉树。

考虑如何计算 \(\text{SG}(x)\)，其中 \(x\) 是深度。\(\text{SG}(x) = \text{mex}_{1 \leq i \leq x}(\oplus_{i \leq j < x} \text{SG}(j))\)。

找规律，发现 \(\text{SG}(x) = \text{lowbit}(x)\)。

AT_abc209_e

如果是 DAG 这道题就是一个朴素的 DP。

由于一个人肯定优先考虑获胜，其次是平局，因此能走到必败局面就一定会走，否则一定会尝试追求平局。

根据上面的结论来一个类 topo 就行了。

AT_abc297_g

可以直接找规律发现周期性和规律，然后 SG 就行了。规律归纳易证。

AT_arc064_b \((1, 5, 3)\)

观察不变量，能发现答案的首尾保持不变，而首尾是否相同决定了结局情况的长度奇偶性。因此答案显然。

CF1425A \((2, 4, 1)\)

这不是贪心吗。

进阶习题

CF1451D \((3, 5, 2)\)

一个策略就是不管先手走什么操作，后手走相反的操作，可以保证点一直在 \(45\degree\) 的线左右。

如果直接这样走后手能赢，那么先手必输。

否则先手可以反根据后手的走法来出牌，先手必胜。

P5932 \((3, 5, 2)\)

直接感受出来了 \((x, y, z)\) 的 P-set 结论，有点惊人了。