随笔杂谈 | CSP-S 2024 复赛游记

day -1

退役前的最后一场 CSP-S。听说 kkk 今年可能不会提前公开选手代码，坏。

白天忙着组了一场模拟赛，晚上自己复习知识点。

重新理解了一下三种联通分量，然后熬夜到了两点。

组模板手速赛但是只有我打，大部分都打的很顺利。

LCA 写挂了，发现是忘记初始化 $dep_s=1$。之前也在这里挂过，当时没理解原因，这次好好想了一下发现是因为 $dep_0=0$，如果 $s$ 深度不设成 $1$ 的话就和 $0$ 点区分不开，跳的时候会跳错到 $0$。

线段树 2 写挂了，以为是懒标记的问题，调了半天，最后发现是把 add() 复制出来改成 mult() 时忘记修改函数内递归的函数名了，我说怎么退化成区间加了。其他部分都没问题，很好。

KMP 几乎不记得了，坏。重新看代码理解了一下，发现很好理解。

出发去考场。路上重新复习了一下三种联通分量和对应的 Tarjan 算法，看了一眼 Nim 游戏结论。最后就在复习数位 dp，然而直到进入考场都没完全理解。

由于准考证和行李之类的问题在考点大门和考场来回跑。

今年还是不让带零食。还有五分钟时进了考场。

位置还是在角落，斜对角就是一位特别强的学弟。

提前三分钟发卷，压缩包和 pdf 密码都一次性打对了，rp++。

敲了代码缺省，开 T1。前五分钟想复杂了，思路有些乱，想上数据结构。重新读题发现就这，很快就会了排序贪心的做法，决定先过掉 A 再开后面题。开写的时候注意到值域可以直接桶排，14:41 的时候过了所有样例。

开 T2，怎么是物理？发现超速区间很好推，显然转化成区间覆盖问题。第一问可以离线下来用前缀和来求区间内是否有摄像头，线性。第二问读完就想到了种树，给我一种按端点排序贪心很对的感觉，但是不太敢写。

想了二十分钟，第二问还是不知道怎么做，遂跳至 T3。读完题很有思路，马上就想到了 $dp_i$ 可以分成 $dp_{lst_i}$ 和 $[lst_i+1,i-1]$，后者用前缀和很可以维护，但唯独 $lst_i+1$ 这个点的贡献到处飞，很难搞。

想了一会不会搞这个点，但是觉得只要搞出来就可以 dp，开 T4 一眼不会，遂回到 T2。

虽然一开始贪心思路记反了，按左端点排序但是取了最右，过掉了小样例，遂开写，发现过不了第二个样例。

对样例调了一下发现贪心错了，想了一会想不到别的贪心，但发现如果按右端点排序两个样例都能过，遂改。改完之后过掉了所有样例，但发现 T 了。

于是优化掉了 vector，然后其他地方卡常了一下，同时确认了清空和边界之类的细节，大样例 1.7s 过了。此时 16:43，也就是花了两个小时。

回到 T3，然后思考了很久 $lst_i+1$ 这个点要怎么搞，甚至想过退化成记搜或者上个数据结构，想了大概半小时后灵光一闪发现了 $dp_i$ 和 $dp_{lst_i+1}$ 的结构是一样的，给状态加个不影响的条件就可以直接从 $dp_{lst_i+1}$ 转移了。

这样的话就很好写了，码码码，发现第二个样例没过，对着调了一会发现对 $dp_{i-1}$ 取 max 就能过，虽然当时不理解要如何解释，不过写上之后过掉了所有样例，此时 17:40，剩余不到 1h。

后面就很坐牢了，完全把题读懂花了一些时间，甚至不会朴素暴力，只会一个 $O(n^2logn)$ 的树上大模拟，加点时从叶子向上 vector 合并。感觉应该有很多分，遂开写。由于建树的时候写了类似动态开点线段树的写法，所以被如何计算是第几场比赛难住了好久。

最后五分钟的时候放弃了，无奈 puts("1")。最后两分钟检查了所有文操、注释、函数返回值（高一省选的时候就因为把 void 打成了 int 又没有返回值导致那题 CE 100->0）。

最后开了 checker 确认了一遍文件名和准考证号，铃响结束。

本次比赛遇到三位莫名其妙像熟人一样跟我搭话的，以及对面的大哥全程嘴里叼着笔，也许他不止一只，以及右边的大哥总感觉经常瞅我进度，也许被我压力到了（

过程中经常观察学弟的表情，看起来很轻松，以为被单调队列了。

出去后吃了点零食重启一下脑子，回去路上晕车但是刷洛谷讨论区。貌似机房其他人没有会 C 的，希望他们也能 1= 吧，rp++。

发现全机房只有我一个人考完就返校，其他人都回去睡觉了，愤愤。

先回机房吃了点面包和酸奶垫垫肚子，发现自测快开了，然后开始默写代码和写题解。默写的过程中发现我 T2 虽然已经很小心但还是有地方没处理好边界，最后效果相当于默认 $0$ 处有摄像头，一旦有车在 $0$ 位置超速而 $0$ 位置没有摄像头，答案就错了，寄。

当晚自测结果前三题都没挂，甚至第四题出民间数据之前在洛谷上还排到了 rk3，激动。

后续在多个平台自测均为 $300\text{pts}$，第二题也过掉除了我以外的所有 hack 数据。也许是因为卡掉我的情况算非常 corner case，所以非刻意构造的话很难出现，希望 CCF 也不要卡我。

中午敲了 $400$ 下电子木鱼，结果 CCF 连续诈骗两次，然后下午一赶到机房就听到了同学的祝贺。

$100+100+100+0=300\text{pts}$，达成三年 CSP-S 都没有挂分的成就。

虽然省排有些烂，但分数还不错，第四题还是黑题，还是很满意了。

希望 NOIP 可以继续发挥好，rp++。

update：今年 GD 高中生分数线居然要 $100\text{pts}$，并且刚好 $100\text{pts}$ 的还要求初赛 $\ge 61\text{pts}$，放以前想都不敢想。虽然我的初复赛都超线很多，但是机房同学好多卡线然后因为初赛被筛掉退役了的，好可惜。

本文原载于 reincarnatey.net，遵循 CC BY-NC-SA 4.0 协议，复制请保留原文出处。