省选联考2023游记

day \(-n\sim -1\)

上课卷点数据结构和树形dp，虽然不是板题不会做，但是还是学会了一些小 trick。下课摆烂。

day \(0\)

摆了一天的烂，下午动员+板刷 zxy 游记，不过 pty 说的非常有道理，省选就是心态比赛，稳住心态就可以拿让人满意的分数。

day \(1\)

8：20左右

坐到了位置上，试了下键盘，好不习惯啊。

8：30

发密码，花 \(20min\) 理解了下题意：
t1区间覆盖问题，求覆盖了 \(x\) 的那一段大区间中有多少小区间的左端点在 \(x\) 左侧，有多少小区间的右端点在 \(x\) 的右侧
t3每个点的权值的权值可以自己用，也可以覆盖掉子树中的任意一个点的权值。
t2为选择一些关键点，删掉这些点之间的所有边后联通块数量不为 \(1\)，所有删除后的联通块中有且只有一个关键点，且联通块大小的最大值减最小值不得超过 \(K\)。

9：00

花了 \(10min\) 敲了一下t1，结果敲挂了，用了近一个小时才调出来，原来是排序排反了。

10：00

因为t3看起来比较可做，留到了最后。想了会t2，发现了个很容易发现的性质——一个边双要么全是关键点，要么只有 \(0/1\) 个关键点。因为记得不知道是谁在很久以前对我说过狭义圆方树是关于边双的（这句是假的，读者啥也不用管），想到了圆方树。但不知道怎么操作，放弃了，花半个小时敲完了暴力。

10：30

回头看t3，转化一下可以发现，令 \(s_u\) 表示子树 \(u\) 中填的数的集合，\(value_u\) 表示标记在点 \(u\) 的数的集合，每次将所有的 \(S_v(v\in son_u)\) 合并，再重复用 \(value_u\) 中的最大值替换掉 \(s_u\) 中的最小值，\(s_u\) 在上传时只保留 \(siz_u\) 个节点，可以用启发式实现，复杂度 $O(mn\log k\log n)，用权值线段树合并复杂度降为 \(O(mn\log n)\)。

12：40

写了一个半小时，最后启发式合并还是没过样例六，有点难受。稍微检查了一下文件名就下考了。

15：15

与群友讨论后发现，选出一个边双里面所有点后它要全部是割点才有可能贡献出块大小大于1的答案，也就是点双，所以直接上圆方树，把图变成树再做。