4B 博弈第二课

• POJ1740 重点在对于 \(n\) 从小到大找规律并证明
• 例二（无题号） 重点也在于打表，随后对于 \(a\) 观察相等表格。
• AT_arc087_c 先想到字典树，然后将问题拆成独立的部分，随后找规律

---

接下来是树上的题

• P6665 前面需要耐心的分析，线段树合并有拆位+标记小巧思
• AT_agc017_d 等效原理（树→链）
• AT_arc038_c 看出每颗棋子互相独立
• 翻硬币（无题号） 模型转换很有意思，随后容易想到 Nim
• 翻硬币扩展（无题号）每一堆石子互相之间仍然互相独立
• Mock-Turtle 找规律，发现 \(f(x)\) 与 \(x\) 的关系
• P2594 努力打表，努力找规律，努力证明！（证明需要分段并归纳考虑）

---

以下是作业了！

• ⭐AT_agc014_d 猜到了完美匹配的结论，证明考虑剥叶子
• AT_agc010_f 摸一下简单的必胜情况，可以得出向权值更小的点移动的策略，进而可以 DP
• ⭐AT_agc043_c 先明确贪心过程的正确性，将其类比成 SG 函数后拆解为多个游戏，发现 \(\text{SG}(x) \leq \sqrt{m}\) 则可以解决。
• AT_agc033_c 这种收缩的题目容易联系到直径
• ⭐AT_arc137_c 先手可达后继完全包含后手可达后继（先手选择的），一个 trick
• AT_arc038_d 先进行关键二分，进行小的转换，考虑类 topo 手段求出必胜必败态（Draw 被题目定义为先手必败）
• ⭐AT_agc010_d 观察总和奇偶性，并对此做出分类讨论
• AT_arc105_d 通过对一个数进行堆叠避免异或和为 \(0\)，随后分讨，一个 trick 是异或和小于正常和
• ⭐AT_agc026_f 需要观察出若先后手转换则后手操作是一定的，并因此对 \(n\) 分讨，二分将问题转化成判定性问题，并分析必胜序列结构即可。