CSP-S2026 游记

博客园 link

省流：题读错了。

坐标 SC，高二，应该是最后一次考 s 了吧，目标是 wc 线。

day -?

考了两场黄紫黑黑的模拟赛，获得了 eps 的手感。越临近 s 的考试发挥的越不好，有预感 s 可能会很差，于是前几天都特别紧张，觉都没睡好。

day0

由于学校是考场所以提前放了假，17:00 就美美回家了。回家之后一直在看杀戮尖塔农🐖的视频，来了一把被甜八弄死了 /fn，最后到 12 点终于去睡觉了。

day1

由于生物钟原因 8:30 就醒了，但还是睡了 8h 的，感觉十分精神。本身想复习一下但不知道为什么就打开了哔哩哔哩，觉得自己太颓废了于是又打开了杀戮尖塔，过了把力量战战士哥。上午就这么颓废完了。

小睡一会后整了杯咖啡，13:30 就去了考场。不难发现作为前后左右全部都是神犇，有点吓哭了。值得注意的是由于我上午清空了肠胃所以下午压力都还在不太大。开考前一个小时还是挺紧张的，可能也是因为之前考大考容易软脚，自己也没有考出过一个满意的成绩，学了那么多年甚至还只是一个绿勾，s 的 1= 也没有拿到过，去年差一分蓝勾更是十分神秘。

验证码延后了 5mins 于是美美打板子。由于害怕 ce 挂分所以全程用的 NOI Linux 写代码。先看 t1，不难发现肯定要选一段值域连续段，排序后双指针即可。然后看 t2，由于刚开考比较紧张，所以读了 10mins 才勉强理解。\(q\) 是 \(5 \times 10 ^ 5\) 大概率是要预处理答案，那么肯定要全源最短路，\(n\) 又只有 \(500\)，那么直接对每条地铁线做即可，对于查询 \((u, v)\) 直接枚举开始和最后面做的是哪班地铁即可，时间复杂度 \(O(m d ^ 2 + n ^ 3 + q d ^ 2)\)。大概 14:05 左右就写完了，两道题一共只花了 30mins，到这里我心态就比较放平了，毕竟没有出现什么前两道题磕死的情况，1= 是大概率了，但离目标 wc 线应该还是有距离。

值得一提的是，这是我第一次用 noi linux。我个人喜欢使用脚本一键测大样例，但是由于不熟悉我一直把 vscode 的 warning 看成我脚本 ce 了，然后又白白浪费了 20mins，真是神了。

然后看了下 t3 和 t4，此时我就把 t4 的题看错了，把要求的 \(\max_{i = 1} ^ n d(i)\) 看成了 \(\sum_{i = 1} ^ n d(i)\)，想了一下发现完全不可做，于是就去做 t3 了。t3 不难发现是一个充要条件计数，先打了一会表发现找不到规律，考虑直接去分析。假设 \(l_i\) 表示 \(i\) 最左边能一次跳到的位置，\(r_i\) 同理，那么最短的路径一定是贪心的一直走 \(r_i\)。如果有两条，那么就存在一个这样子的平行四边形：

其中 \(l_b = p \land r_a = p + 1\)，玩了一下这个就是充要条件，考虑对这个计数。可以考虑枚举 \(b\)，那么 \(p\) 和 \(p + 1\) 都是固定的，然后统计 \(r_{a} = p + 1\) 的方案数即可。考虑 \(a\) 和 \(b\) 还要向两边延申，分别用 \(pr_a\) 和 \(sf_b\) 表示，dp 做一遍即可。此时大概是 16:10，直接开写。写完之后发现除了两个小样例大样例全部挂完了，此时是 16:40，很无助，但发现多测大样例里面还有很多小样例，ccf 良心发现了。于是开始调，发现我的充要条件是对的，但是 \(pr\) 和 \(sf\) 计算有大问题，对于每个小样例，我的答案都大了，势必是哪里多了，大概又调到了 17:00，每个大样例里面比较小的样例全过了，但是那些很大又全死了，全部都是我的输出偏小，说明和之前的不同一个问题。这个时候有点慌了，因为 200+ 大概率是没有 wc 打的，而且 t4 我连 50pts 的暴力都不会（当然这是因为当时一直以为求的是 \(\sum_i d(i)\)）不如和 t3 死拼，而且万一 t3 最后一车人过呢？我可能一等都没有。先上了个厕所冷静一下，我的充要条件是对的，那应该不是我整个做法都假了，而是细节问题，果断写了个拍子，果然拍了个 hack 出来！分析一下发现还是 pr 和 sf 漏了一种 corner，改了一会，在 17:40 测了一下大样例终于过了，舒服。

然后就去打 t4 了。又想了一下，还是一点思路都没有，果断敲了 \(O(n 2 ^ n)\) 的暴力。写完了一直调到 18:10 发现还是一直错，然后再去读一遍题，这才发现题读错了！然后调了一下轻松过掉了小样例。想了一下正解，大概是二分答案，对于二分到 \(v\)，把所有叶子的 \(v\) 级祖先，提出来建虚树，那么只可能是一条虚树上 \((x, fa_x)\) 的链，但在原树是链的情况问题大得很，根本不可能有时间写的完 \(n ^ 2\) 的暴力，不如再弄个特殊性质走了算了。特殊性质写完已经 18:25 了。美美摆烂了。

出来之后碰到了 SCma，发现他 t3 没有调出来有点可惜。怎么我们机房的 t3 都没做出来前面的也没发挥好，怎么回事呢。感觉还是有点可惜，如果 t4 没有看错题能再拿不少分。晚上吃了烧烤打了台球到了很晚，玩得很开心。

day2

重新写了下代码，前三道没挂，但 t4 的特殊性质挂了，所以估分：100 + 100 + 100 + [15, 25]。