CSP2025 游记

__O_v_O__ · 2025-11-15 18:11:25 · 生活·游记

Day -1

初赛过了。

Day 1

J

AK 了。

S

开题，看 T1，发现是个 ad-hoc。看起来很典，很想要猜结论的样子。想到了之前一道 AGC 的题，大概确定了是反悔贪心。然后就猜测先全部选第一个社团，后面反悔贪心再改决策；有可能改了之后第二、三个社团超人数了，再对这两个跑一遍反悔贪心。但是写了写发现大样例没过，好像正好把我的做法 hack 掉了。我尝试往除了贪心的其他方面想，但是没有想出来。回到我的贪心做法，我又想不出来有哪些地方可以改进，开始有点急。过了 1h+，我先把 T1 放弃了，直接去看 T2。

读了 T2，发现 k\le 10，可以爆搜。但是考场上把 2^kn 看成了 10^8（本来应该是 10^7），于是感觉爆搜做法很没有前途。而且由于我放弃了爆搜做法，就没有找到有用的边只有 n-1 条的性质。后面往图论的方面想了一下，发现完全没有思路。于是先把 T1 80 和 T2 48 打完了。然后去看 T3。这时候心态很爆炸，因为不确定自己能不能做出来 T3，T1、T2 又感觉完全没有思路。

看 T3，花了 10min 看出来了询问串需要和替换串中间部分相同的性质，然后把问题转化成了求 a 是 c 前缀，b 是 d 前缀的 (a,c) 组数。但是到这里我就卡住了。后面想了很久哈希之类的东西，花了很长时间，突然反应过来前缀有关的最重要的东西是 Trie。马上把询问搬到 Trie 上，发现就是求两棵 Trie 上两段根链的并，其实这题就是个数据结构题。想到离线询问挂在点上，再 DFS 一遍就做完了！可是因为我思考花了太长时间，导致只有大概 1h 给我写代码，然后我写完只剩下大概 30min，调了 15min 没调出来，自己感觉以当时的精神状态也没法调完了，所以还是去把这题的 25 分暴力和 T4 8 分暴力打完了。

出成绩，80+48+25+8=161，卡着线一等了。

感觉没考好的主要原因有一些：

• T1 花了很长时间，还没有做出来，这对我做 T2 和 T3 的心态有非常大的影响。如果 T1 能 20min 之内写完，可能我 T2 也不会有太大问题。其实 T1 只需要把我做法中先全选第一个改成先选贡献最大那一个就行。感觉对于这种整道题只有一步，但是没有什么思考路径的思维题，我要得出正确的结论很困难。

• T3 虽然思考出来了，但是花了太长时间。赛后再看我的思考过程，感觉每一步转化、处理都非常自然，应该很顺利地想到才对。但是考场上不知道为什么就是花了很长时间，特别是把问题搬到 Trie 上那一步。可能有一部分心态原因，也可能是平时做题思考的速度、节奏就比较慢，还可能是练题时没有积累一些处理的普遍思路（比如前缀问题用 Trie 做）。