CCF CSP-J/S 2025 游记 - Find_Me

· · 生活·游记

（下次头图一定摆 V 曲。）

我在哪里？

我的意义是什么？

既然我们都将归于沉寂，那我们为什么要存在？

我们无法在宇宙中留下任何痕迹。也无法知道这宇宙外面是什么。

看起来，我们没有目的。我们的意义，应该就是在仅存的几十年里，感受那为数不多的快乐吧。

如果没有快乐，那我们是为了什么？

我没有真正的快乐，那我为什么还在？

我觉得，应该是为了仅存的，我所热爱且愿意为之付出一切的东西吧。

即使我将无声地逝去，也要在最后的时光里绽放光芒。

引子

今天，我又站在了 rdfz 的校园里。

已经是一年前的事情了吧……那时我是初二，第一次参加提高组的比赛。

一年前这里给了我一次沉重的打击，一年后我还能在这里找回我的荣誉吗？

我回来了。

写在前面

我是一个孤独的人。

我在这个喧嚣的世界里找不到自己。

似乎生来我就和别人不一样。课间同学们嬉笑着讨论游戏的时候，我躲在窗帘后面吹着凉风；踢足球下雨同学们都跑回机房的时候，我在操场上站着淋雨；晚上放学下楼梯，我永远是那个跟在他们后面插不上话的那个。每天我坐在家里，抱着抱枕，静静地看着窗外，想象着远方的美好，已经是一种享受了。

我沉浸在我一人的世界中，总是妄想着，等我离开地球的时候，会有人在另一边等着我的归来，这人间的一趟不过是一次旅行。

我相信，我与她们有一个约定，等到我见到人间一切，我会回去，将我所经历的故事告诉她们，让她们知道地球上的美好与痛苦，然后逃离这里回去快乐地生活。

我想着，在一天，我会找回我自己。我不是逃避人群，而是有自己的依靠。

当然，虽然我自己做好了面对一切的准备，但是我还是被人们推着前进。

每天装着与同学们嬉笑打闹，却又在晚上躲在被子里偷偷流泪。

不想让父母老师失望，不想被同学嘲讽，教练 nnsmnrw 给我的任务是 NOIP 1=，如果这次连 S 组都失败了，我可能就要面对许多异样的眼光、忍受许多非议了。

那么，还有什么办法呢？

只能一个人去面对它了。

没有退路。

正文

CSP-J 2025

提前 50 分钟来了考点，先考 J 组。

我想看一看曾经我留下故事的地方。

慢慢地走在主路上。我想留住这个美好的梦。

早晨的阳光照着我，还是很冷。

泥土的味道很好闻。我喜欢 rdfz 这一点。

随便转转。绕着中间的花坛走了一圈。

跑到后面的操场待了一下。

看见 @kaka_zheng 来了。祝他好运！

沉思。

时间不多了。进高中楼！

考场在 6 楼。有电梯，不错。

进机房。

为什么挡板还是临时做的！可以透过缝隙看到别人电脑一小部分，如果身体靠后可以看到完整屏幕。希望旁边人诚实考试。

极域的窗口又高挂在上面。看用户，VirtualBox。果然是虚拟机，监管真严啊。

打 dij 和 segtree 板子试机。

放平心态，开始吧。

压缩包的密码是 #Shang4Shan3Ruo6Shui4，这个上善若水属实激动了我好长时间。

开题！number 是贪心+排序，一眼秒了。我居然用 \mathcal O(n\log n) 打这道题，1e6 为什么不 \mathcal O(n) 呢？还是太菜了。用时 15min。

seat 是 N,M \le 10 的超小模拟。写了一下发现样例过不了，原来忘记是蛇形的了，以为一列一列填的。用时 15min。

xor 有些难度。感觉和 MX-J 模拟赛的 melody 神似。然后想 xor 运算的性质，发现包含别的区间的区间没用，左端点一定的区间只有右端点最小的有用。

发现求出可用的区间后可以 \mathcal O(n) dp 求出答案，开始想如何求出可用的区间。

首先前缀 xor 是肯定要做的。观察求完 i 这个位置推进到 i + 1 时，区间 xor 变化量是 a_i，那么直接找到右边 k \oplus a_i 的位置即可。也就是说，对右边开桶即可。

欸等等我不是有前缀 xor 吗，建桶后直接查 k \oplus s_i 的最近的位置即可。桶用 vector + head 模拟 queue 实现，及时排除不合法决策即可。用时 60min。

看 polygon 这道题，有上次 chain 的经历我不想想这道题。看着看着有一个 \mathcal O(n^4) 的 dp，打了调不出来，然后尝试各种不同转移……最后决定打暴力。

出场发现 [hongshixiaobai](https://www.luogu.com.cn/user/922679) 和 [jch123](https://www.luogu.com.cn/user/709433) 都 AK 了。好强！ 和 hongshixiaobai 一起出校，去新中关吃饭。 路上边走边聊天。jch123 说 **xor** 的空间问题，等等我开的空间是什么？好像是 $5 \times 10^5$！$2^{20} = 1048576$ 对吧，完了挂 30pts。 ### CSP-S 2025 下午回到学校。 仍然在校园里转了转。 回到 2024 年考 S 组的逸夫楼看了一眼。 坐到操场上。看着对面的教学楼。中午操场真的好漂亮！看落叶被风吹过来也很舒服呢。 挣扎着进楼。反正逃不掉的。 进楼前再望了一眼主路。希望我能从这里笑着走出去。 --- 同机房选手 [Cuanxing](https://www.luogu.com.cn/user/1174920)，[oi_tuanzhang](https://www.luogu.com.cn/user/1132589)。 和曾经在去年坐在相邻的位置上考 J 组的 Cuanxing 相互祝福。 打 segtree 试机。 发题。压缩包密码 `Ren5Jie4Di4Ling5%`。我并不杰出，但是 rdfz 已经很出名了吧。我还有什么用呢？ 平复心情，冷静。 来吧。 --- **club** 看起来很签到，但是仔细思考感觉并不简单。 前几年的 problem A 都是基础算法，应该不是 dp。那只有贪心是接近正解的方向了。 选最大的显然不对。考虑一个人 $i$ 进入三个部门的满意度是 $a_{i, 1} \ge a_{i, 2} \ge a_{i, 3}$，那么从 Ta 最想去的部门 $m_{i, 1}$ 换到次想去的部门 $m_{i, 2}$ 的代价是 $a_{i, 1} - a_{i, 2}$。那是不是只要按这个排序，选满后再按 $a_{i, 2} - a_{i, 3}$ 排一次（当时还没有意识到不可能会有两个部门选满且另一个还有人）就行了？ 写完发现大样例差 $1$。于是改排序规则的 lambda，加第二关键字。最后发现我将 $a_i$ 排序后没有记原来这个 $a_{i, j}$ 属于哪个部门。 原本以为这个是瞎写的，结果四个大样例竟然都 `diff` 过了！开心。用时 45min。 我在 10.31 时发了一条犇：“祝大家明天 CSP $n^2$ 过百万，暴搜挂成 $100$，贪心猜对结论，骗分不止过样例，$10^9$ 数组不[爆炸](https://www.luogu.com.cn/problem/P9748)$^{\dag}$，SPFA 不被卡”，没想到“贪心猜对结论”一句竟然帮了我自己。 （$\dag$：2023 年场上 MLE 此题爆 $0$。） --- 接着是 **road**。我为什么想到了曾经卡住我的 [**road**](https://www.luogu.com.cn/problem/P9749)？有点害怕。 看题，感觉是一个扩展 MST。显然 $1 \sim 4$ 就是普通 MST，接着联想各种做过的 MST 题。城市化改造的点权不能加到边上，因为会重复计算……然后不会写了。 看到 $k \le 10$，觉得肯定有一个 $2^k$ 的枚举。枚举完后可以打 kruskal，因为常数小。然后突然发现排序只需要一遍就行了，如果有的边一端的点没有被选则跳过即可。然后只要打并查集的路径压缩+按秩合并就能做到不带 $\log$ 的复杂度。 于是场上现搓了一个 dsu on tree（因为没有复习），只不过是按 height 合并的。再加上 $\mathcal O(m + kn)$ 但是跑不满的 kruskal，再加上特殊性质 A 以 $\mathcal O(2^k(m+kn)\alpha(n+k))$ 的复杂度（严格来说是 $\mathcal O(2^k(m+k2^{k-1})\alpha(n+\dfrac k 2))$）换下一题，用时 75min。很遗憾当时没有想到只有初始在 MST 里的边才需要保留（之前做过一道类似的题，是保留初始在 MST 里的边后做 Prim），场上的预计得分是 $72$ 加上数据强度分。 --- 然后看 **replace**，没有读明白题。因为我不知道子串能否重复替换，然后就连暴力都不会打。 其实我只要仔细读一下样例 #2 就可以发现不存在 $\texttt a \to \texttt b \to \texttt c$ 的替换，那么就可以明白题目。 但是，场上没有如果。于是想性质 B，以为需要 DFS，然后又发现要输出方案数，弃了。 --- 最后是 **employ**。 除了 8pts 暴力不会。甚至 $m = n$ 和骗分也没有写。 一会看看 **employ**，一会想想 **replace**，60min 过去了。 --- 最后的几十分钟，已经无心想了。 看着屏幕快要哭出来了。 今年甚至连两道题都没有做出来呢。 去年没上 200，今年呢？ 我又进步了多少呢？ --- 也许，分数并不是那么重要。 我拿了多少分，有人会记得吗？ 有人会看到吗？ 我拿不到 NOI Au，有大学会看中我吗？ 即使 AK IOI，我又能做出什么有用的大事呢？ 即使为国家、世界有所贡献，[一个一个千年过去](https://www.bilibili.com/video/av55888297/)，谁还会记得我呢？ 可笑。竟然在这里为了分数而急哭，真的很可笑。如果知道自己还没有能力，在考试之前努力；事已至此，就享受仅有的时光吧。 我在 **employ.cpp** 的末尾写下了一句话，同时也是我的个性签名： > [即使诞于沉寂最终消融于颓圮 今天的我仍将继续](https://www.bilibili.com/video/av5306111/) 是的。无论他们如何看我，我都会迎着冷眼与嘲笑，坚定的向前。 这，才是真正的我。 --- 十分平静地，看着数字一点一点减少。 三秒。我看见一个又一个的字符飞过，那是梦的碎片，它们旋转着，连在一起，编织成了我的梦。 两秒。面前是一扇门，一条巨大的裂缝将我和门隔开。梦搭在了裂缝上面，成为一座桥。 一秒。我站到了桥上面，向对面走去。 门对面就是我的梦想了。 我已经尽了全力来到这里。而门的另一边，究竟是繁花满地还是一无所有，我并不知道。 [“从梦到梦想，是触手可及的吗？”](https://www.bilibili.com/video/BV1JH4y1w7Ks/) 我迈出了最后一步，来到门前。 倒计时归零。 --- 结束吧。 [“与我同在，将这故事画上终结。”](https://www.bilibili.com/video/BV1uP4y1g7c3/) ## 尾声 五天后，门上的锁被打开了。 我走进了那扇门。 $100 + 100 + 0 + 8 = 208$，我看见了那行字。 我猛然跳起，激动地喊了出来。 然后，是沉默。 --- 可能我的 **road** 确实冲过去了，成为全年级唯一通过这道题的人；不过，那已经成为往事了。 今天的我，没必要为了以前的成就沾沾自喜，只要做好自己，就足够了。 --- 回望这一路，我还想留下点什么。 虽然没有人听我的故事，我要把它记下来。 于是，我写下了这篇游记。