2020 杭电多校训练第 8 场

rank solved A B C D E F G H I J K L
22 8 . O O O . O . O O . O O

B

Solved by ytriayggg (03:17:47).

DP,每个值使用 std::set 维护滑窗,使用线段树查询最值。

C

Solved by XLor (00:09:41).

叉积。

C

Solved by XLor (02:10:28).

LCT 维护出现时间的最大生成树,连边时删除环上最早出现的边。

F

Solved by XLor (00:33:38, +1).

H

Solved by miaojie (01:52:18, +1).

I

Solved by XLor (01:10:26).

枚举循环节长度,哈希去重。

K

Solved by ytriayggg (02:24:40, +1).

一个结论,$x \oplus y$ 能被线性基表示当且仅当 $x$ 和 $y$ 使用线性基消去后相等,然后 KMP 匹配即可。

L

Solved by XLor (04:58:08, +3).

记 $dp(u,i)$ 表示子树 $u$ 完成,利用从祖先传下来的值 $i$ 时最小操作次数。

转移时,对于合法区间,枚举子树求和,对于非法区间取合法区间最小值 $+1$。