做题笔记 2023 博弈论
也有 2024 的题。
易碎树
Source：广东实验中学 NOIP 模拟赛（2022.10.31，reused on 2023.10.19）- Problem D
两人在一棵无根树上进行游戏，两人轮流操作，每人每次可以选择一个点为根，然后删去所有叶子，若一个人将整棵树删空则他获胜。
现在给出一棵无根树，多次询问，每次询问给出 $x,y$，问如果令 $x$ 为整棵树的根，取出以 $y$ 为根的子树进行游戏，谁会获得胜利。
链的情况是平凡的，我们会发现每次操作只有两种情况，若操作者选取链的端点，则另一个端点会被删去，链长 $-1$；反之链的两个端点都被删去，链长 $-2$。这相当于 bash 博弈，我们通过链长 $\bmod 3$ 的余数即可判断胜者。
这也容易推广到一般的情况，在一棵树中我们只需要关注直径的长度。可以直接说明直径长度每次也只可能 $-1$ 或 $-2$，也可以感性理解，直径一定是最后被删光的部分。总之，我们可以通过一棵树直径长度 $\bmod 3$ 的余数判断胜者。
现在的问题就转化为了，我们需要求出 $x$ 为整棵树的根时，以 $y$ 为根的子树的直径长度。这等价于令任意点为根，求 一棵子树 或 除一棵子树之外部分 的直径长度，这可以方便的用线段树维护，也可以换根 dp 求解，复杂度均为 $O(n\log n)$。
Clashmas
Source：ZR 23 省选 10 连 day1 - Problem A
有一棵 $n$ 个顶点的树，每个顶点属于 Alice 和 Bob 中的一人。Alice 和 Bob 轮流操作，Alice 先手，每人每次可以选择一个度数恰好为 1 的点删去。$n-1$ 次操作后，剩余点的主人获胜。问谁会获得胜利。
略作思考就会发现这个题相当麻烦，需要对 $n$ 的奇偶性做大量分类讨论，我们不妨先将问题简化一下，只考虑 $n$ 为奇数的情况，$n$ 为偶数时只要考虑先手第一步的决策，然后用奇数的方法判断后手是否能获胜即可。
方便起见，我们称属于先手的点为 A，属于后手的点为 B。
我们先来考虑链的情况，我们会发现，先手必胜当且仅当链的中点为 A 且中点左右的两个点至少有一个为 A，也即，链中心的三个点应当形如 AAA，AAB 或 BAA。在这样的局面下，先手每次操作都可以将链的中点移动到两个 A 中间，后手无论怎么操作链的中点还是会移动到 A 上，从而最后剩下的是 A，先手胜。反之，后手每次操作都可以将中点移动到 B 上，最后剩下的是 B，后手胜。
这个结论不能直接推广。
我们再来考虑菊花的情况，先手必胜要求最后剩下的两个点都是 A，菊花中心一定会留到最后一步，所以中心必须为 A，在此基础上我们只要比较叶子中 A 和 B 的个数就可以判断最后会剩下谁的叶子。
综合上面两种情况，我们考虑从一般的树上找一个类似的结构，这确实很需要人类智慧。
我们可以找到树的重心。首先重心本身必须为 A，否则无论先手如何操作，后手总是有维持重心的能力从而获胜。我们考察重心的所有子树，根据根的归属来确定整棵子树的归属，那么，先手必胜当且仅当属于 A 的子树大小总和不小于属于 B 的子树大小总和。
在我们的期望中，A 和 B 都会尽可能去消除对方的子树。但是这里需要注意，除最后一次操作外，其余时候原重心需要保证有大于一个儿子，否则后手如果提前删掉原重心，整个策略就失效了。这也就要求先手时刻保证重心不改变，否则如果原重心只剩两棵子树时有一棵子树过大，此时先手想调整也为时已晚。
现在轮到先手操作。先手删 B 会导致重心移动一定是由于存在一棵 A 的子树，其大小恰好为总点数一半。先手依旧去删 B，此时重心转移到两个 A 之间，后手操作时可能将重心移动到两个 A 中的任意一个，先手只需要再将重心移回两个 A 之间即可（类似直径上的分析）。（所以要求 A 子树较大实际上是为了在重心移动阶段先手更优）
如果 A 的子树大小小于 B 的子树大小，游戏也会在某时刻进入重心移动阶段，而后手总有能力将重心移到 B，从而最后剩下的点也为 B。
综上，我们就大致证明了之前提到的结论。
取石子
Source：NOI.AC NOI 2024 省选训练赛 34 - Problem C
有 $n$ 堆石子，第 $i$ 堆石子有 $x_i$ 个。Alice 和 Bob 轮流取石子，Alice 先手，每人每次从一堆石子中取 $a\sim b$ 个。无法操作的人失败。此外，当一个人取完一堆石子时他会立即获胜。求谁会获胜。
$n$ 堆石子每个都可以视作子游戏，所以我们考虑使用 SG 函数。但需要注意，如果一堆石子被取完，整个游戏立刻停止，这并不好在 SG 函数中描述。具体来说，如果一堆石子的个数在 $a\sim b$ 之间，那么游戏会马上结束。事实上我们发现，一堆石子的个数在 $a\sim b$ 之间，这种状态无论在什么情况下都是绝对劣的，只要有人转移到这种状态，无论全局状态如何他都会马上输掉游戏，因此我们也可以认为这些状态根本就不可达。据此计算 SG 函数即可。注意开局时如果存在 $a\sim b$ 的堆先手直接获胜。
斐波那契树游戏
Source：NOI.AC NOI 2024 省选训练赛 44 - Problem C
转化题意：给你一棵二叉树，两人轮流操作，每人每次挑选一个顶点并删去以其为根的子树，删去最后一个顶点的人失败（misere play condition），求谁会获胜。
misere play condition 下的游戏处理起来很不符合直觉，但是我们发现一个人会输当且仅当现在只剩一个点，反过来说，一个人只要把树删的只剩根，他就获胜了。这意味着，原游戏等价于我们将根去掉，分成若干子树，然后在这些子树上进行 normal play condition 下的游戏。
现在我们有多个子游戏，所以我们肯定要用 SG 函数。很自然的会想到一棵树的 SG 值应当和根的所有子树的 SG 值异或和有关联，但并不是直接相等。
我们将根的所有子树看作一个游戏，这个游戏的 SG 值当然就是所有子树 SG 值的异或和。现在用一个点连接所有子树的根，所带来的影响相当于是原游戏的所有状态都新增了一个 SG 值为 $0$ 的后继状态（$\varnothing$），于是游戏的 SG 值 $+1$。
所以一棵树的 SG 值等于其所有子树的 SG 值的异或和再加上 $1$。
本题中的二叉树条件并不重要。
石子游戏
Source：百度之星 2023 总决赛 - Problem J
给定若干堆石子，两人轮流操作，每人每次需要从石子数量最多的堆中拿走若干颗石子，不能操作者输。给一个由正整数组成的可重集 $S$，支持两种操作：
- 向 $S$ 中加入 $x$；
- 对于所有满足 $x\in S,l\le x\le r$ 的 $x$，以 $1/2$ 的概率将一堆大小为 $x$ 的石子加入游戏。查询先手必胜的概率。
由于本题带修还要做区间查询，所以先手必胜的判定条件应当是简洁的。
从规模较小的情况入手。一堆石子的情况过于平凡，考虑两堆石子的情形。两堆石子有很强的对称性，容易发现，先手必败当且仅当两堆石子的石子个数相同，后手只需模仿先手操作即可。
接下来考虑推广。由于玩家只能操作石子最多的堆，影响游戏胜负的应当也只和石子最多的那几堆有关。结合两堆石子时的结论，通过尝试，可以类似的得出先手必败当且仅当石子最多的堆有偶数个。证明是容易的。
有了结论后用值域线段树维护单点修改和区间查询即可。
博弈
Source：ACC 2024 省选联测 26（p_b_p_b）- Problem A
给定 $n$ 个点 $m$ 条边的 DAG，边总是从编号小的点连向编号大的点，每个点为黑色或白色，初始时有些点上有棋子。A 和 B 轮流操作，A 先手。A 每次选一个白点上的棋子沿某条出边的方向移动一步，B 每次选一个黑点上的棋子沿某条出边移动一步，不能操作者输。问在所有 $2^n$ 种初始棋子摆放方式中，有多少种使 A 必胜，取模。
本题中两人能采取的操作集合并不一样，不是公平组合游戏，不适用通常的分析方法。当然，每颗棋子独立，我们还是只考虑单颗棋子。
点分为黑色和白色的好处是，只要我不把棋子移到对方的点上，对方无法影响我的操作，决策完全取决于我自己，每个人的目的应当是最大化自己可操作的步数减去对方的可操作步数，基于此就可以直接在 DAG 上 dp 了。
计数只需保证 A 的可操作步数严格大于 B，背包解决即可，复杂度 $O(n^3)$。
直觉上会将这个题考虑的相当复杂，实际上可以说明一个人总是不会将自己的棋子移动到由 $>1$ 个对方点构成的段上，要么我不通过这种操作也可以获胜，要么我也不可能逼迫对手将棋子再移回我方点上获利。
本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
