本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-26 20:00:09

实际上已知最终的顺序。

考虑按照最终的顺序逐个扫描。

合法的前提是相邻后一项的最大成绩小于等于（能否等于得看 id）前一项的最大成绩。

$f_{i,j}$ 表示已经确定了前 $i$ 个选手的方案，总共隐藏 $j$ 题，此时最后一个人的最大的公开成绩。

可以粗略的估计，所有选手隐藏题目个数的总和不超过 $M$。

假设隐藏了 $M+1$ 个题目。

首先，初始情况下最高分减去最低分最多为 $M \cdot K$。

若隐藏了 $M+1$ 个问题，那么意味着中间的差值减少了 $(M+1)\cdot K$，无论如何都不能保证原来的顺序。

现在需要知道每个选手有哪些方案。

$g_{i,j,k}$：当前选手考虑了前 $i$ 道题，公开了 $j$ 个，此时公开总和为 $k$ 是否可行。

转移：逐个扫描题目：

• $g_{i+1,j+1,k+v_{i+1}} \leftarrow g_{i,j,k}$
• $g_{i+1,j,k}\leftarrow g_{i,j,k}$。

其中 $v_i$ 表示当前选手对于第 $i$ 题的分数。

暴力转移复杂度将会是 $O(m^3k)$ 的。

加上 bitset 优化后变为 $O(\frac{m^3k}{\omega})$ 。

对于 $f$ 本身的转移，需要枚举下一个人的公开成绩，以及公开题目个数。

那么 $f$ 的求解总复杂度将会是 $O(nm^3k)$。

总复杂度 $O(nm^3k+\frac{m^3k}{\omega}) = O(nm^3k)$，期望 72pts，irris 说开 O3 优化能过。

考虑哪些状态有效。

重定义状态 $g_{i,j,s}$ 表示当前选手考虑了前 $i$ 道题，公开了 $j$ 个，真实总和减去隐藏总和的值为 $s$ 是否可行。

令 $id$ 表示当前选手编号，注意到 $s \ge score_{id+1}$。

也就是说，$s \in [score_{id+1},score_{id}]$。

仅保留有效的 $s$，那么注意到所有选手的 $g$ 的有效状态数加起来仅有 $O(m^2\sum\limits_{i=1}^n(score_i-score_{i+1})) = O(m^3k)$，其中 $score_{n+1}$ 视为 $0$。

再分析一下 $f$ 此时的转移复杂度。

每一层分别加和，得到 $\sum\limits_{i=1}^n (score_i-score_{i+1})m^2 = O(m^3k)$。

再算上一开始的排序，总复杂度将是 $O(n\log n + m^3k)$。