题解：CF1483E Vabank

一文带你详细理解神秘鸡蛋做法。

注：这是放缩限制之后基于

\text{DP}

的确定性做法，若要看调参解法请移步其他题解。

首先是倍增，和其他题解一样。然后设当前不确定会输/赢钱的区间是

[L, R]

，即已经知道对于

x \in [1, L)

选

x

一定赢钱，对于

x \in (R, \infin]

选

x

一定输钱。

我们的目的是尽快把这个区间缩短至

0

的长度，显然直接二分是不行的，原因是补钱操作带来的开销巨大。

有性质：我们在分治过程中不会选择

> \frac{l + r}{2}

的

x

赌博。感性理解，如果赌输了，一来你损失的钱比赌

\frac{l + r}{2}

的要更多，二来你的区间长度大于原来的一半，这种最坏情况风险极大，完全不如选择中点。

因此我们先钦定每次只在

[l, \frac{l + r}{2}]

中间取。我们取

p

，则分析赌博过程，有性质如下：

最开始的时候你取两次

L - 1

，由于

R = 2^k, L = 2^{k - 1} + 1

，这个“可以任意取”的性质天然满足；又由于

p < \frac{l + r}{2}

，则我们可以归纳证明整个过程中都能任意取。

因此原问题等价于：

你有 $k$ 个鸡蛋，现在有 $t$ 秒倒计时，每一秒你可以选择扔一个鸡蛋或者补充一个鸡蛋，捡鸡蛋不耗时。如果鸡蛋不碎，你额外得到一个鸡蛋。问最大的 $x$ ，使得有 $x$ 层楼时你可以在 $t$ 秒倒计时内问出鸡蛋从那些楼层下落不会碎。

“额外得到一个鸡蛋”的限制不比原题目的限制宽松，这一点可以通过“可以任意取位置”性质以及

p \leq \frac{l + r}{2}

理解。

设

dp_{k, t}

表示上述问题的解，预处理后根据

dp

值询问即可。

文章操作