博弈小结

感觉各种让我推策略的题目都不太会。一点思路都没有。所以记录一下。

这种题目一般和贪心或者 dp 结合，也有时候会跟 sg 函数的博弈论相关。

P3554 [POI2013] LUK-Triumphal arch

很久没有自己做出来带点博弈策略的题目了。虽然这道题真的不难。

先考虑二分。$k$ 为每次可以选的点数。B 每次只会往深的地方走，所以每次染色只往当前的子树中染肯定不劣。令 $f_i$ 表示 $i$ 的祖先至少要往 $i$ 的子树中额外染 $f_i$ 个点的颜色。发现如果 A 获胜一定要把子树全部染完，必须有 $f_1=0$。

分析一下有转移 $f_x=k-\sum1+\max (f_y,0)$。复杂度 $O(n\log n)$。

CF725F Family Photos

第一步都想错了，警戒！

考虑一个严格弱的问题：一堆照片只有一张的情况，有贪心策略两个人按 $a_i+b_i$ 轮流取。

从直接代数的角度上理解，如果 $a_i+b_i\ge a_j+b_j$，则有 $a_i-b_j\ge a_j-b_i$，对后手同理，先取 $i$ 一定不劣。

从更巧妙的构造上来说，把每张照片变成 $(\dfrac{a_i+b_i}{2},\dfrac{a_i+b_i}{2})$，而开始之前先把所有照片的代价加上 $\dfrac{a_i-b_i}{2}$，这样先后手取之后贡献不变，而贪心策略也就很直观了。

回到原来的问题。考虑 $a_{i,1}+b_{i,1}\le a_{i,2}+b_{i,2}$，第一张照片如果本来就要在第二张照片前面取，那么不用管栈的限制。否则：

• 如果 $a_{i,1}\le b_{i,2}$ 且 $b_{i,1}\le a_{i,2}$，则两个人都不取这个。
• 如果 $a_{i,1}\ge b_{i,2}$，则 A 取上面的。
• 如果 $b_{i,1}\ge a_{i,2}$，则 B 取上面的。

排序即可。复杂度 $O(n\log n)$。

小结

这种先手后手问题的策略大概率是严格对称且优雅简洁的。

对称可以理解为先手取完以后后手就变成了先手，不会出现什么“按差值排序一个取最大一个取最小”，因为也要考虑两者相互干扰的情况。

优雅在于不需要管 $\ge$ 还是 $>$，细节不是重点。

贪心策略还是要多积累。