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

T1

枚举左端点，考虑怎么确定右端点。

首先要满足两个数字的位数一致，所以考虑先通过位数筛掉一些右端点。

注意到随着选择区间的增加，第一个数字的长度单调不增。

另外，选择的区间的总和的位数每增加一位，都需要增加很多选择的数字才可以。

对于同一个 $l$，最多连续大约 $6$ 个 $r$ 对应的最终位数是一致的。

也就是说，可能的右端点最多只有 $6$ 个，先二分找出可能的右端点区间（二分的根据是结果的位数），然后暴力枚举右端点判定。

T2

一开始，所有艺术家的可能作品集合都是 $1,2,\cdots,n$。

第一次操作后，划分为两个集合，集合内部每个艺术家的可能作品集合都一致，即所有集合内艺术家的作品都有可能是自己的作品。

第二次操作后，对于每个集合，再次根据本次的分组情况进行划分成两个集合。

一个集合划分之后如果大小变为 $1$，那么其就确定了。

T3

考虑二分答案，令答案为 $t$，首先保证二分上界不能超过最小区间的长度。

那么假设左端点为 $l$，右端点为 $r$，即 $r-l+1=t$。

答案将会是 $\sum\limits_{i=1}^n\max(0,L_i-l)+\max(0,r-R_i)$

上述式子改一下变为：
$$ \sum\limits_{i=1}^n(\max(0,L_i-l)+\max(0,l+t-1-R_i)) $$ 令 $U_i = R_i-t+1$，上式变为：
$$ \sum\limits_{i=1}^n(\max(0,L_i-l)+\max(0,l-U_i)) $$

$$ \sum\limits_{L_i \ge l}L_i-l + \sum\limits_{U_i \le l}l-U_i $$

从一开始，$l$ 不断增加，答案会先减少再上升。

考虑三分 $l$。

T4

实际上已知最终的顺序。

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

合法的前提是相邻后一项的最大成绩小于等于（能否等于得看 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})$，期望 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)$。