CSP 2025 游记

lx2009 · 2025-11-04 20:48:00 · 生活·游记

本来是不想写这篇游记的，但是这次经历使我留下深刻的印象，我认为对我本人亦部分人有教育意义。

考前打了若干场不知道是NOI Plus还是NOIP还是CSP难度的模拟赛，反正就是十分拉跨，连续考前两场没有写出第二题的满分代码，反正就是很难受，有点不安。

上午：

原来给自己定的目标是 2 个半小时写完普及组所有题目，没想到 1 个小时就完成了，玩了扫雷、小恐龙若干游戏。

中午：

随便吃了点午饭回酒店休息，然后被时光代理人控了半个小时，成功浪费了蛮多宝贵的午睡时间。

下午：

是杭师大仓前勤园机房。

其实很不想来小机房考，总感觉在大机房考更有利于我的发挥，可能是因为空间大小原因，也有可能是因为电脑速度原因。

不管怎么说，总归是要在这里考完。

监考员提前 2 分钟左右告诉密码，将所有文件先解压出来后不知道能不能开始考试了，好吧其实可以了。

开场通读四道题，第一题一看就是贪心，第二题图论，第三题怎么是字符串，我亲爱的动态规划呢！第四题没什么心情看，我知道以我的水平根本做不到第四题，甚至不会有时间去好好看一下第四题。

感觉第一题很简单，是不是类似于最小生成树的加边之类的思想，直接从大往小加呢？写完第一版，过不去小样例才发现假完了，哦哦，那是不是先假设 A 加入进去了，B要加入时与 A 发生冲突然后反悔贪心呢，哦哦哦，那我会了，又写挂了。痛定思痛，重新整理了一下思路，按最大值减去次小值排序，可以临项交换证明是最优的，大约于开考 1 小时通过大样例。

我愕然，在 2025 的考场上，我原定是要争取 300 分的，然而这第一题就写了一个小时，已经严重打乱了我的节奏，燥热的空气，超慢的机子，心中的慌乱，我……还能赢吗？

赶紧看第二题，觉得完全不可做，过了 3 分钟才发现 k\leq 10 那肯定是直接枚举了，啊！ 10^6 条边，开玩笑吗？又想了挺久突然醒悟我只需要对城市跑个最小生成树，把里面的边保留其他删掉就好了，这样就只有 10^4 条边了，哦哦，我再把边先排序好，是不是每次跑一遍最小生成树就好了？来不及细想，总感觉只能这么做了，写完第一版过不去大样例。已经过去两个小时了，难道我今年 200 分都拿不到吗，我不甘，突然发现乡镇的点编号给错了，改了后通过了大样例，也不管跑的速度怎么样，我只知道这是我能想出来的最好方法了。

第三题，一眼感觉是多次替换，那我还做个毛线，直接臆想只能做 1 次操作，发现求出最小修改区间，两边再形成前缀后缀关系，赶紧写了字符串哈希，先暴力然后再优化，通过了小样例，才发现确实只能做 1 次操作，中间把长度不相等判掉了，发现大样例一直过不去，做法假掉了？不可能！一致尝试各种哈希，比赛最后 6 分钟换了个 119 作 base 终于通过了所有大样例，毫无疑问，剩下时间我已经干不了什么事情了，结束了……

出来后感觉很不好，跟同学讨论做法发现第三题我的做法太劣了，后面不转化维护完全会T飞，哀。

洛谷估分：100+100+60+0

云斗估分：100+100+75+0

梦熊估分：100+100+50+0

其实我感觉第三题最多拿 40 分了，因为我用了快速幂自带一个 \log，哀！

实际出分：100+64+40+0……

其实我这次有如下几个原因导致失利，供参考：