CSP-S 2025 差点(貌似真的)坠机记

· · 生活·游记

突然发现自己成为老年选手。

省流：[0,100]+[0,100]+[0,50]+[0,5]=[0,255]。

upd：100+80+50+4=234，你 md 的 CCF B 题 O(2^knk) 才给 80。

2025.9.19

明天怎么初赛了？

2025.9.20

今天怎么初赛了？

去年还做了很长时间的模拟题，今年是一套完整的题目都没做，不管了 qwq。从学校请假回家玩了一上午，百合番真好看。

下午 1:30 左右到考场，发现只有物理竞赛的开始入场，所以就先去机房上找同学了，模了一会鱼，时间到了就一起去考场。

进考场才发现监考老师是教练，主要任务从完成初赛到憋笑挑战了，高年级的学长和 djydjy 在其他考场。

开考后感觉不大好，神秘 DAG 比较难搞，KMP 也忘的差不多了，有好几个题目都是靠排除法做的，到了程序题好了一点（考前其实做的最少的就是程序题）。最后一题有点小插曲，所以看了很长时间，索性最后理解题目做法了。

出考场后感觉比较轻松，毕竟题目基本都会，比去年简单一些，对了一下 luogu 的民间答案，只有三个答案不一样，应该是稳了。

2025.9.？

忘了是哪一天了，总之就是出分了。

预估 93，实际 90，被 CFF 做局了，CCF have no eggs。

djyqjy 考了 94，Bonely_Muffin 考了 95+，太牛了，疯狂磕头。

2025.10.1~2025.10.5

考了若干次，成绩非常不理想，经典的套路和 trick 全部忘光，拆位状压猜测半个小时网络流，原题变了个表达方式认不出来。

菜完了，预计 CSP 会坠机。

2025.10.?

第一次月考，垃圾完了，政史地加一起大约 220，排名飞到 500+ 了。

2025.10.20

貌似比较认真对待的比赛。

T1 开场发现 r=n，然后搞了个前缀和秒了，没写代码看 T2。

T2 看起来非常神秘，阅读了一下后懂题意了，看了一下特殊性质 k=2，思考了 b_1,b_2 之间的关系，貌似推出了本题所有核心性质，此时过了 0.5 h ，继续看 T3。

T3 看错题了，虽然出题人贴心加粗了且，但我仍然看成了或，询问了一下 flyfree，他说 ACD 是简单题。

T4 非常神秘，我觉得很困哪，跳过了（和 CSP2024 一样正确的决定）。

T1 光速过了所有样例。

T2 光速挂了一堆，重新整理了一下条件和思路，也是成功变的更乱了，进入了 2h 的垃圾时间，最后调出来了。

T3 暴力跑路。

最后菜完了，发现 T3 是 ABC F 的平均水平，不评价。

2025.11.1

今天怎么复赛了？？？

由于去年考前认真复习直接坠机了，所以今年尝试摆烂打法，最好的状态就是没有状态。

花了一上午时间 Hollow Knight。把芬达和失落近亲打了，跳了苍绿之径的跳跳乐，最后在跑到王国边缘被巨大的 CCB 生物踩死好几回。

很好玩，学校的步行道的银杏叶变成了金黄色，非常的漂亮，可惜忘拍了，不过银杏果被踩碎放出的垃圾味真的很难闻。第一次坐学校大巴参赛，非常有新鲜感。

回想一下去年失败的原因，貌似是太紧张了，路上制定了一下计划：0\sim 0.5 时顺序开题，先口胡，0.5\sim 2 时看完所有题后再打，2\sim 3.5 时拼暴力，最后 0.5 时检查一下问题。虽然这个计划后面几乎没用。

刚上车气氛比较轻松，大家有很多放歌的，比如准备出发，熙熙攘攘之类的，我放了一首影色舞，但车上貌似有人休息，我没放多久就关了。

进考场了，和 flyfree 以及同届的同学 baoliniu 一个考场，结果发现 ask_silently 就在我旁边？不管了先磕头。键盘很好使，系统也非常流畅，总而言之给考场打好评。

过了一会就要开考了，捣鼓了一下解压缩和文件拓展名，就开题了。

T1 是小清新题，\le \frac{n}{2} 的限制直接想到了 CSP-S2019 Emyia 今天的饭，感觉就是简单反悔贪心？

T2 是图论题？看了一眼想到了 Watering Hole G 这道经典超级源点 MST 典题？细细一想感觉很有差别，就认为自己想假了。感觉 k\le 10 非常奇妙啊，n2^k 正好是 10^7 级别的，难不成应该在这里做文章？

T3 是字符串题，刚开始貌似没能理解限制，以为找出本质变化的部分然后扫一遍 Hash 就秒了，比较激动，就跳下一题了。

T4 读了一遍题，题目意外的小清新，是感觉很经典的排列计数，但 \le 500 非常神秘，考虑了一下 n\le 18 和特殊性质跑路了。

T1 整合了一下想法，最多一个营超过限制，我们就对这个营反悔，反悔一定不会使其他营超过限制。想清楚后写了一遍过了，情绪比较高涨，觉得自己能考好。

T2 开始思考，看了看暴力，m2^k 用 MST 应该是好做的，但没前途，于是开始胡思乱想，比如在求 MST 的过程中每加一次边就用 k 个点让他们连通，总而言之没一个对，于是跳了。

T3 光速写完 Hash。一测大洋里发现有限制没理解，比较沮丧，发现自己只会做 O(L^2)，比较垃圾，此时过了一个小时垃圾时间。

滚回去写 T2，发现貌似可以求出原树的 MST，然后枚举二进制状态，把 nk 条边加进去再跑 MST，这样边数不是很多？感觉很对，可以用加一条边会形成环的方法证明，不管了，写写写，过了样例二，挂了样例三

我宣布我有 T2 症。

比较绝望于是滚去写 T3 了，有点迷糊，脑子里一直在放魔法少女小圆的插曲 and I'm home（百合害人不浅/ll），最后写完 70 行左右的暴力。非常痛苦，于是申请了厕所，洗了把脸。

回来仔细想了一想，再这么搞就完蛋了！要清醒，于是开始思考 T3 正解（我真的清醒吗）。把本质不同的部分去掉后要同时满足前缀后缀的匹配才回产生贡献，最开始想着前缀后缀拼起来做 AC 自动机，后来发现假了，因为本质不同的变化串确定后，匹配的初始位置也确定了，直接 trie 就行了，迷迷糊糊想了后发现这个思路只有一半，且比较难写，还有细节，而此时只剩下 1.5 时......woc! 只剩下 1.5 时了，搏了一把，决定去调试 T2。

先把 T2 改成了 O(m2^k\log m)。经过玄学的调试发现我的貌似是跑多组 MST 清空错误的问题，后来发现是不被覆盖的部分被排序打乱了，就错了，改过来后就对了，又改成 O(nk2^k\log n) 就对了，但是大洋里在不满的情况下依旧跑了 9 秒，决定卡常，发现排序可以放在外面，就优化成了 (m\log m+nk2^k)，这个时候机子也跑的比较快，大概 1 秒就跑完了，虽然不放心但止步于此了。

写出 T2 后精神状态好了一些，至少比去年强了，于是整理一下思路把 T3 的 O(nq) 写了，由于没有大洋里我过了小样李就直接交了。

去赶 T4 暴力，发现只剩下 10\min 了，疯狂拼写 STL 中的全排列函数，尝试三分钟后失败，最后 cout<<0<<endl 再见。

干完这些事后我开了最后一盒奥利奥，突然听见老师提醒说这个考场还有人没有提交代码，我突然反应过了，我好像只上传了没有交，于是赶紧交了上去，此时只剩下了 3\min，如果不是善良的监考老师，我可能现在已经被温和的教练打断了双腿。

然后就出考场了。

ask_silently 和 flyfree 都没过 T2？这个题这么难？

四中的一位大神用 trie 上双指针过了 T3，orz。

darkmoon 的分数不知道，不过听说 wg 的 dalao 花 2.5 时 AK 了，orz。

想找 Bonely_Muffin 和 chongzi，结果一个没找到，于是上车回去了，发现自己的身份证和文局盒放考场了，比较慌张，最后是老师帮我拿了回来，真是太感谢了。

晚上重新打了一遍代码发现若干错误，觉得自己很弱智，不过因为一些 C++ 特性没错，希望评测时可以正常运行吧。

T1T2 再 luogu 都能过，发现 T2 没写快读，/bangbangt。luogu 的评分是绿蓝紫紫，真的假的，我这么强？

不管怎么说，感觉要比去年打的开心了一点，希望大家都能打出理想的成绩。

不要挂分球球啦。