题解：P13345 [EGOI 2025] IMO

· · 题解

实际上已知最终的顺序。

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

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

可以粗略的估计，所有选手隐藏题目个数的总和不超过 $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}

其中 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)。