Codeforces Round 722 (Div. 2) ABCD 记录

· · 个人记录

A

容易注意到，将 a 升序排序后，相同值作为一整块，那么每一块选择自己整块加上前面块的其中一个元素，这样是最优的。

最后只有最小值不能被删除。

B

容易注意到，最多选择一个大于 0 的元素。

另外，如果选择的最大元素小于等于 0，那么所有非正数都可以选择。

现在只需要枚举哪个元素是唯一的正数（当然也可以没有正数）

C

考虑子树选完了，自己该怎么选。

（不一定）容易注意到，只有 l_u,r_u 是可能选择的。

D

考虑 f(n) 代表 n 个点的答案。

考虑第一个点与哪个数匹配，设其为 r。

容易注意到，除了在 [1,r] 里面的，所有线段长度都必须等于 r 。

另外，比 [1,r] 长度小的线段只能在 [n-r+1,r] 内部。

容易得到 [n-r+1,r] 不为 0 对应的 r 是一个区间。

另外，另一个结论：

假设一个整数 $d$，那么两个端点可以配对当且仅当其编号差为 $d$。 一个 $d$ 是好的当且仅当所有端点都可以被配对。 结论：$d$ 是好的当且仅当 $(2d-2) | n$。