题解：CF1483E Vabank

Felix72 · 2025-11-12 15:35:27 · 题解

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

注：这是放缩限制之后基于 \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，则分析赌博过程，有性质如下：

• 如果赢钱，则下一次可以任选 [p + 1, R] 中的一个位置赌博；
• 如果输钱，则我们通过询问 L - 1 补一次钱，下一次可以任选 [L, p - 1] 中的一个位置赌博。

最开始的时候你取两次 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 值询问即可。