CSP-S 2025 游记

· · 生活·游记

（怎么这么迟才写游记（））

前置 CSP 2025 训练记

重复内容就不写了，直接快进到考试日。

2025-11-1

本来计划上午多睡一会的，但还是很早就醒了。晚睡早期，很坏了。

没看普及组的题，不太想影响心态。摆了快一上午后去看板子，复习了刚学的几个字符串算法。
走之前又看了遍扩展欧几里得和线性预处理逆元。感觉每次考前都会看但还是会记不住，心里十分没底。
拿了某提神功能性饮料和吉祥物。
按以往经验考场会很热，虽然已经下过雪了但考虑外面温度不是很低，从门口到考场那段路跑两步也不会怎么冷，于是严肃决定短袖加外套加一层裤子，等到了考场把拉链拉开披着就好了。
感觉省会选手在考试上有好有坏，不用提前走再去适应环境，但也少了很多参赛体验。尤其我这样弱省弱校的，一个人去考场然后由一个人离开。
sad，严肃怀念！

严肃前往考场，发现是之前没去过的一边。进考场前习惯性的还是把带的喝的的外包装皮撕了。大约提前十五分钟进入考场。签到后看了一圈编号发现在第一排，和老师教学面对面 QAQ。发现并没有凳子，询问后先把老师座位的椅子搬走了。（）
老师和同学一样坐没有靠背的小板凳好评（bushi）
感觉考场以前的 Windows 系统安全检测过于耗时，每次编译都要等好久安全检测。于是举手换了 Linux 系统，感觉在 Linux 系统下还是安心一点。然后发现日常没有下发的试题，于是再次举手找老师考题面。
（我牌子呢？（））

文件结构和解压密码的 ppt 还是普及组的，试了下发现确实无法解压于是先去建了文件夹敲了缺省源。键盘好难用！有几个建根本不回弹！差评！
又过了几分钟才拿到密码 #Ren5Jie4Di4Ling5%，然后还是不对（）又过了几分钟才说没有最前面的 # 号，于是开考八分钟后才用正确的解压密码 Ren5Jie4Di4Ling5% 拿到试题。
注意到 T3 不同寻常的空间限制，注意到评测机换新 CPU 了（而且内存超大），但希望不要是缩过缸的（）

看了眼 T1 感觉就很贪心，直接每个人都选最大值，此时可能有一个集合人数超标。
把这个超标集合的人都按第一志愿和第二志愿的差升序排序，从小到大把人踢到第二志愿，直到这个超标集合的人数合法。
由于保证 n 是偶数，于是不可能有两个集合同时超标。由于调整后一开始超标的集合还剩 \frac{n}{2} 个人，于是另外的两个集合也不可能超标。
于是迅速开始实现，敲完后顺利过测全部样例。考虑大样例也可能测不出问题，又反复读了好几遍代码的逻辑确认和思路完全一致。大约半小时时决的没有什么问题。

备份了下代码后继续往后看。 读了下 T2，感觉只会最暴力的 $O(2^k m \log m)$ 做法。考虑枚举城市化改造那些乡村，将每个乡镇拆为两个点。对于每个乡镇，题目中给定的新增边连向第一个点，再加一条由第一个点连向第二个点的边，边权为城市化改造费用。 发现 $k \le 10$，感觉很极限。想了一会也不知道怎么做，看了下数据范围认为有希望通过 $1$ 到 $8$ 点。前四个点过于板了（） 猜测特殊性质 A 直接钦定城市化每个乡镇即可，但并没有想到证明。 又想了一下认为似乎可以 dfs 的过程中加边后直接跑一遍最小生成树，这样每次时间复杂度似乎是 $O(n \log n)$ 的，于是总时间复杂度 $O(m \log m + 2^k n \log n)$，似乎能过。但又想了一下感觉正确性并不显然。决定先往后看。 看 T3，发现是字符串！复习到点上了（bushi） 想了一下发现可以哈希做到 $O(n \cdot L_2)$。 又看了 T4，就很计数就很 dp。 我恨计数（）不行！还是得面对啊 QAQ！ （考虑前两天刚独立做完两道很长时间以来一直认为非常难的 dp 计数，信心倍增（bushi）） 看数据范围感觉就很 $O(n^3)$（bushi） 草稿纸上列了下每题的预期分数和时间复杂度，想了下感觉 T3 最有思路，决定再想一会 T3。感觉很像字典树，感觉空间限制的提示也很明显。但想了很久都没有思路，于是转而想了一会特殊性质。感觉特殊性质 A 似乎也没有什么想法，特殊性质 B 想到了一种奇妙的统计 b 的位置的插值的方法，于是预期得分 $50$。 认为应该开始实现了 ，想了下决定先实现 T3。 刚开始实现感觉很顺利，认为一个半小时时可以实现出来。但随后感觉截取的思路很乱于是在草稿纸上理了一下思路。 整理完后我感觉思路十分清晰，但此时已经一个小时二十多分钟，我决定在两个小时之前一定要实现完。 写完匹配替换后跑不过样例，排查了一会决定输出替换过程的哈希值，发现最开始的初始值就很错，应该是 $t$ 的哈希值有问题，也输出了一下发现显然，又看了一下发现是计算时把 ```h[j]=(h[j-1]*B+t[j]-'a'+7)%P``` 写成了 ```h[j]=(h[j]*B+t[j]-'a'+7)%P```（）糖丸！ 改完后发现还是不对，继续排查发现替换后的值还是很怪。 此时已经快两个小时了，我有点慌。重写在草稿纸上梳理思路，发现之前的式子竟然边界情况会越界。 重新梳理式子，看见已经到达两个小时的时间，我变得很慌。 我想起 NOIP2024，当时面对 NOIP 2024 T1 时的我就是这样。那依旧是我至今挥之不去的阴影。 我告诉自己我已经通过了 T1，但那 T1 思路和实现让我心里还是很没有底。我不敢确保我通过了 T1，我认为大样例极大概率测不出 T1 的 bug。 我告诉我自己你是一个弱省的高中生，你有参与正赛的资格。只要不爆零，几乎就一定能进 NOIP。 但我想赢，我想去 NOIWC。即使身处弱省已经有很大优势了，但我不敢赌在我前面的人都不报名。我没有 syx 那么好的运气，只考普及组 120 就进 NOIWC。我不想擦线。我想再考高一点，我想进前五，我想进全国线。 我没有遵守自己的时间约定。 我用几个确切的数作为例子辅助我写式子，重新写完式子后我继续实现。 我严肃决定在两个半小时前实现完，要是没有写完就还是先写另外两题吧。 我感到手在发抖，我感到心口不规律的急速跳动，我感到呼吸不顺。 这是...躯体化吗？ 我不知道，我甚至想举手让老师打 120。但想去 NOIWC 的心将我的手死死的按在了键盘上。 我会赢吗？我不知道。 好在最后经过无数遍检查的式子是正确的，我在两个小时二十多分钟的时候通过了大样例。 我注意到不保证 $\left | t \right |$ 相同，我犹豫了。我怕多写多错，我想我的双模哈希应该不会受此影响，于是我没有写特判。 我依旧没有遵守自己的时间约定，我决定开始写特殊性质 B。 写了十几分钟后我意识到我的思路十分混乱。身体的感觉愈发强烈。我猛猛的喝了几口某功能性饮料。 好热，明明已经穿的这么薄了，明明已经拉开拉链了... 我能活到考试结束吗？ 我决定放弃 T3，以 25 分的预期结束。此时已经两小时四十多分钟。 非常失败的策略。 我调整了一下座位和桌面的物品，使得我即使晕倒了，也不至于磕伤。 我决定实现 T2。我先实现了一下最小生成树，但样例似乎没有给 $k=0$，于是我手搓了一下检验。之后仔细梳理了一下 dfs 过程中加边和删边以及拆点的过程。写了特殊性质 A 的特判，通过了样例。此时认为预期得分 $[12, 48]$ 分。而这道题只用了不到半个小时。 写 T4 想了一下直接 dfs 似乎会达到 $n^n$ 而不是 $n!$，我又慌了。我想起一个枚举全排列的函数，但我忘了它怎么拼写。但眼下我也没有其它事做，于是还是开写。然后我测试了 $n=10$ 发现它跑得飞快。 我看了下特殊性质，我认为 $m=1$、$m=n$ 和特殊性质 A 似乎会好做一些，而特殊性质 B 不知道怎么处理。于是写了个分类。 想了一下认为特殊性质 A 乎就是 $n!$，光速实现后发现错了。打开样例分析了一会发现 $c$ 居然可以等于 $0$，想了一会发没有任何思路，但对于 $m=n$ 如果存在一个人 $c_{i}=0$ 那么就没有合法方案，于是就特判。 于是预期 $12$ 分。 此时仅剩余不到二十分钟，我决定开始检查。反复核对了文件名和输入输出，检查没有输出调试信息。然后指着题面和代码检查空间有没有开够和代码逻辑。发现 T1 的 $maxn$ 是 $1$ 开头的，而一眼看到题面中有个 $2 \cdot 10^4$ 于是火速将 $1$ 改成 $3$。 我来不及编译检查了。 我彻底慌了。 Windows 的收卷似乎是自行拖拽到内网的上传程序自行上传，而 Linux 需要拿 U 盘拷。 看他们一个一个的到老师电脑面前核对收取的文件是否正确，我简单的估了一下分。$[0, 100] + [12, 48] + 25 + 12$ = [49, 185]。 我感到一阵眩晕。 出考场后我看着那天空，习惯性的拍了几张照片。 走着走着决定发给 [CASCwty](https://www.luogu.com.cn/user/761444) ，他或许没有体会过时差呢。 他告诉我说“T1想了两个小时，T2差一点做完，T3不会，T4暴力没救了”。 我不相信，毕竟[当时](https://www.luogu.com.cn/article/84jh9kt2)拿到 T2 我至今依旧不会，而他当时就会形式化证明了。 我看到某群里在讨论 T1，我简单想了下认为我 T1 假了。 我瞬间玉玉了。 然后又过了一会自行回想了一下证明过程发现没有假。 我想了一会 T2，[CASCwty](https://www.luogu.com.cn/user/761444) 告诉我“应该要状压选的乡村，然后首先对原来的城市跑一遍最小生成树，跑完之后把最小生成树和乡村加进来的边再跑一次最小生成树就ok了，套状压复杂度感觉没太大问题”。我想了一会认为很有道理。 又想了一下“特殊性质A和这个做法应该是一样的道理。对于原图跑一边最小生成树，然后再加入所有新边和新点。由于所有新点点权都是0，且都有一条边权为0的边相连，就首先保证了答案不会更劣。然后让答案更优我觉得和你这个做法似乎是一样的道理。” 后来我又想了一下我似乎忘记了最小生成树加点加边后原先不选的边之后也不会选到这一性质了。 我发现我亲手否掉了 T2 的正解。 我亲自藏送了自己的 CPS-S 2025。 晚上找 whk 同学讲题，讲到嗓子干疼也讲不通一点。$\sum$ 这个符号怎么举例都讲不通。后来用 OI 思想浅浅讲了一下，一维的数格子好像讲通了，但二维就又讲不通了。$\sum_{i = 1}^{i \le n} i = \frac{(1 + n) \cdot n}{2}$ 的证明更是讲不通一点。自闭！ 似乎理解为什么枚举法要在大纲中单列出一条了。 ## 2025-11-05 看到 [__Segment_Tree__](https://www.luogu.com.cn/user/748015) 在犇犇发分数后迅速登了一下系统，发现改 URL 后查不到。于是翻讨论区获取了用申诉页面查分的方式。 （感觉现在查分的方式越来越怪了） $100 + 56 + 30 + 12 = 198

T3 多 5 分，T2 意识到是之前预期的时候漏算了两个点。
没有挂分，甚至反向挂了 5 分。
但我高兴不起来。

如果还有机会给学弟学妹们讲单调队列，还会哭吗？
还会有人愿意听我讲吗？

2025-11-07

看到了 CASCwty 的 [CSP2025] CSP-S2025 游记 & 初中OI回忆录。有一种说不出的难过。

看到了 __Segment_Tree__ 在犇犇发的排名，如此排名或许可以在 NOIWC 见到他。

结尾写了很多，又删了很多。最终也就不知道怎么写了。
或许这只是一篇永远没有人关注的游记。
他记录着，我曾来过。

我常常追忆过去。

我爱OI，我恨OI。

希望大家永远记得我。