专栏文章

CSP-S 2025 游记

cchuazen
生活·游记参与者 2已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mineujvb
此快照首次捕获于
2025/12/02 01:15
3 个月前
此快照最后确认于
2025/12/02 01:15
3 个月前
查看原文
今天是 1111 月 22 日星期日。
刷 luogu 时无意间看见 CSP 游记征稿贴；
点进去看了发现挺有意思的——
于是开始尝试写一篇游记啦。

2025 年 10 月 23 日，周四

照例下午有两个小时的校本课。我们 OIer 自然是在机房边打题边聊天。
“chuazen，你怎么还不停课啊，看我俩每天在机房打题目多好。”MengShang 说。
“啧，我文化课怎么样你又不是不知道。最后一周再停啦。”
s_mayunfeng 凑了过来，“到时候打印停课申请书的时候记得叫上我！”
“好。”
晚上又是一场模拟赛。机房换成 Linux 系统之后只能用 Codeblocks 了，没看到 Dev-C++ 的蓝框框总感觉别扭。
不过还好，做出了 T1，胡出了 T2，暴力了 T3。不过在机房里排行不高就是了。
“Lizeh，我要写停课申请书。”Lizeh 是我们竞赛教练之一。
没想到申请书还没有现成的模板，要自己按以前的版本打字。
“停课……10 月 27 日至 11 月 1 日……尽量不影响文化课成绩……”
ZJ 刚降温。出了机房还能感到阵阵凉意。s_mayunfeng 还在打字，我便趁着月光和北风，悄悄地溜出去了。
高二了，是该冲最后一把了。

2025 年 10 月 24 日，周五

今天是找各科任课老师签名的一天。大三门和选考三门都有课，所以签字比较方便。
“你停课没问题的。”“我对你还是有信心的。”“停课？……好。”
s_mayunfeng 跟在我后面，他就没这么幸运了。老师或多或少体现出了一点不满和怀疑。
“管它呢，反正周末作业不用写啦。”回去的路上，我笑着跟 s_mayunfeng 说。
是啊，看似只停了一周，其实还附带两个周末。
晚自习也不可能呆在教室做作业了，直接溜去机房开始复习。
从哪开始呢？唔……那就从任务计划开始吧。

2025 年 10 月 26 日，周日

做了两天的收藏题目，感觉收益不大。
点击题目，一眼不会；点击题解，知道结论；理解结论，一个式子就没了……
这……除了通过量增加也没什么别的收益了吧。
今天集训，上午是金牌选手讲课，讲的数学相关知识。前面 exgcd、逆元什么的我还能应付一下，后来直接蹦到积性函数、卷积和各种筛子去了。直接掉线，开始打题。
下午有一套模拟赛。没想到老师这次直接搬了 MX 昨天的试题。罢了，做完 T1 其他的拿个部分分就走吧。排名依旧荡在中游。
晚上回家，发现新出了个 K-D Tree 的模板。我好像寒假刚自学过来着。试着抢篇题解。
窗帘外的世界应该很美丽吧，因为回家路上看到天气很好。初五的月亮应该是贴在天边，朦朦胧胧的，能和群星打成一片。
不过窗帘拉上之后什么也看不见了。陪伴我的，只有转了一圈又一圈的分针，和不断 WA 的模板题。

2025 年 10 月 27 日，周一

停课第一天。
早上机房格外热闹。全体高二 OIer 和大部分高一生都选择在最后一周停课。
闹哄哄的机房似乎不是个调代码的好地方。我搬到了走廊上。那里也是我接下来几天常去的地方。
周一的校园看着似乎比较冷清，像是教学楼没从周末的懒觉中睡醒。窗台投进的阳光好奇地看着我，但被冷风摧残得连暖意都不剩下。
上第二节课的时候我终于过了这道题。其余时间在编辑 K-D Tree 的文章。以前对 Markdown 和 LaTeX 的使用都不规范，逐字改跟调代码一样难受。
第二节课下，抽空去参加了升旗仪式。班里同学排队的时候还是那么欢乐，sky 在台上指挥还是那么从容，ypj 在主持升旗仪式还是那么古板……
一切都没变嘛。但又怎么可能变呢？仅仅因为我停课吗？
后面回到机房又开始思考做什么题的问题。噢，暑假集训时候笔记还没补过。MX 那边上了两期课，都没怎么吸收。
高阶树状数组……树套树……可持久化文艺平衡树……怎么一上来就是这种毒瘤数据结构啊……
做了个《上帝造题的七分钟》，感觉燃尽了。
往后翻了几页笔记，发现有数论模块。Lucas,CRT,BSGS……我怎么什么都不会啊。
“这又不考，你做那些干什么。”MengShang 说。随即他把做过的几道好题跟我分享了一下。
思维量适中，码量较小，适合水掉。
第二天登录 luogu，发现“做题热度趋势”里多了个深紫色方块。
那就……这么干吧？

2025 年 10 月 31 日，周五

停课第五天。
停课期间又有两场模拟赛。第一场性质比较好发现，A 了两道，终于到了平均水准之上；但第二场模拟赛就很不乐观了，在普遍 300300 分，甚至有人 AK 的情况下只做出了 40 pts40\text{ pts}。
考前最后一天，机房似乎发了疯。“我退役啦”“批话哥”“巨——”的声音不停回响在教室。
竞赛老师忙着干考物工作了，机房又没人在管。我在此情况下也无心订正模拟赛了，把数论板块结束掉之后和 MengShang 他们爽聊一下午，中途还回班级参加了生日班会。
晚上大家走得都很早。有人还在哀叹自己没复习完，有人在“诚心诚意”地祝别人 AK CSP，也有人，比如说我们，在猜测“万圣节考 CSP 会不会给每个人发糖”。
回家本想做一道题安个心的，但发现团委那边好像有点事情。于是着手处理了一下，便没做题按时睡了。

2025 年 11 月 1 日，周六

早上八点半我们从学校乘中巴出发。到杭师大的路程差不多要三小时。
我自知看手机会晕车，所以闭目听了一路的音乐。中途还被热醒了一次。
杭师大恕园，我也去过不下两次了。但每次来心情都不同。这第三次也是一样。
我们在岔路口合了个影，随后前往附近一个食堂吃饭。饭菜挺美观，也挺好吃，但就是不让免费加饭。
不让加饭！
在食堂休息了片刻，我们一行人找了个空教室歇脚。此时距离考试还有一个半小时。
PatrickPanPan 停训了一年，在调线段树的板子；MengShang 带了信息学奥林匹克竞赛辞典，在桌上复习各种知识。我身后的 biLang 开启了 原神⋅空月之歌原神·空月之歌，lcyymqcxqhtlsztl 在跟高三的打王者。至于 s_mayunfeng 和 linxudong，他们似乎睡得很安稳。
Lizeh 在群里发了上午 CSP-J 的考题。我在食堂就听说 CSP-J 很水，只有 ABC 前几题的难度。一看，前两道显然，后两道不会。
一个前缀和，一个 DP。谁做它啊。转而去玩天天象棋了。

距考试 30 分钟

MengShang 在勤园考试，先走了；我们都跟老师走到了恕园。确认集合地点之后，我就向 202 机房走去。
进了机房，发现坐最靠窗一排，背对着窗户。这时候阳光终于有了些温度，覆盖了半张电脑屏幕，似乎让我回到了那熟悉的教学楼走廊。
我打起了呵欠。坏了，中午没睡觉，现在犯困了。
刚趴下去想眯一会儿，那个问题又在我耳边炸响：
一切都没变嘛。但又怎么可能变呢？仅仅因为我停课吗？
我这次会考出怎样的分数？拿得到一等吗？还是止步于二等停滞不前？
我的实力有增加吗？会因为我停课就能做出这几题吗？
脑海里两种声音不断盘旋：一种是质疑声，一种是闪过知道的所有算法。
考前十分钟。广播关了。给我的回答只有死一般的寂静。
监考老师来发草稿纸了。
广播开始报解压码了。
考试开始了。

2025 年 11 月 1 日 14 时 30 分

打开题目，解压文件，开始打头文件及快读快输。
杭师大的机房虽然有 Dev-C++，但是是比较新的版本，蓝色框变红色圆还是有点别扭，不过比 Codeblocks 好多了。
一开始不太适应这边的键盘，总是误触一些键，左右方向键也不好掌控。
打上 freopen，快读快输正确。开始看题。

2025 年 11 月 1 日 14 时 38 分

T1 club
根据前两年的经验，T1 应该只有普及组的难度。
看一眼数据范围，常规，但并不友好。
于是断定，T1 并没有普及组那么水了，而且要注意到一些性质。
建好文件夹，尝试在代码后面写注释，但发现不支持中文。
罢了，拿起笔开始演算。
“如果我能把 n2\frac{n}{2} 的条件去掉……如果每个人都能去心仪的部门……
“然而没那么顺利，总有些人要调动……
“等等，他们只需要调动一次！”
手磨样例，没问题。开始打代码，懒的思考怎么打比较简便了，所以打了三个功能一样数组、三个结构一样的 Lambda 表达式。大样例通过。
头晕晕的。可能是要回到月亮上了太激动导致的吧。

2025 年 11 月 1 日 15 时 03 分

T2 road
“如果没有那些该死的乡村，这显然是个最小生成树问题……
“k=10k=10，应该可以枚举吧，但这要占掉我 10310^3 的复杂度……
“不过枚举之后就可以了，和原先城市一连，还是最小生成树。
“复杂度 O(2kmlog⁡m)O(2^k m \log m)，好像只有前面八个点？
（考试时候真这样想的，后来发现其实有十六个点）
“不行不行。Kruskal 是不是有点烂啊，我记得有另外一个最小生成树算法只与节点数有关的？可是没学啊……
（说的是 Prim 算法，但其实最优只有 O(mlog⁡n)O(m \log n) 不可行）
“优化？优化……我可不可以减少边的数量……
“诶？如果已经有了个最小生成树，现在加了个点加了个边，其他没在树上的边是不是肯定不在新的最小生成树上？”
感性理解正确。理性证明似乎正确。手磨样例正确。
“这样复杂度是 O(2knlog⁡n)O(2^k n \log n) 的……log⁡n\log n 大概 13,1413,14 这样……似乎有些卡常？”
不太敢打，因为对我这种码力弱的人来说有很多地方会踩雷。正确性也没有严谨证明，有可能打了浪费时间。
“那就……看后面几题吧？”

2025 年 11 月 1 日 15 时 14 分

T3 replace
“不是 recall，差劲。
“这题考字符串……KMP？看着挺像的。
（其实应该更像 Trie 的但没想到）
“如果我能求出它的 border……有什么用？不还是遍历整个 O(qn)O(qn)？
“如果只能做到这个复杂度……我也许可以用 STL 水掉暴力分。”
T4 employ
“一眼 DP。但放在最后一题的肯定不是水 DP。
“设状态……如果前 ii 个人有 jj 个被录取……不对，太难转移了。
“好累啊。这个特殊性质我似乎可以看看……只有 1818 个 11？（磨了五分钟）算了，这样搜是行不通的。”
“啊，我该怎么做……思路都没有……
“算了回去打 T2 吧。”

2025 年 11 月 1 日 15 时 38 分

（当时以为只剩两个小时不到了）
尝试用 vector 存图，发现不好写生成树。
struct 保存边 e\text{e} 的信息，对权值进行排序，kruskal 维护并查集，将最小生成树建成一个新图……
嘶，新图叫什么好呢，就叫它 new_e\text{new\_e} 吧。
赶紧测一下，嗯没写挂。
然后开始搜索，dep\text{dep} 种图都得保存下来以免回溯时候要重新加边……
嘶，临时存的图叫什么好呢，就叫它 temp_e\text{temp\_e} 吧。
写完测一下，怎么有几种状态没搜到？噢，只是我输出有问题。
再测一下，怎么把输入掉个顺序就不一样了？噢，乡村的权值加少了。
样例过。大样例过。本地 1.2s1.2s。
一阵眩晕。我停下来缓了缓。
我盯着最后一个数据点发呆：2knlog⁡n2^k n \log n 会被卡掉吗？
算了吧，如果卡常那 CCF 不是人了。

2025 年 11 月 1 日 16 时 13 分

（打 T3 暴力，这时候意识到还有两个多小时）
STL 似乎不是很友好。左右区间的开闭是个问题。
于是打一行代码运行一次，就怕自己连骗分都骗不到。
头已经没那么晕了，心里冒出这样的想法：200 pts200 \text{ pts} 够了……
不，怎么可能够？T2 还不知道正确性呢。
高二了，是该冲最后一把了。
样例过。大样例不测了，肯定超时。
（打 T4 暴力，爆搜 8 pts8\text{ pts}）
燃尽了。去上个厕所吧。

2025 年 11 月 1 日 16 时 44 分

本来想在厕所踱步的，但发现监考老师跟我一起上厕所，于是尴尬地回了机房。
外面还是有些冷。甚至一到机房就感到了热气铺面。
回到座位，思考 T3 特殊性质 B。
“话说这个‘字符 aa 和 bb’是指这两个字符还是两种字符啊……
“看眼大样例，好像就是这两个字符。
“如果我能找出 si,1s_{i,1} 和 si,2s_{i,2} bb 出现位置的差，再维护一下前边有几个 aa，后边有几个 aa……
“对于每个 tj,1,tj,2t_{j,1},t_{j,2}，我也求出 bb 出现位置的差……
“但这样的话还要判断 aa 的数量，怎么降低复杂度？
“罢了，这是否有推广性？
“如果我把 si,1s_{i,1} 和 si,2s_{i,2} 不一样的地方哈希出来，再维护公共前后缀的长度和哈希值，好像就跟上边差不多。
“再求 tj,1,tj,2t_{j,1},t_{j,2} 的前、中、后哈希，判断是否一样不就好了。”
emmm，这做法肯定是乱搞，因为判断是否一样还是要遍历。排序之后二分查找，最优 O(qlog⁡n)O(q \log n)，但最坏会有 O(qn)O(qn)。
（具体如何哈希就不写了，怕 CCF 卡掉我）
中途有好几处边界问题，在 RE 了若干次后终于对了，且大样例本地 1.03s1.03s。

2025 年 11 月 1 日 18 时 13 分

收官。检查文件命名。誊抄字节数。
监考老师游荡。
广播响起。
考试结束。
刺耳的挪椅子声传来。
该谢幕了，该离场了。

2025 年 11 月 1 日 18 时 40 分左右

回到集合地点，发现我最先出来。Lizeh 在和别人打电话。
在等待同学集合的时候，我和几位先出来的同学交流了做法。
“这套题怎么这么多动规，T1、T4 都 DP 啊。”“嗯？”
“我靠，T1 我写了个 wqs 二分……”“啥？”
“我后面随机化乱搞的……”“啊？”
“我 T4 式子推出来了但打错了……早知道先写 T2 了”“巨！”
咳咳，去掉这些谈论，还可以听到：
“T2 加点的时候用归并可以做到 O(2knα(n))O(2^k n \alpha (n))。”“靠，我这做法复杂度假了。”
“T3 空间贼大，可以用字典树做。”“我靠，我怎么没想到 Trie。”
夜晚的恕园因我们而热闹。这算是人杰地灵吗？
灯火微弱，月光缥缈，桂香扑鼻。踏在绿化带上还能听见落叶碾碎的声响。
我们乘着日光而来，又随着月光而去。
空月之歌，启动
我们的目标，NOIP，正等我们追逐。

2025 年 11 月 2 日

起来，浑身酸痛，浑身发冷。
发烧了。
但为之庆幸吧——
因为这是一个没有作业、没有集训的周末。
下一次，我会在没睡醒的周一教学楼里
去醒来，再追逐。

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...