4B 博弈第二课

📅 2026/7/30 22:26:35 👁️ 阅读次数 📝 编程学习
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\) 分讨,二分将问题转化成判定性问题,并分析必胜序列结构即可。