CSP 2025 游记

· · 生活·游记

Day -1

打模板，今天是疯狂星期四有没有人 V 我 50。

等等，星期四？晚上蹲点看 Pico，这集是 HHW 的，果然风格很 kkr。

丸山彩又被做局了。

Day 0

打模板，明天就要比赛了好紧张啊，打了点数据结构。

Day 1

上午真的没心思打了。初中的同学基本都去打入门组了。

剩下我们几个高中的留下来在机房开 UNO。考前消耗（积攒）人品来的。

中午食堂持石。匆匆收了行李就来机房。

泡了杯咖啡，然后出发。

到了的时候还有大于半个小时时间准备，于是找考点的同学聊天。

最后进考场，但是今年进考场格外晚，好像 28 分才进去。

解压密码……两遍过了。

直接开题，我的策略是先把所有题都先看一遍在决定要打什么。

先看 T1，看着很可做。

看 T2，图论吗，我并不擅长。

看 T3，有点繁琐的题面，这个“替换操作”能做一次还是多次？

看 T4，大计数。

看完了决定先开 T1，想了一下决定写反悔贪心。看来今年 T1 不像去年那么白痴。

30 min 左右写完了，但是无法通过大样例，然后我就发现了一些很繁琐的分讨。于是这个时候我开始考虑更换思路，因为这个反悔贪心就算能过也很容易写挂。

我考虑了一个 O(n^3) 的 dp。很可惜过不了。没写。

我考虑了一个朴素的贪心，总结就是跑四种方案取最大值。

我觉得这个做法很有正确性，也相对没有那么难写。

到 1h30min 我才写完，然后调了一下过了所有大样例。

我这时做了一个很重要的决定：保 T1 的正解，不要掉分。

所以我没有急着写后面的题，先是写了个对拍。好像很对。

保险起见，我在提交的代码中加了暴力，这样就算挂了也有暴力分。

这时过了两个多小时了。再不写后面的真没时间了。

开 T2，首先一档一档来考虑。

有 k=0 的分数，这一档完全可以直接跑最小生成树板子。

有特殊性质 A，我发现可以权值 0 的边直接连上去，反正点权为 0。然后最小生成树。

然后是发现了 k 非常小，考虑一个状压，状压某个点要不要重建，然后就把所有边连起来最小生成树。复杂度是 O(2^k(m+nk)\log(m+nk))。

这样已经可以拿到 64 分。

我们继续考虑：这个 m 太大了，要消掉。

发现最后取到的边只有可能是原图最小生成树上的边，那么先跑一遍预处理出来。

复杂度 O(m\log m+2^knk\log nk)，可以拿到 80 分。

这时候我打算先写这 80 分，因为 80 分和正解相差无几。

写的很快，想 + 写 + 调才半个小时出头，过了所有的大样例。

等等我不是没写正解吗，为啥能过所有大样例。

哦原来大样例没造满。

这个时候我做出了本次考试的第一个错误点：没有继续思考这一题的正解。

我觉得 80 和 100 没啥区别啊，然后就跳了。

但是其实只要把所有的边连上，状压的时候，没有的边直接跳过，就不用排序。

复杂度 O(m\log m+2^knk+nk\log nk)。

这真的很可惜。

这时还有一个半小时左右，我选择开 T3。

把这个题面转化为：有一些不合法点和一些区间，要用区间覆盖住所有的不合法点，求方案数。

这个时候我做出了本次考试的第二个错误点：读题不清晰。

这个“替换操作”到底可以一次还是多次？我观察了样例，样例中没有对此说明。我默认为多次。

那这题似乎有点不可做，我连暴力都不会打。跳。

但实际上只能一次，这样的话会有一个很轻松的能拿到 [25,30] 的暴力。

很可惜。

由于我认为这一题不可做，那么开 T4。

怎么做？首先有一个 O(n!) 的暴力分。光速打完。

然后考虑到特殊性质 B 和有一档状压分。

这几档加起来可以拿到 36 分，我认为很有希望。

这个时候我做出了本次考试的第三个错误点：死磕暴力档。

于是开始打这个状压，但是此时有点想昏睡，脑子糊了。

去厕所洗了把脸，回来继续打。

怎么计数？

对啊，怎么计数？

我打了很久，虚空调试了很久，发现计数会重，但是我不会去重呀。

有点慌了，我已经打了一个小时，现在距离结束还有半个小时。

旁边的同学在睡觉，老师在走动，外面窸窸窣窣的声音此起彼伏。

也许就只能到这里了吧。最后一个半小时，我一分都没拿到。

最后检查文件读写及保存。

出考场，天好黑。

预估 100+80+0+8=188。

七级没希望了啊……但是不挂分也许还有一等奖。

出来与同学交流，有上两百的，有两百大几，也有和我一样没两百的。

基本上所有人都反应 T1 不好写，那我放心了。

回家。真的好困。

同学们在群里交流心得，看到很多同学 T1，被卡了。

我很慌了，我不会也被卡？

手造一组 hack，坏了，错了。

为什么我对拍了两个小时没有拍出来？

真的崩溃了，现在 T1 也炸了，没戏了。

那现在 T1 就只剩下暴力分和特殊性质 C 的分。

结束了。

听听歌吧，耳机里放的是可惜夜的《夢現、夏風薫る》。

突然想起来，去年这个时候，我在听可惜夜的《明け方の夏》。

没想到今年还没有去年高。

一年了，你又什么都没变。

又是一年夏末。

梦境与现实、夏风拂香。

Day 2

睡了一觉起来没有那么难受了，今天一天就休息吧。

继续和同学们玩 UNO。

Day 5

官方发通知了，明天中午 11 点出分。

晚上，群里有人说出分了？？？

原来是通过申诉通道偷跑了，我来查查。

最终得分 100+64+0+12=176。

我该高兴吗？

T1 被碾过去了，但是 T2 挂了 16 分，然后 T4 反向挂了 4 分是什么鬼。

我草，我 T2 凭啥挂了。

教练有大手，说我是 RE，我的空间明明开的很够啊？

好多人都莫名奇妙挂了一堆分，机房里的人挂了 [-12,80] 分不等。

看来我挂的还算少。

这下大概率有一等了？可惜七级没戏了。

Day 6

官方出分，确实是 176。

云斗估分，一等线 160 左右，七级线 192 左右。

意思是，我要是不挂 T2 的 16 分，还真没准能七级。

真服了。

代码包发下来了，来看看我的 T2 为什么爆，哦原来是我边数组开成 N 的范围，是我唐了。

希望 NOIP 打好点了。

总结

NOIP 加油！