省选联考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的答案，也就是点双，所以直接上圆方树，把图变成树再做。

Day $2$

可能是因为昨天考得还可以，自己也知道自己水平，没想去进队，今天进考场的时候还挺轻松的。

8：30

发密码了。还是一样的惯例，先理解题意。
t1两人博弈，求两人都采取最优策略后，谁会赢，最少步数为多少。
t2对于 A 所有的可取方案，求 A 和 B 相同的数的数量的最小值最大为多少。
t3求有多少完美序列和所有完美序列权值的最大值的和

9：00

因为觉得前两题可做，就放在了后面，稍微想了下t3，发现没有想法，写个搜索走了

9：30

开始想t2，性质 $A$ 很容易想，性质 $B$ 一眼是个环，即第二个人只有两种选数方案，但这有什么用呢，在场上罚坐了半个小时没有一点思路，只会写暴力+性质1，想到还有t1没写，果断写了，留两个小时去写t1。

11：00

开始想t1，两个人交替操作，求胜利者的最小操作步数，让人想起了这道题，该题正解是对抗搜索。虽然正解在考试这道题中复杂度不正确，但还是可以一用。于是有了一个感觉很对的暴力。分别考虑两个人谁最后是胜者，那么这个人就要尽量减少步数，另外一个人就要尽量增加步数，可以上对抗搜索，最后输出较小的步数即可。写了一个半小时，最后在样例二由于太慢跑不出来，卡死了。