CSP-J/S 2025 游记

昨晚睡了个好觉。

早上 J 组由于在很熟悉的地方考，所以得心应手。

正序开题。

T1：提取数字，排序，切了。

T2：怕写错，于是写了个模拟。

T3：一下就觉得可以贪，写完发现大样例也过了。

T4：一看数据范围，大概率 $O(nV)$，然后正难则反，在 $\max$ 处算贡献，很快写完了。

但是由于我做法有一个 $3$ 的常数（考虑边数 $\ge3$），测大样例的时候发现要跑 $1.2s$，就稍微卡了卡常。

四道题 45min 就写完了，代码也都非常短，为了防止挂分写了好多对拍。

T1 又写了个桶做法，T2 写了个数学做法，T3 写了个自带减枝的 dfs，T4 也写了个 dfs。

剩下的时间在玩 Pr、上厕所、睡觉。

出考场发现周围的人几乎都是 AK。

下午睡过头了，20 几分才到考场，匆匆忙忙写对拍。（但是后面好像都没用到）

睡得有点懵，T1 一下就想到 mayan 游戏，但是已经忘记那道题的做法了。

第二个想法是悔贪，结合题目中写到的 “$\le \frac n2$” 证明了一下是对的就开写了。

T2 一看最小生成树但是还要考虑乡村。

一开始以为是优化建图然后跑一遍最小生成树的题目，但是想了 5min 发现不大行。

随后脑子里就马上跳出 $2^k$ 的影子。一下就想到了 $O(2^k kn\alpha(n))$ 的做法。但是感觉这个复杂度有点危险，想了几分钟想不到更优做法就开写了。

（写完才发现城市和乡村不是一个东西）

跑大样例花了 $1$ 点多秒，但是一看已经过去了 45min 就赶紧跳下一题了。

T3 字符串，心想 S 组应该不会考 AC 自动机或后缀数组什么的（况且我考前没复习非常弱），看到匹配脑子里一下就蹦出了哈希。

看了一下样例解释，大致就想到了把 $y,y'$ 相同的二元组单独考虑。

接下来考虑前后缀，我一开始的做法是每次询问都跑 $2$ 个 trie 树，但是很容易就发现时间复杂度假了（写哈希写一半发现的）。后面画了一个图发现是二维数点，就又匆匆写代码去了。

T3 代码我写得非常慢，感觉非常容易出错。写了双哈希+离线+trie+二维数点，代码写了 $4.5k$（考前没写过这么长的代码）。测大样例发现跑得飞快。

原本计划 16:30 打完 T3，结果 17:00 才打完。

T4 看完题目，感觉做过一道类似的匹配问题，但是这道题限制有点多，毫无思路。先打了 $O(n!)$ 的部分分。深度思考了 15min，没有任何思路，半放弃了。

回去 T2 加了个快读，跑了 $0.7s$，感觉差不多了。

T3 仔细算了下发现空间开错了。空间开正确后又发现爆了。（开了两个 trie 的空间）赶紧优化了一下空间。

最后一会时间，发现之前 T4 深度思考的是类似指数级的做法。赶紧写了个 $O(2^nn^2)$ 的暴力以及 $n=m$ 部分分。

预计 100+100+100+24。

吐槽一下下午考场机房电脑的搜狗老是 shift+space 切换全半角，害得我一个下午切换输入法不下 50 次……

难以相信 CSP 就这样结束了，似梦，似诗……

希望别挂分。

PS：当天晚上 S-T3 空间复杂度算错了害得我提心吊胆了好久。

感觉自己 dp 还是太菜了。T4 题解都看不懂……