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 题解都看不懂……