比赛：CF2127 Div.1+2

· · 题解

CF2127

A

如果 a_i 为 0，等价于要求 \mathrm{mex}=\max，无解。

否则，等价于要求 \max=\min，则所有数都要相等才有解。

B

容易发现只朝一个方向走最优。

C

把 a_i 和 b_i 看作区间 [a_i,b_i] 或 [b_i,a_i]，

若存在两个区间有交，Ali 一直选择这两个区间即可，答案和原序列相同。

否则，Ali 选择两个距离最近的区间，然后后面一直选这两个。

D

首先必须是树才有解。

发现一个点连向对岸的点，必须在对岸构成一段区间，且这些区间两两的交 \le 1。

于是可以想到，若一个点的邻点中，\mathrm{deg} > 1 的点的数量 >2，则无解，因为 \mathrm{deg} > 1 的点一定要放在区间的端点。

然后除去邻点中度数大于 1 的点，剩下的点可以随意排列，乘上阶乘。

然后如果两岸都有 \mathrm{deg} > 1 的点，最后答案乘 2，因为可以把每个方案两岸同时翻转。否则翻转后和原来的方案等价。

最后答案还要乘 2，因为每个方案对岸可以互换。

Code

E

考虑自底向上填，发现点 u 的颜色若不确定，如果子树中有任意已经确定颜色的点，那么一定可以在子树中找到一个颜色作为点 u 的颜色，使得方案最优，且不会对更上层的节点产生影响。

否则，若整个子树都没颜色，我们放到最后再处理。

进行完初步确定后，如果整棵树都没颜色，全部设为 1 即可；否则，从上往下确定颜色，让没确定的节点颜色等于父亲节点的颜色。

用 set 启发式合并维护子树颜色即可。

Code