题解：P13345 [EGOI 2025] IMO

· · 题解

先求出最终的排名，那么挖掉一些位置之后每行的和有取值范围 [l_i,r_i]，其中 r_i=l_i+c_ik。令 ord_i 表示第 i 名的原始标号，那么要求 r_{i+1}\leq l_i-[ord_i>ord_{i+1}]。直接从上往下 dp，记录当前 l_i 的删除个数最大值。对于行内需要处理和为 x 选 y 个数是否合法，压成一个二进制数可以处理转移。值域大小是 mk，这样做的复杂度是 \mathcal O(nm^2k)。

上述做法的状态以值域为基，其大小为 mk，很不好优化。令 S_i 表示初始每个人总分数，可以看成数轴上初始有 n 个初始为单点的黑色区间 [S_i,S_i]。每次删除一个点会导致 [l_i,r_i] 长度 +k，而数轴的总长 \leq mk，因此答案 \leq m，尝试以此作为状态。那么最终 [l_i,r_i] 是以 S_i 开始拓展的线段，最多拓展到 [S_{i-1},S_{i+1}]。

处理 f_i 表示使得前面删 i 个点所需的最大 l_i。和为 x 选 y 个数是否合法中，x 只关心到 S_{i+1}-S_i。从 f\to f' 的转移考虑填表法，枚举 f_p 的转移，当前删除了 q 个，找到 \leq f_p-qk-[ord_i>ord_{i+1}] 的最大点作为 f_q，要求 \ge S_{i+1} 否则终止。对于每个 p 双指针找到这个转移点即可。

时间复杂度 \mathcal O(n\log n+nm+\frac{m^3k}{\omega})，因为中间可以 bitset 优化一下背包，因为只关心 01。寻找后继也可以直接在这个 bitset 上做。