CF 444

Cocoly1990 · 2023-01-07 22:59:50 · 个人记录

A

比较套路的题。不难发现最多只取一条边，证明用反证法证明是容易的。

B

考虑枚举 a 来贪心，每次相当于把 b 右移 i 位来匹配 a_i，直接 bitset 优化即可，注意每次遍历要控制时间复杂度为 \operatorname{popcount}，否则会超时。

综合时间复杂度 \mathcal{O}(\frac{n^2}{\omega})。

C

大家都会珂朵莉树吧。注意到颜色段覆盖增加的端点数量是 m 级别的。考虑分块维护，若整块是相同颜色则一起处理，否则暴力重构，由于上述结论，因此复杂度为 \mathcal{O}(m\sqrt n)。

D

平衡规划，不超过 4 的字串个数不超过 4n 个。

因此，长度超过 \sqrt {4n} 的字串个数不超过 \sqrt {4n} 个。

暴力预处理大对小，大对大即可。

E

考虑二分答案，连上小于 x 的边，相同连通块内的点不能互相连通，猜了个结论，只要对于每个连通块的补的度数限制和 \geq 这个连通块的点数即存在合法方案，反之无，证明似乎也不困难。

然后发现这玩意根本不需要二分答案，直接顺序加边就好了。