LCA NOIP模拟 2025.9.25

· · 个人记录

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）前一项的最大成绩。

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