CSPS2025

· · 生活·游记

省流：65+80+100+0=245，1= 选手……

感恩 CCF T1 留了 65，T3 没卡 |T1|!=|T2|

进考场看 T1，直接会了开始写，写完过了大样例，linux 压测对了很多直接交，这个时候应该是 20 min。

然后看 T2，注意到 n=10^4 但是 m=10^6，k\le 10 特别小，可以状压 k 的所有状态，但是做最小生成树是 O(m) 的，直接想起来加边不会使得原本不在最小生成树上的边成为新的最小生成树边，于是 m=10^4，然后可以愉快 O(2^knk\log nk)，跑着还蛮快，一看大样例 n\le 10^3 天塌了。造了几组数据跑下来本机 1.6s，因为评测机比较先进所以感觉能过准备扔了。

突然发现是不是排序可以归并来着？然后写 inplace_merge，喜提复杂度少一个 \log 多一个 k 变成小丑。

T3 空间两个 G，因为是提高组排除 AC 机之后只能是 trie。题面一眼没有特别好能直接上 trie 的于是先观察性质。

首先观察到若 S1=S2 没用因为 T1\not=T2，又因为 |S1|=|S2|，则问题可以抽象为从 S1 和 S2 中找到一个最短的包含所有被修改的位的段。S 可能给 T 贡献一定是两者的最短修改段完全相等。于是可以给每对 S 或 T 分成前中后三段，要求中间段相等的 S 和 T 放在一起处理。于是只用考虑前缀和后缀了。

这时候就很好建 trie 了，对于每一组 S，T 的前后缀分别插入 trie 树中。一个 S 对 T 有贡献当且仅当 S 在两颗 trie 树中节点均在 T 对应节点到根的路径上。此时只用暴力维护就可以 O(nq)。

用一点非常简单的数据结构思维，我们发现 n,q\le 2\times 10^5 而不和 L 同阶，直接提示我们上数据结构。这种两颗 trie 树等价的，可以直接在一颗 trie 树上游走，维护另一颗 trie 树的贡献。于是我们分别建 trie 后游走前缀 trie 树，维护当前在前缀 trie 树上的点到根的所有 S 终止节点，在后缀 trie 树上的贡献，显然一个 S 能贡献的是子树内的 T 节点。查询就直接查询当前后缀 trie 树上对应 T 节点的权值即可。

所有需要维护的东西，即两颗 trie 树，其中一颗的 dfn，以及一个树状数组支持区间加减单点查询。

最后一分钟调出来了过了所有大样例，没来得及写 (n+q)\log 写的 L\log。

回家的路上群里面在发 |T1| 可能不等于 |T2|，遂直接破防，相当于我花了两个小时的时间写了一个小丑东西，最后出题人随便卡卡就一分都没有，但是想到双 trie 直接做暴力可能都有至少 50 分。

T2 的时间复杂度假了，比正解多了一个 k^2。

T1 的实现假了，被洛谷数据卡了 20 分，被云斗卡了 30 分，也是理论上可以 0 蛋的。

完全没有想过自己真的可能以能在人生中可能的最后一场复赛中获得这样的成绩。

我初二的时候，参加 CSPS2022，获得了 150 分，那个时候我图论只会最小生成树，数据结构只会不带懒标记的线段树。于是我在 T1 写下了 dfs 判环，在 T2 写下了 8 棵我仅会的“仅查询线段树”，获得了 50+100+0+0。

我初三的时候，参加 CSPS2023，获得了 150 分。那个时候我还是只会写最小生成树，以及多会了一个树状数组。于是我在切掉唐 T1 之后花了 3 个小时去写大模拟 T3 的 65 分，没调出来最终获得了 15 分，以及 T2 写了 35 分的 n^3。

我高一的时候，参加 CSPS2024，获得了 300 分。那个时候我基本把提高的算法补完了。非常幸运，我在切掉唐 T1 的时候，一眼发现了 T2 就是暑假集训时候讲的贪心，直接就糊过去了。T3 发现了 dp 以及其优化方法过后，使用了“新学会的线段树”切掉了。我那时很想去 WC，因此打的很激进，我锚定了 T4 的 64 分准备冲，结果比赛结束了还差一点没写完，最终就是 T4 获得了 0 分。可笑的是，如果 T4 写了最低的暴力，就可以去参加 WC。

我高二的时候，参加 CSPS2025，获得了 80 分。

在最想多说的时刻，却一时一直一再语塞，令人唏嘘。