Codeforces Round 908 (Div. 2) Editorial

__vector__ · 2023-11-25 20:54:22 · 个人记录

A

可以枚举所有可能的方案。

B

将所有 a_i 值相同的 i 组成一个连通块，那么需要两个连通块即可完成构造。

C

可以将操作进行逆转，并且逆转之后的情况是唯一的。

如果遇到循环就退出，循环节最长为 n。

D

首先降序排列 b，然后依次插入。

现在，试图设法让每次插入后答案都不变。

首先考虑插入位置左边，先假定插入的值小于等于左边的所有数，那么自然就能想到，只要插在第一个小于它的数左边，就能使答案不变。

双指针。

E

自然想到枚举 len。

问题是，len 的取值范围可能很大。

但是，注意 len 很大对应的是答案很可能为 0。

事实上，当 \sum {r_i} - \sum {l_i} \ge \sum n_i 时，答案一定为 0。

而 \sum n_i \le 10^5。

然后就可以枚举了。

至于每个 len 对应的答案，我的做法：

• 第一步，每个 multiset 都要选择 l_i 个，优选选择非 len 的数值，如果实在不行，再取数字 len。记录这一部分必须选择的数字 len 总数。
• 第二步，由于需要再从所有 multiset 中选择 len - \sum l_i 个数字，这一步需要统计所有 multiset 中第一步尚未选择且非 len 数值的总数（即优先选择，不会对答案产生影响的数字总数），据此计算出必须选择的数字 len 总数（最终答案）。

需要扫一遍预处理。