二分答案

我居然连二分答案都不会了。

决定思考一下啥时候能用二分答案。

• 最大值最小/最小值最大类问题

最常见的形式。

• 值域转换为 \(0/1\) 类问题

[AGC006D] Median Pyramid Hard

问题只与数的相对大小有关，可以把问题值域转化到 \(0/1\) 上可能会有更优的复杂度。

具体的，设答案为 \(x\)，那么把所有 \(\le x\) 的数变为 \(0\)，所有 \(>x\) 的数变为 \(1\)，最后算得答案为 \(0\) 说明答案小于等于 \(x\)，否则答案大于 \(x\)。

• 博弈类问题

一次国赛模拟赛考的，到现在其实还是很懵。

Alice 想要让值尽可能大，Bob 想让值尽可能小，可以任意时间结束游戏。

二分一个最终答案 \(x\)，那么把所有最终状态权值 \(\le x\) 的状态看作白色，所有最终状态权值 \(> x\) 的状态看作黑色。

那么问题就是检验每次 Alice 从白点走到黑点，Bob 从黑点走到白点，此时谁会胜的问题。

如果最后走到了白色的格子上，说明双方存在一种方案使得最终答案 \(\le x\)，否则存在一种方案使得最终答案 \(> x\)，于是就可以二分了。

• 函数变化量类

这个我真的没看懂，求大佬教教。

[ARC016D] 軍艦ゲーム

列出 DP 发现是有后效性的，但是所有的值只跟一个状态有关，并且式子里有 \(\min\)，没法直接用线性方程组等方式求出答案。

假设这个状态为 \(f_u\)。考虑二分答案，二分这个状态的值 \(f_u=A\)，然后根据 DP 式子求出 \(f_u\)，如果 \(f_u=A\)，那么说明这个 \(A\) 还可以更大，否则就不能更大。

还有一种写法是看 \(f_u\) 关于 \(A\) 的变化量，也就是把 \(f_u\) 看作 \(f_u=kA+b\)，如果 \(k=1\)，那么 \(A\) 可以更大，否则就应该更小。

这个真的不是很能理解，如果有大佬能研究明白求告诉我。并且这是好久之前考的题了，我也找不到当时的代码了，所以纯靠记忆瞎扯，如果更大更小反了麻烦告诉我。

一节课时间就想到了这么几个，欢迎补充。