CSP 2025 游记

以下用 [数据删除] 代替暴戾语言。

2024 年，某小升初 oier 在 CSP 考场上的抽象行为集锦：

最终双 2= 遗憾离场。

集训时长累积 30 天。

J 组 86 pts，S 组免考（GESP）。

参加了某教练的三场模拟赛，分别获得 $110,185,210$ pts。严肃批评教练不给大样例的行为。

vp 了 SCP 2025，赛时得分 $100+8+12+8=128$，卡线 20%。花了很多时间想 T3 的 28 pts 做法，但是发现根本不会做。问了一圈发现大家都会做，以为是我 [数据删除] 了，结果补题的时候发现是 pdf 把 $n,m \le 3000$ 写成了 $n \le 3000$（详见 帖子）。强烈谴责 + 下次 SCP 再也不看 pdf 了。

又参加某教练的模拟赛，250 $\rightarrow$ 30 pts。看了一眼榜，人均挂分 200 pts。讲评的时候教练批评我们「老是想用提高级算法而放弃了思考」。合理怀疑教练是故意不给大样例让所有人挂分，然后借此说批话。

信心赛的 7 道题名称均包含子串 $签到$。难度红橙黄绿蓝蓝紫，还放了一道交互。切了前 3 题，D 题也已经有了思路。感觉状态不错。

赛前老师给所有人发了士力架，还让我写了做题策略（伏笔）：

晚上 11 点钟就睡了，而且睡得意外很好。

考点在七中高新。考场的监考员先是把回收系统网址写错了，然后又延迟了 3 min 发题。CCF 退钱。

T1 T2 签到题。

08:45 开 T3，发现如果能处理出所有满足条件的区间的话，剩下的就是一个经典贪心。又根据贪心结论，对于每一个下标，以它为左端点的区间最多只有一个且长度最短，故 $O(n^2)$ 做法显然。根据策略 1，先把这个做法写了出来。现在有 60 pts 了。

09:10 开 T4，可以很显然地设计出一个 $O(n\cdot \sum a_i)$ 的 dp，期望得分 80 pts。写出来了之后一直在想怎么用数据结构优化掉，然后把式子各种变形终于变成了区间加区间查的形式，结果发现线段树根本开不下。在浪费了大量时间后还是放弃了。

10:40 回去想 T3，发现似乎优化是显然的。但是赛时脑抽了写了一个很抽象的实现。11:10 过了大样例，然后摆烂。

估分 $100+100+100+80=380$。问了一圈同机房的除了 1 个 AK 的以外好像都没我高。

中午看了一眼题解，发现 T4 是简单题，只需要正难则反一下就能很轻松地做出来。没切黄。我是 [数据删除]。

无所谓了 J 组本来就不重要，对吗？

下午网址没写错，而且准时发了题。

T1 读完题发现 $O(n^3)$ 的暴力 dp 似乎是显然的，几个特殊性质也是显然的，AB 随便排个序贪一下就完事了，C 直接把最大值相加应该就能过。共计 80 pts。根据策略 1，先把 55 pts 写了出来。

14:45 开 T2，发现好像很抽象。当时没细想，觉得根本不可做。结果犹豫片刻后选择了回去想 T1 正解。这显然违背了策略，但这个决定却救了我。

回到 T1 后，我先尝试了一下优化 $O(n^3)$ 暴力，发现不太可行，于是认定是贪心。然后没有经过足够的思考，就打了一个很 [数据删除] 的做法（违反注意事项 4）。大致思路是先让所有人选最满意的，然后依次遍历每个社团，如果有爆仓就让当前社团中若干个滑档后损失最小的人滑档，经过若干次调整直至满足条件。这个做法虽然很 [数据删除] ，但是确实是正确的。但实现起来比正解麻烦许多，而我码力很弱。写了将近 1h 后心态有点爆炸 —— 我想起了去年 S 组 T2 的惨剧，难道今年又要因为冲动而重蹈覆辙了吗？顿时恐惧充斥了大脑。幸好残存的最后一丝理智阻止了我删代码。然后仔细想了一下，得出了只会进行一次调整的结论。于是把之前的代码改了一下就过了。虽然有惊无险，但此时时间已经过去 1.5h，而我才做了一道题。

16:00 回去看 T2，这才发现子集枚举 + MST 可以得很多分（算上特殊性质 A 有 72 pts 的样子）。当时没仔细算时间复杂度，写了大概 20 min，一测发现第三个大样例要跑 3.4 s。分析后发现时间复杂度是 $O(2^k \cdot (m+nk) \log\,(m+nk))$。但即使如此也不会被卡啊，难道是我常数太大？尝试了各种手段，然而连 3s 都压不进去。此时距离做完 T1 又过去 40 min，我感到前所未有的压力。后来突然意识到可以先把所有边建好，然后枚举检查的时候只需要把不能用的边跳掉就行了。时间复杂度优化到 $O(2^k \cdot (m+nk) \log\, (n+k))$，样例 3 只跑了 300 ms。期望得分 72 pts。

开 T3 时已是 17:00。看到字符串时内心是绝望的。这玩意儿以前似乎很少考，所以我根本没复习。强迫自己冷静后看了一眼数据范围，10 pts 显然直接暴力就行，那 25 pts 呢？我想了许久，终于想起了哈希，但和字符串相关算法我基本没写过。但基本思想我还记得。于是打算推一推。幸好哈希的式子还是很好推的，大概 10 min 不到就会了。然后开始写，写得很仓促，而且由于不熟还写出了诸如 ha[i] = (ha[i - 1] * base + (t1[i] - 'a')) % MOD 的 [数据删除] 代码。一测当然全 WA。看了半天才发现问题。后面还因为下标写错调了一会儿。总之又花了很多时间。

开 T4 时已将近 18:00，只剩不到 40 min。看完题发现 $n \le 18$ 的 $O(2^n \cdot n^2)$ 状压 dp 似乎显然，于是开写，同样写得很仓促。写完 WA 了。此时只剩 20 min 不到，内心非常焦急，各种乱改，好不容易过了样例 1 又过不了样例 2。时间一分一秒地流逝，只剩 10 min 了！是继续调，还是去写 $O(n!)$？！在剩下 8 min 的时候我做出了选择 —— 打 $O(n!)$！此时监考员已经在催交代码，全考场只剩我一人还在敲打着键盘。赶在还剩 3 min 的时候写完了，一遍过了样例，赶紧交了代码，检查了一下 freopen 就离场了。

估分 $100+72+25+8=205$。

走出考场时我内心是忐忑的。T1 和 T3 的样例似乎都不强，而且我一个对拍也没写，会挂多少分完全是随机数。好消息是，我估分好像是机房最高分。

回家后先出门散步，21:00 回到家后发现前两题已有民间数据。立刻开始重构代码。T1 100 pts，T2 72 pts。22:00 T4 民间数据也出来了，8 pts。此时只剩下了 T3，也是我最没把握的一道题。重构代码时才发现 $|t_1| \ne |t_2|$ 要判，当时心瞬间凉了一截，结果仔细一看发现我的写法似乎自动判掉了这种情况。虚惊一场。

早上起床发现 T3 民间数据已出，马上测。25 pts。一分没挂啊，有点陌生。接下来只要 freopen 写对大抵就能稳 1= 了吧。

现在想想只觉得幸运。如果当时真的按策略把 T1 55 pts，T2 72 pts，T3 25 pts，T4 20 pts 打完了，那么 T1 正解恐怕没时间写……

出分了。好快。

J 组 $100+100+100+80=380$，S 组 $100+72+25+8=205$。

赢了。

又是一年过去了啊，恍如隔世。这已是我打 OI 的第三个年头。

回望过去的一年，OI 让我见了很多老师、交了很多朋友、学了很多东西、也花了很多时间。说实话，我现在已经不知道自己为什么要学 OI 了。

记得 23 年 10 月，我和我妈自驾去绵阳考 CSP-J，虽然只考了 2=，但那时学 OI 真的好幸福啊……

前阵子语文周考，作文考的《以 XX 为桥》，我写的《以初心为桥》，素材是 OI，但我似乎已经忘了自己当初学 OI 的初心是什么。或许，我当初所谓的初心，不过是孩童天真的幻想吧。

有时我真想不通，自己为了这 [数据删除] OI 花这么多时间，最后还不一定出成绩，到底有什么意义。有这时间不如去搞搞我那 [数据删除] 文化课。

但我对 OI 却总有一种特殊的情感，促使我义无反顾地学它。是热爱？是依赖？还是已经麻木？我不知道。唯一可以确定的是，我还会沿着这条路走下去，即使找不到起点，也看不到终点，也要走下去，毕竟

By Mier.

今年游记总算有点文采了，应该不用删了：）