CSP 2025 游记

qczrz6v4nhp6u · 2025-11-02 19:43:35 · 生活·游记

省流：荣幸成为 CHAK takes me fly 唯一低于 400 兼唯一低于 350 兼唯一低于 300 选手。

失误用 斜体 标出，严重失误用 粗体 标出。

Day 0

班里下午搞了个大食汇。吃了一碗茯苓糕。

晚上一直紧张焦虑睡不着觉，并且由于茯苓糕的缘故，一点以后大概十几分钟就会干呕一次。结果大概在凌晨 3~4 点才睡着。

Day 1

中午睡了一个很长的午觉，至少起来之后感觉精神挺正常的。

开题，先默写缺省源。观察了一下四题题面，但没有进行基础思考，准备平推。

做 T1。考虑直接贪，不满足限制调整一下就好了。大概 10min 时过了这个题。

做 T2。注意到 2^kn 是可以接受的，考虑爆搜有哪些关键点，在最开始把每一种最小生成树上的边求出来，每次 Kruskal 合并即可。瓶颈在于排序，归并一下做到 O(2^kn\alpha(n)+m\log m+kn\log n)。大概 40min 时过掉这个题。

做 T3。最开始读成可以置换任意多次问方案数了，感觉巨大不可做，但重新阅读题面发现只能置换一次。那把 ACAM 建出来二维数点是不是就好了。但是怎么 L\le 5\times 10^6，但是注意到修改只有 O(n) 个所以分块平衡一下就好了。中间想过 S 组不应该考 ACAM 所以应当有简单做法，尝试建一下正反 Trie，但是定位节点似乎还要写一个字符串 Hash，秉承着能不 Hash 就不 Hash 的原则我弃掉了这个做法。因为忘记构建 ACAM 需要带 |\Sigma| 我此时认为的复杂度是 O(n\sqrt n+q+L) 的。然后因为没有想的很清楚写的很慢，最终大概 1.5h 时才写完，2.5h 时才调出来，尽管这个东西没有任何细节。总之算是过拍了。

做 T4。由于前面调试时间过长大脑已经宕机了，我并没有进行任何的有效思考。突然想起来 T3 还没测效率，我决定回去给 T3 造个极限数据看看跑多快。结果一测发现怎么 10^5 个长度为 20 的串跑了 1.8s？？？？？？？？？观察一下瓶颈发现怎么在于建 ACAM？？？？？？？？？wcnm 赶紧回去卡常。结果发现根本不会卡啊，只是加了一个循环展开跑到了 1.4s。但是想着反正也不会 T4 我选择把 20 分状压后继续卡常。可能是大脑已经宕机的缘故 我并没有想起来我最开始还会了一个只用字典树和 Hash 的做法。结果就是尝试换一种写法，发现跑的没原来快，Ctrl+Z，如此循环。中途仍然尝试想 T4 的一两个特殊性质，但仍然未进行有效思考，当时的脑回路可能是“这个性质看起来跟原问题差不多难，如果我会了这个我为啥还不会正解”。

直到出考场时我 T3 的 n=10^5,L=2\times 10^6 还是跑了 1.4s，T4 还是可怜的指数级暴力。

呵呵。

出场交流了一下发现全世界都 AK 了。回家路上突然想起来那个正反 Trie + 字符串 Hash 的做法，这样就是正宗 O(n\sqrt n+q+L) 了。睡前想了一下发现 T4 是人机题。

呵呵。

说到底还是自身实力不够，凭什么有的人 2.5h 就 AK 了我 2.5h 才写完被卡常的 T3？凭什么有的人一眼了 T4 我没有一眼？

总结一下本次 CSP 出现的问题：

• 思考太慢太粗。
• 写代码太慢。
• 心态不够稳。
• 注意力不够集中，太容易走神了。
• 策略重大失误。
  • 没有在刚开考最清醒的那段时间对困难题进行任何有效的思考。
  • 在某道题未获得期望获得的分数时不敢开后面的题，一味的恋战。
  • 没有进行合理的时间规划，甚至没有进行任何规划。

赛前思考的那么多策略的有实践吗？前几场打了那么多次“嘴巴 AK”的模拟赛，重新打一次真能 AK 吗？原本模拟赛出现的失误，想着“反正正赛不会出现这样的失误”，正赛真的得到改正了吗？

感觉相比省选唯一的进步就是记得检查 freopen 了。

痛定思痛。CSP 爆这么大的雷，希望剩下的四个星期里能有所改进吧。

Day ?

T3 通过了。不知道该高兴还是该愤怒。