CSP2022游记

· · 个人记录

作为退役选手参加的第一场比赛

几乎没啥压力，在本校考，环境都很熟悉，但是密码输错好几次，感觉有点寄。

开 A，感觉不会；看 B，没看懂，CD不想看

于是集中精力想 A 题，发现两次预处理就好了，开写，写到一半发现不能 dfs，果然退役太久了，基本搜索都忘记了，于是快速改成 bfs，调了调就过样例了。

读懂 B 题之后感觉是比 A 简单的真正的送分题，权衡了一下是写 8 个 st 表还是两个线段树，考虑到前一天还打了一发线段树板子于是决定写线段树，调一调就过了。

开 C，秒了限制条件等价于出度都为 1，但是没想到哈希维护，而是一直感觉是对于点扫描线然后用一个数据结构维护，想了1h无果，转而写 60 分暴力，很快就调完了。

开 D，突然发现这是 csp，只有 4h，我一直当做 5h 在做，发现只有 1h 时间了，有点慌。仔细读完题之后发现 k\le 3，感觉就是一个弱智倍增预处理 dp 值，然后矩阵乘法合并。但是此时只有 45min 了，感觉写不完，于是没有追求的退役选手就果断决定写 76 分暴力，最后卡着点调完，甚至没时间加上 k=1 的计算 LCA 的送的 8 分。

出考场估分 100+100+60+68=328

然后发现 C 的复杂度写假了，痛失 10 分

结果在 infoj 上给我 C 放了 80 分，也不知道数据是怎么造的

出来一问，感觉全世界都 AK 了，至少也有 336，没上大众分的退役选手爬了。

upd：官方出分了，100+100+70+68=338，不会造数据可以不造，没必要这么恶心人