231004.md

2023/10/04 模拟赛 总结

时间安排

07:40 - 08:20

看题，写 A,B，感觉会 C。

08:20 - 08:40

写 C 暴力。

08:40 - 09:10

写换根部分，思考怎么不用平衡树。

09:10 - 10:10

写平衡树，调代码。拍 C。

10:10 - 10:20

写 D 暴力。

10:20 - 10:40

拍 A,B。

10:40 - 11:20

写 D 40分。

11:20 - 11:40

发呆。

总结反思

大愚若智。

交题前检查数据类型。

数据结构注意常数和边界。

题解

A.

暴力 dp。

B.

对质因数大小根号分治，状压。

C.

策略是不断往中间走，然后轮流拿最大子树。

路径权值可以换根。排名分别为奇偶的元素和可以用平衡树维护，但是太笨比了。发现每次最多删两个，对每个点奇偶前缀和。

D.

暴力思路是线段树分治后带线段树上二分和撤销。

但是空间时间都炸了。换成平衡树维护连续白色段可过。

std 是单侧递归线段树，就是 pushup 的时候暴力查询，但是只递归一侧。