CSP2025 游记

Mr_Min · 2025-11-04 13:15:49 · 生活·游记

不知道干嘛，随便跳题跳到了一道简单题，和一道很难写的数据结构。

不想复习，严肃围观学长打篮球赛。

摆了一个晚上。

目标是 300。

上午在家随便看了点博客，然后就开始水群。10:15 上了火车，火车上追忆了一下脚本啥的该怎么配置，然后 bilibili 启动！

11 点到站了，去考场等 lw393，连续拿两年普二也是神人了。

在考场外继续水群，发现好像没人发题目？11:40 多 lw393 出来了，发现他 AK 了，要成为 JX 第一个 J 组满分了吗。

去食堂路上问了一下题，发现似乎比较简单。

中午继续摆。

下午提前 30 min 进考场，光速配好 VSCode 和 makefile。

测了一下速，发现 10^8 次固定模数取模要跑 300 ms，疯狂。

14:30 准时下载到了 pdf，先化半个小时把没到题都想了一下，T1 秒了，T2 不会，以为有 64 分送的（事实上是假的），T3 串串题，A 性质 50 分很可做，T4 有 20 分状压。

于是先写 T1，30 min 写完了，然后看 T2，一眼就看出了是最小生成树，然后以为脑抽了忘了乡镇改造只算一次费用，写了一个很错的东西，成功过不了大样例。

注意到只算一次后，想了一个贪心，每次把原图的边和乡镇改造可以加的边放一个堆里，然后从小到大取。写完发现假干净了。

在不知道多久后发现可以枚举那些乡镇要改造，于是会了 O(2^k (kn + m) \log (kn + m))，只有 64 分。

此时已经 16:00 了，感觉要寄，先去写了 T4 8 分暴力，瞪了一眼 m = n 不会（？）然后就去写 T3 了。

由于 T2 没写出来所以非常慌，在想到把最短的不同的子串提出来后会了 AC 自动机的做法，然而我早就忘了于是更慌了。

想着写个 kmp 代替一下，发现自己 kmp 也写不明白，遂放弃。

决定死磕 T2，然后发现 m 条边是没用，只用存 n - 1 条，写出了 O(2^k kn \log kn)，不知道为什么大样例跑了 1.5 s，感觉会死。

于是继续优化，发现可以存下最小生成树，然后就变成 O(2^k n\log n)，显然稳过。

大概到 17：00 写完了 T2，菜完了。

然后写 T3，由于做完了前两题，心态好了很多，会了 A 性质。

于是开始写，直接把所有 s 分类，每次只在同一类中找，O(nq) 但是常数很小。

写的时候很顺利，但是中途会了正解，只要每个类建两颗字典树就变成二维偏序了，还剩 1 小时最后放弃了。

写完一测大样例，全过了，还跑得飞快，最慢只有 100 ms？

还有 30 min，T4 状压随便想了想，没有写。大部分时间都在优化 T2，和检查了。

最后四道题检查了文件读写提交了，18:30 准时离场。

大概是 100 + 100 + ? + 8 \approx 258。

出场后发现 T2 确实很难，有一车人被卡了。

原来 O(2^knk\log nk) 能过吗？为什么我的跑的这么慢。。。

学弟写出了 T3，被单调队列了。

怎么大家都写了 T4 的状压啊。

晚上得知 T3 没有 |t_1| = |t_2|。

挂完了。

艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹艹

晚上在 lw393 车上刷手机，手机忘充电了，耳机忘充电了，寄。

hz 把压缩包破了，集训队爷太强了%%%/bx/bx/bx

用手机把代码测了一下，洛谷 258，云斗 288，貌似没有 WC 去了欸。

教练我想去 WC 教练我想去 WC 教练我想去 WC 教练我想去 WC 教练我想去 WC 教练我想去 WC 教练我想去 WC 教练我想去 WC 教练我想去 WC 教练我想去 WC 教练我想去 WC。

upd on 2025.11.05：草，T2 80 分被卡常了，我 O(2^kn\log n) 怎么卡的？238 没厕所去了。