题解：P12251 [科大国创杯初中组 2025] 抽卡【暂无数据】

Purslane · 2025-04-20 20:47:18 · 题解

Solution

来个拉格朗日插值优化 DP 的方法。现在的安徽小朋友越来越不容易了，一年一年的上强度。

阅读题面的时候一眼看到三个可：，非常有趣。

可能会有一些小朋友阅读这篇文章，所以我写的详细一些。

首先，考虑固定局面下小可可怎么取牌可以获得最大收益。

假设有一个集合 U=\{1,2,3,\cdots,2n\} 表示牌的编号（注意和牌上的值并不相通），小可可选取的牌的集合 C 是 U 的一个大小为 n 的子集。在这 \binom{2n}{n} 个子集中，我们需要选出合法的且代价最大的那一个。

为什么要强调“合法”呢？比如，小可可并不能选出前 n 张牌（n \ge 2），因为波特肯定会在第一张牌和第二张牌中选出一个。

我们断言：小可可取出的集合 C 合法，当且仅当 \forall 1 \le k \le n，C 中小于等于 2k 的牌的个数 \le k。使用数学归纳法容易证明。

那么不妨设小可可初始的牌放在 1，3，\cdots，2n-1。每一张牌可以移动到后面的任何一个位置，最终不能重叠。换句话说，小可可的最后一张牌可以在后两张牌中选取，倒数第二张排可以在后四张牌中选取，依次类推。

这样我们就会计算答案了——显然每一步都可以贪心。所以你开一个堆，从 n 到 1，每次往堆里面加入 2 个 a_i，并且取出堆顶。复杂度 O(m^n \times n \log n)。

这样也许可以拿到 24 分？看你常数怎么样了。拿到这档分的小朋友未来很有希望的：你有很强的分析问题的能力，和获得更高的分只差了经典技巧的积累，多做点题就能克服这一关了！

这类问题有一个经典的讨论：“二分”转 01。

设 f_i 表示，最终取出的 n 张牌中，有多少张排的大小 \ge i。答案显然就是 \sum_{i=1}^m f_i。根据期望的线性性，E(\sum_{i=1}^m f_i) = \sum_{i=1}^m E(f_i)，所以你想方设法算出 E(f_i)。

可以证明，f_i 等于：将 \ge i 的数看做 1，\le i 的数看做 0，执行上面贪心的流程得到的结果。

这么做的好处是什么呢？由于所有数要么是 0 要么是 1，我们只需要关心堆里面有多少个 1，而这样的状态数就比较少，可以进行 DP！（这里有点 DP 套 DP 的感觉了，和去年 T4 很像！）

假设我们需要求 f_x。设 dp_{i,j} 表示，执行了所有 i_0 \ge i 后，堆中有 j 个 1 的概率。最终状态是 dp_{1,j}，表示堆里面还剩了 j 个 1。这样假设加入了 k 个 1，小可可就取出了 k-j 个 1。我们的答案是 E(k-j)=E(k)-E(j)，其中 E(j) = \sum_j (j-\min\{j,i-1\}) dp_{i,j}，E(k) = E(\sum_{i=1}^n [a_i \ge x]) = \sum_{i=1}^n E([a_i \ge x]) = \sum_{i=1}^n p(a_i \ge x)，其中 p 表示概率。