浅谈博弈 DP II
Felix72
·
·
算法·理论
几个月前看到了 浅谈博弈 DP，感觉是高质量好文，一直想写一个类似的博客但是没什么时间。正好今天元旦有空，就来狗尾续貂一下吧。
可能难度上和上一篇文章不太一致，但是风格上会学习的。另：其实文章里面的题目不全是 DP。
博弈问题难点在哪里？
比较困难的博弈问题，往往相比其他问题的不同之处是“不知道如何入手”，即其问题转化相对来说是困难的。如果我们知道了双方的最优决策是什么，那么问题的解决就会容易很多。
因此我们做此类问题的时候，不仅要思考如何维护的问题，更要尝试挖掘问题中的特殊性质（这种“性质”在博弈问题中很多），从而大大简化问题。
博弈模型的分类
- 用 SG 函数分析。这是最“套路”的博弈题，在较早的比赛里常有出现，但是除非套上数据结构或者上树，不然就太经典了，现在比较鲜见。
- 用必胜必败状态分析。这种题比 SG 题稍微有技巧一些，毕竟不能无脑套公式，至少还需要自己推理一下状态定义和转移，它的优化也通常是比较需要手法的。
- 没有固定的分析方式。这类博弈题偏向 Ad-hoc，特点是特异度较高，甚至不能简单地设计出一个多项式复杂度的算法。碰到这种题推性质是关键。
例题部分 A（SG 函数）
这块写简略一些，毕竟不是本文重点。
P2575 高手过招
注意到是阶梯石子模型就非常简单了。
P2594 [ZJOI2009] 染色游戏
你需要知道：对于互相独立的硬币问题（“互相独立”指一个硬币对其他硬币的影响只是简单的异或叠加），一个局面的 SG 值为单个硬币的 SG 值之异或和。
知道这个结论后，你可以直接打表猜硬币的 SG 值，AC 之后再证明。
P6665 [清华集训 2016] Alice 和 Bob 又在玩游戏
## 例题部分 B（必胜-必败状态）
### [P6803 [CEOI 2020] 星际迷航](https://www.luogu.com.cn/problem/P6803)
首先考虑你需要什么信息计算答案。思考后，你会发现只需要记录必胜、必败节点的总数量，而这个信息是可以被矩阵加速的。
那么我们只需要 DP 出每个节点（或其子树）是必胜还是必败节点，以及每个节点会受到多少个节点连接一个必败点的影响从而反转胜负状态即可。
这些信息可以通过简单的换根 DP 得到。
### [P7864 「EVOI-RD1」摘叶子](https://www.luogu.com.cn/problem/P7864)
从这个题开始，我们引入一个很厉害的技巧：
- 虽然你不能确定一个状态是必胜还是必败状态，但是这个状态加上若干独立、无后效的元素一定是必胜的。
证明很简单：
- 如果当前节点必胜，说明一步操作之后可以到达必败状态。那么就算加上了若干无效元素，我们也可以在第一步中照搬原来的方法，并顺便移除这些无效元素即可。
- 否则，直接移除所有无效元素，此时是必败状态，那么初始状态必胜。
那么对于这个题，我们可以导出一个结论：
- 在任何树的任意非叶子上面加任意多个叶子，得到的树一定必胜。
那么初始情况如果符合上面的条件，那么先手必胜；同时双方操作时也一定不希望造出这样的局面。有了这样一条性质，这题就很简单了。
### [P2599 [ZJOI2009] 取石子游戏](https://www.luogu.com.cn/problem/P2599)
直接沿用上一题的思路。
稍微扩展一下：
- 对于任意一种局面，我们在它的左/右边新加入一堆石子，那么最多仅有一种方式可以造出必败状态。
证明：拿加在左边举例，找出最小的石子数量使得新状态必败之后，无论这堆石子有多少，先手都可以一步造出必败状态，因此剩下的状态全是必胜。
那么设置 $l_{i, j}, r_{i, j}$ 表示在 $[i, j]$ 区间的左/右边最少需要加多少石子使得状态必败。转移是简单的。
### [AT_agc048_d [AGC048D] Pocky Game](https://www.luogu.com.cn/problem/AT_agc048_d)
和上一题大同小异。
### [AT_agc043_c [AGC043C] Giant Graph](https://www.luogu.com.cn/problem/AT_agc043_c)
这题的难点是发现它是博弈论题目。
我们容易导出一个不小于 $O(n^3)$ 的算法：从大到小考虑每个点，能选直接选，如果之前有选了的点和它在同一条边上面就选不了。
这看似是一个图论问题，但是对必胜必败模型敏感的同学会发现，这正是 DAG 上博弈的模型。我们把“选”的点等价为必败点，“不选”的点等价为必胜点，那么原问题要求的正是所有必败点的权值和。
转化为博弈论模型之后，很容易看出三个维度的独立性，那么暴力计算出 SG 函数就可以算了。
## 例题部分 C（无固定分析状态）
这类题目的通用方式是反复代入双方的视角思考怎样恶心对方/有利于自己。因为其性质可能过于奇妙，所以通常是人类智慧的。
### [AT_agc005_e [AGC005E] Sugigma: The Showdown](https://www.luogu.com.cn/problem/AT_agc005_e)
这个题是上面说的思想的最好反映。
我们不急着分析形式化形式，直接代入跑的人的视角：后面有个人在追你，不管他的移动方式是什么样的，只要有无敌点位我就尽快钻进去，否则这个游戏在一棵树上进行，~~周围既没有板子又没有窗户的，手上又没有道具能编译，对面还是个带透视纯走地屠夫~~，那还说啥了，只要杀机，第五甚至蛋仔玩过一款的都知道应该直接跑了。这时如果回头那就是纯粹亏身位。
继续带入追的人的视角：已知对面马拉松牵制我，那没办法了，只能跟在后面追。这时如果走回头路那就是让对面先跑，对自己肯定不利。
所以说两人走的都是从树根到叶子的链。直接 dfs 判断能不能进入无敌点位即可。
### [P7387 「EZEC-6」象棋](https://www.luogu.com.cn/problem/P7387)
这题显然不是让你计算炮的 SG 值。那么我们代入棋手的身份思考一下。
如果当前对面有一步棋能吃你一个棋子，那么显然你走对称的操作就能吃他一个棋子。这样以来，就算我不考虑任何其他问题只是“能吃就吃”，吃到的棋子数量也至多少对面一个。
那么回到上帝视角，如果黑棋数量减去红棋数量不是零或一，那么有一边就直接赢了！
我们分这两种情况讨论一下：
1. 如果两边棋子数量相等，那么对于红方来说，自己肯定希望在自己的一步小巧思之后对面无法移动。此时需要打表瞪出结论（这题我做过，确实没有更好的发现结论的办法了。。。），刻画出什么棋盘状态可以让红方必胜；
2. 否则，该情况的红方和上一种情况的黑方处境一致，我们反着分析即可。
打表得到结论后可以 $O(n)$ 判断。具体的结论就留给读者自行发现/证明了。
### [AT_codefestival_2016_final_h Tokaido](https://www.luogu.com.cn/problem/AT_codefestival_2016_final_h)
~~（题外话：这题的工单可以看到小圆开战红钻头，但是我坚持认为 DP 部分是紫的）~~
利用 [浅谈博弈 DP](https://www.luogu.com.cn/article/cppcue0v) 中“记录得分差值”的技巧，设 $f_i$ 表示自己的棋子在 $i - 1$，对方的棋子在 $i$，轮到自己操作，自己得分减去对方得分的最大值。
转移是简单的。考虑优化：我此时在 $i - 1$，到底要移动到哪一个位置能让贡献差值最大呢？
可以感性理解出两种方式：
1. $i - 1$ 的移动方式可以和在 $i$ 时相同。这是因为 $i$ 的转移点对于 $i$ 是最优的，那么对于 $i - 1$ 肯定也劣不到哪里去，最多就是让了对手一个 $a_i$。
2. 如果上面的方式不是最优的，那么肯定是 $i - 1$ 有一种神秘转移点，这种转移点是自己在位置 $i$ 时无论如何也无法达到的。很显然，多出来的这个转移点就是 $i - 1 \to i + 1$。
你也可以通过数学证明来理解这个结论。
既然可能的转移只有两种，那么直接考虑数据结构维护 DP 即可。这里用的是有交平衡树合并。
## 简单概括总结一下
1. 拿到一道题先分析它要考你什么，是最基本的必胜必败态分析，还是用奇技淫巧维护 SG 函数，又或是披着博弈论外壳的一道 Ad-hoc。
2. 对于必胜-必败态题目，其通常存在易于攻破的性质，即 DAG 图上真正“有用”，值得我们分析的转移边并不是那么多。我们只关心一个状态能不能转移到必败状态，并不关心图的具体形态。
3. 对于 Ad-hoc 类型的博弈论，站在游戏者的思维里分析是通用策略。注意及时的视角切换，总是从一方的角度考虑问题并不能一步得到答案，从三种（两个博弈者，以及旁观者的形式化视角）视角交替思考可以更快分析出正解。
最后简单放一张很适合放在博弈论博客里面（？）的插图吧！（其实是防伪标识）
