CSP-S 2024 游记

第一个 1h 在乱写，最后一个 1h 在疯狂改答案。最后 98.5，虽然没用，但是就当是信心赛。

晚上体锻，有人跑道上排练校运会入场式。

排练的老师拿麦大喊：“操场上踢球的同学请马上离开！”

我们转移阵地，发现学弟那边还在场上。

“幸好我们是玩飞盘的。”

不用打模拟赛，自行复习爽。

翻了翻考纲发现自己一堆板子忘了，所以只好开始补板子。被自己两年前写的丑长慢板子给震撼到了（比如 100 多行的线段树1），忍不住决定要顺便重写代码。板子有点多，直接来吧！以颜色为第一维、字典序为第二维排序，直接开写！

但是早上没睡醒，直接在【模板】栈 和 【模板】线性筛素数 各 WA 了两发，然后心态直接爆炸，何以 CSP？

好在后面复习板子还算顺利，还发现了一些新的板子，也一并补上。下午看 Tarjan 算法，分不清强连通分量/点双/边双的板子，怀疑自己点双假了。听 yhd 说 qoj 模板赛的数据比较强，扔上去测居然是对的，不管了。

看一下提交记录，自己新写的板子不知道比原来的板子慢到哪里去了。逐个卡卡卡常常常。

晚上回到机房转了一圈，好像有人已经开始调试不知道几个 G 的大模拟了（？）8:00 到 9:00 踢球，点球大战太精彩了，跌宕起伏！最后剩下一堆 math & string 的板子，第二天再弄。

继续推板子。重学了学过的数学和 KMP、manacher、AC 自动机。SAM 和 PAM CSP 先不考虑。

下午教练把所有人聚集到一起，看了 “CCF 关于严明考场纪律的通知”。里面列举了一些朴素作弊（偷窥）方式：

然后注释内暴戾语言不仅禁赛三年，还要通知到校长和教育局了？

接着是每年一度传统节目，经典 how to die 环节：

下午试机，考场门口就看到去年写压缩包密码的黑板竟然还没有擦。座位在机房最里面的一个角落，挺不错的。晚上跑路回家摆烂睡觉。

不存在的。

上午看了去年的几道题，还是没写 T3 大模拟。恳求今年不出大模拟。下午先回一趟机房，充分发挥主场优势。听说 J 组题目红黄绿蓝，想起去年 S 死磕 T2 失败只有 100+，慌。洗把脸冷静，进考场准备。

惯例提前 2min 给出压缩包和 pdf 密码，提前 2min 结束。第一次 CSP 一遍敲对验证码，舒服了。T1 读完题发现纯无脑签到题，10min 不到写完测过，这时才发现好像整个机房的人敲键盘都特别用力，同一张桌子的人互相影响。矿泉水瓶一直在晃。T2 读题，匀加速直线运动？高一物理专业对口，优势在我！居然还提供公式说明。马上知道每辆车不合法的一定是段区间，$v_t^2-v_0^2=2as$ 即可解出区间长度。剩下的是典，区间右端点从小到大排序后直接扫一遍贪心做。分类讨论没有预想中的繁琐，简单调一下就过了大样例。此时应该 1h 不左右。

本来打算直接跳 T3 看 T4，结果 T4 题面太长，一会儿才读懂，完全没有思路，回过头开 T3，很快想出一个假做法，花 30min 写完代码后直接就被样例1 叉掉了。不会做！怎么办！急急急！考虑 50pts 的部分分，先搞一个 $O(n^2)$ 的 dp 出来，暴力 dp 状态不够就多设几维。发现记 $dp_{i,j,k}$ 表示对前缀 $[1,i]$，离 $i$ 最近的同色/异色点分别为 $j,k$ 的答案。考虑转移时发现 $j,k$ 中必有一个是 $i-1$，可以压掉一维，记 $dp_{i,j,0/1}$ 表示 $[1,i]$，$i$ 和 $i-1$ 是否同色，最近的异色/同色点为 $j$。分别做 $0/1$ 的转移，讨论 $j$ 是否为 $i-2$，前缀和优化之就能做出 $O(n^2)$，马上写出来，细节很多所以一直在调。调出来只剩 2h 不到。考虑正解，发现自己完全不会优化状态，也想不到有什么 dp 的神秘做法。瞪了一段时间发现一个结论，觉得是除了一两个特殊位置从全局最大值转移过来，其它地方的 dp 值都是直接继承或全局加点什么东西，可以上线段树。线段树写得很奇怪，担心调不出来，终于在大概 17:45 的时候通过了大样例。

T4 还是不会一点，骗不到什么分，干脆直接不写了，重新测了前三题的代码，可惜没有放到虚拟机上测一遍。16:28 准时离场，期望 $100+100+100+0=300$。

发现 T4 yhd、yinhee 和 zlt 好像都没完全写出来。大家也是精准预言难度橙绿蓝黑了。

感觉大众分 300 左右，唯一能希望的就是不要挂分。

回到家 Q 群 zlt 一下开出 T1 原 CF903C，怎么题解全是众数啊，不懂。

不知道还能打几次 CSP。希望能没有遗憾。

没有代码所以还没自测，其它人记忆力惊人，直接重现考场代码。但是晚上发现自己 T3 结论假了，不好，但是过了大样例，相信 CCF 的数据！

$13:00\to17:30$【成绩单未上传？】

出分了。$100+100+60+0=260$，被一车学弟杀穿了。T3 线段树挂成 $60$ 了，呜呜呜（记得考前有人说 CCF 评测机 1s 1e9，谁说 CCF 评测机跑得快的）。跟别人讨论发现自己 T3 最开始的做法改改就对了（其实就是把两个 $lst_i$ 改成 $lst_i+1$），还是线性的。

感觉 $7$ 级勾要没了，不是很爽，但是比去年还是有很大的进步的。