| rank | solved | A | B | C | D | E | F | G | H | I | J | K | L |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 18 | 9 | O | O | O | O | O | O | O | O | . | . | . | O |
A
Solved by miaojie (00:15:47).
喵喵贪心。
B
Solved by XLor (00:16:03).
操作等价于一个环上的偏移量。
C
Solved by XLor (00:44:23, +1).
先判断顺时针和逆时针，再判断长度为 $8$ 和 $9$ 的关系。
D
Solved by XLor (03:28:58, +3).
对于 $n$ 个黑点，最多产生周长 $4n$，下界则是尽量全部凑在一起，考虑拼出一个近似的 $a \times b$ 的矩形（可能会有一些空缺），但是至少填上两条边，产生的周长是 $2(a+b)$，最多容纳 $ab$ 个黑点。
类似与上面的做法，将方案抠出来后背包 $DP$。
P.S. 可以直接 $O(n+m)$ 调整地构造。
E
Solved by miaojie (02:20:15, +2).
如果只有一个完美匹配，那么就是把权值排序后，两两配对。
现在要求两个不交的完美匹配，观察到最多只有 $4$ 元环或者 $6$ 元环。
F
Solved by ytriayggg (01:02:01, +2).
G
Solved by XLor (01:53:05, +4).
观察到每个点至多被扩展一次。
使用并查集维护连通性，并且维护每个块内尚未被扩展的点，这里使用一个链表可以实现 $O(1)$ 的拼接。
H
Solved by ytriayggg (03:57:59, +4).
注意到每次只会修改不同的一个位置，重载 std::sort 的比较函数，使用 ST 表进行比较。
P.S. 可以考虑笛卡尔树的结构，$O(n)$ 进行统计。
L
Solved by ytriayggg (00:03:59).
签到。