题解：P13345 [EGOI 2025] IMO

LightSpot · 2026-11-10 15:16:32 · 题解

按总分从小到大排序，考虑确定一部分成绩的值后，一个人可能的成绩在区间 [l_i,l_i+K \times x_i] 中，这里 l_i 是第 i 个人已经确定的成绩总和，x_i 是这个人还未确定分数的题目数量。于是限制可以转成相邻两个人的 r_{i-1} \le l_i 或 r_{i-1} < l_i，取不取等取决于两个人的编号大小。

没什么新的思路，我们考虑发现一点性质。设我们最后有 X=\sum x_i 项成绩没有公布，同时对于相邻的两个人总有 r_{i-1} \le l_i 成立，此时成绩区间的总长度取得最小值 KX+1，将其放缩到 KX，则显然 r_N 不低于这个值。而 r_N 的最大值不可能超过 MK，因此有 KX \le MK \Rightarrow X \le M。

据此我们设计一个这样的 DP：令 f_{i,j} 表示：按排名从高到低处理到第 i 名选手，且当前未公布的成绩总共有 j 项时，当前这个选手的 l_i 最大能是多少。接下来考虑如何转移。

假如处理到第 i 名选手时，前面已经隐藏了 j 项成绩，我们枚举当前选手隐藏 t 项成绩，并令该选手未隐藏的成绩之和为 l_i，容易得到可以转移的条件为：l_i + Kt \le f_{i-1,j} \Rightarrow l_i \le f_{i-1,j}-Kt。当然这里只考虑不等号取等的情况，不能取等的情况是类似的。

那么我们只需要考虑如下问题：从当前选手的 M 项成绩中，选取其中的 M-t 项，使得它们的和不超过 f_{i-1,j}-Kt 且该和尽可能大。假设我们已经求出这个最优值为 g_i(t,\lim)，则转移就可以写成：

不过直接做无论是求 f 还是 g，复杂度都是炸的，考虑优化。

考虑先把求 g 的复杂度压下来，我们发现 g_i(t,\lim) 的 \lim 这一维直接取满整个范围是劣完了的，稍微给它缩一个范围：\sum\limits_{j=0}^{M-1} a_{i-1,j} \ge l_{i-1} \ge r_{i} \ge \sum\limits_{j=0}^{M-1} a_{i,j}（注意这里 a_{i,j} 表示按总成绩排序后的从高到低第 i 个人的第 j 项成绩），即有 \sum\limits_{j=0}^{M-1} a_{i,j} \le l_{i-1} \le \sum\limits_{j=0}^{M-1} a_{i-1,j}。

因此求 g_i 只需从所有成绩都不隐藏开始，只考虑隐藏完成绩后总分仍然不小于 \sum\limits_{j=0}^{M-1} a_{i+1,j} 的情况进行转移，这样背包的第二维的总和就是 O(MK) 的了，对于求 g 部分的复杂度即为 O(MK \times M \times M)=O(M^3K)，当然可以用 bitset 优化转移来除一个 w。

接下来考虑如何求 f，直接求是 O(NM^2) 的，我们同样考虑稍微优化一下。根据类似地推导，我们可以得到 \sum\limits_{j=0}^{M-1} a_{i+1,j} + Kt \le l_i+Kt \le \sum\limits_{j=0}^{M-1} a_{i-1,j}，即 t \le \dfrac{\sum\limits_{j=0}^{M-1} a_{i-1,j} - a_{i+1,j}}{K}。将右侧对所有 i 求和，我们容易发现它是 O(M) 的，于是求 f 的总复杂度变为 O(NM+M^2)。

那么这道题就做到了 O(N\log N + NM+M^2 + \dfrac{M^3K}{w})，第一项来源于初始的排序。