CSP-S 2025 游记

· · 生活·游记

初赛没啥意思，感觉 S 组可能比 J 组还简单。92pts 但一车人比我高。

复赛。

跟期中撞了。复习地没头没脑（同时指期中和 OI）。

听说很多人 AK 了 J 组？希望 S 组也简单点吧。

到考场，半个考场可能二三十个人里有三个我们机房的，还有高一级的巨佬 yangyang1000，还坐他旁边。抽象。

yangyang1000 敲键盘声巨大而且赛前一直在敲。搞得我好紧张。不一会来了个更巨的 幸存者 坐我对面。恐怖如斯。

下发密码之后好像有点没反应过来，可能是全机房最后一个打开题面 pdf 的？

诶诶诶？VS-Code 怎么编译？忘了复习了。哦哦哦会了。诶诶诶 VS-Code 怎么运行 .exe？哦哦哦彻底忘了。遂转 Code Blocks。

T1。好像不会啊？有点紧张。想了想想起上次死在贪心加上 T1 理应是简单题于是胡了个贪心，发现 \frac{n}{2} 性质很好就过了。

诶诶诶？怎么 diff 来着？诶诶诶？怎么在终端回退到 home 啊？哦哦哦彻底忘了。遂放弃。

得，复习了主席树线段树合并树剖 Tarjan 欧拉回路 exgcd，然并卵。结果基础操作忘了。要是因为这个痛失什么就释怀了。

开 T2。最小生成树。Prim 好像忘了怎么办？虽然会 Kruskal。脑子转得很慢，过了 1h 才想到 \mathcal O (2^k m \log m)。这个东西只有 56pts，road2 的大样例都得跑 6 秒（本机）。怀疑自己写法有问题因为算出来其实才 6 \times 10^8。但是没时间管了。难道真的 1s 10^8？

后面一直想优化掉 2^k 但是其实没注意到瓶颈在于 m。于是就似了。这里只需要观察到可以贪心地选第一次 Kruskal 留下的 n-1 条边即可。怎么还是死在贪心了呢。不会 T2，死在贪心，多少次了？

有了上次 T2 花 2.5h 的经验于是迅速润去 T3。事实证明我如果花更多时间看 T2 没准会？那也是马后炮了。T3 好像有点难懂，一度以为替换能替换多次，还以为没一分可做。后面意识到好像 1 \sim 5 可以哈希然后 B 性质也很有意思。好像是个二维数点。

可是当时我没认识到是二维数点以为 vector + lower_bound 就完事了。写了 0.5h 才发现，直接放弃转写暴力（甚至是个不错的决定？因为答案很小的情况下暴力复杂度不高，大概是 qw，其中 w 是答案量级。而大样例的答案不超过 10。）。

写出来了但是不能 diff。结果翻到最后 981 行似了。调了 15min 才发现某处多减了一。虽然 981 行是对了，但没有 diff 还是不知道正确性。是的，至今不知道。

至此还剩 1h。赶紧码哈希。结果写了 40min 没调出来。诶怎么只剩 20min 了？？？说好了还要回去写 T2 结果 T4 没看 T3 最基础的暴力没写时间就没了？虽然不是第一次考场上没写出哈希了。好像就没怎么写成功过？还好 substr 救了我不然 10pts 暴力都写不出来。

瞄了一眼 T4 发现有点读不懂再加上时间所剩无几所以就没动。赛后发现人均 8pts。还有阶乘骗分法。后面还有最后三分钟卡常 T2 把所有没用的 long long（有 typedef long long ll 然后所有循环变量用 ll 变量的坏习惯并且也有过把所有变量从 ll 变为 int 后过题的经历）全换成 ll。结果 road4 大样例一直是负数输出。最后发现是 Kruskal 函数的返回值设成 int 了。最后一分钟交上去的，但愿没死。

估计 100+56+15+0=171？虽然但是，真理。

就这么混乱地考完了。yangyang1000 第一句话对幸存者说：我又不会 T3。幸存者说 T3 用的 AC 自动机然后 384。叹气自己一年比一年分低（他初一 AK S）。那我是不是死了。

Fancy 不会 T1？神秘。但是发现自己 T2 好像被刷的无影无踪了。后面 mzq 更是直接告诉了贪心做法。然后 lyx 也会 T2。wtz wlx ljx wyp 等大佬还没问呢。听说他们在讨论为什么不去看 T3。这是人均 T2？那我真无了啊。

好像自己真的是分最低的。不过想到 T2 有可能冲到 64 然后 T3 数据水的话最多 35。100+[56,64]+[15,35]+0=[171,199]？T2 感觉希望不大 T3 感觉有点机会。主要是 T2 死的太惨了直接少了快 50。

赛后难得在期中前水 lg。最神秘的是 zhc 的得分 100+0+50+8=158，T2 没写。好像不少人没注意到 t_1 可以不等于 t_2。我好像判了？可能是好消息。但是还是坏消息多。

感觉能打 NOIP。要是打不了就退役得了吧。

退役吧。t1 25pts。

最终 25+56+25+0=106。