CSP-S 2024 游记：旌旗十万斩阎罗

序

初赛题没做完，喜提 82pts 同年级最劣解。

Day -2

飞机落地 CKG，前往学校视察机房装修情况。

Day -1

上午打教练组的一套模拟赛。教练声称其为信心赛，题目非常简单。

于是被结论题和推式子题爆锤。喜提 200pts。同年级最劣解。

下午打 sk 的模板题比赛，发现自己不会荷马史诗。然后复习了数论和图论。做了 NOIP2024 充满了希望，1A。真是充满了希望。

诶诶诶怎么复习的都没考啊。

Day 1

上午补打边双连通分量，1A。不负众望地没考。

下午排队进考场。今年怎么有安检的，是为了防止把手机带入考场吗。

14:40 打完头文件之后开始看题。

T1 好奇怪，想二分但是感觉又不能二分。发现我们排序后，删掉的一定是较小的一串前缀，并且一定从小往大删，每次选择可以让自己被删掉的最小的一个发起攻击即可。于是设 f_i 表示首个 i 攻击后可以退场的，递推 g_i=\max(g_{i-1}+1,f_i)，找最后一个 g_i\leq n 即可。

14:50 开始写。

14:58 写完了，通过所有大样例。开 T2。

分加速度正负进行讨论，先找到每辆车经过的首个测速仪，能检测到一个车超速的测速仪根据加速度正负的不同，一定是一段前缀或后缀，二分即可求出。于是问题变为选择最少的点，使得每个线段都覆盖至少一个点。按右端点不降排序然后贪心即可。

15:05 开始写。

15:20 写完。发现样例错了。

15:25 分类讨论部分复制后修改不完全。修正后通过了所有样例。开 T3。

T3 有一个很显然的 dp，即 f_{i,j,0/1} 表示考虑到 i，上一个另外颜色的 a 值为 j，当前颜色是红色/蓝色的最大值。状态爆炸考虑优化。在状态转移写出来之后，立刻发现可以整体 dp，只需要支持全局加、全局 max、单点 check max 和单点查值。于是无脑上线段树维护第二维即可。一个 \log 的做法测极限数据，在本地只跑了 200ms，故不再考虑优化。赛后发现这个东西可以直接用数组维护，但不重要。

15:35 开始写。

15:58 写完。一遍通过所有样例。

16:00 上个厕所开始想 T4。

先考虑了 O(nm) 的做法，即对于一个固定状态询问。我们可以对于每个叶子判定其是否合法。对于擂主是自家的情况，判断是容易的；擂主是对方的情况，需要判断对面能不能上来一个能力值小于 R 的人。第一想法是设 f_i 表示 i 节点能上去的最小能力值，合并看起来很容易。于是得出一个 O(nm\log n) 的做法。

然后考虑优化。首先当加入一个人使得树的大小变化时，我们需要重构这棵树。每次新加进来一个人，等价于确定了一个叶子的取值，会更新一条链上的 f 值。对于一条原来的叶子到根的路径，将叶子编号挂在路径上每一个非自己擂主的点上。这些点中若有一个点非擂主变得不合法了，则其上的所有叶子都不合法，需要从答案中减去。注意到全过程中所有树的大小为 O(n) 级别，故动态维护这个过程即可做到 O(n\log n)。看起来很能通过。

这个过程看起来有点复杂，也想了很久。

16:50 开始写。

写到计算 f 的时候突然发现这个东西实际上是没法合并的。具体地，对于一个擂主的 f<R，由于可行的能力值不连续，所以合并时不能直接将 f 与 R 取 \max。此时我马上注意到 R 很小，于是直接修正为维护 f_{i,j}，其中 j 表示上来的人能力值为 j 是否可行。这样就可以合并了，不过一次合并的复杂度变为了 O(\log n)，也就是说复杂度退化至 O(n\log ^2n)。看起来很不能通过。

17:30 写完 O(nm\log n) 的部分，这里已经有 150 行了，决定先把这一部分调过。

17:55 调过上述部分，发现只能过 n\leq 500。于是继续写。

18:20 写完并调试通过了 O(n\log^2n) 的部分，此时代码接近 200 行。大样例全部正确且用时较小。不知道 CCF 数据能放过多少分。预期得分是 T=4 的 68pts，理论上也可通过 T=16，获得 76pts。

18:25 检查完文件名等细节。切回 windows 准备结束。

18:37 完成签字操作，首个离开考场。其实很想在单子上签一个“已阅”。

贴一张出来之后拍的宣传横幅。是橘子味的。

Day 2

上午重构了前三题的代码，在通过大样例后均在洛谷上通过（怎么重写还能多错大样例的）。

第四题不想写了。预期得分 100+100+100+x=300+x。怎么还是同年级最低分？

尾声

断头今日意如何？创业艰难百战多。

此去泉台招旧部，旌旗十万斩阎罗。

继往开来，再接再厉！