CSP-S 2025 最后 4 分钟调出 D 来不及卡空间记

A 正常速度做完了。写完不到 10min，再花了一点时间写了个测样例脚本。

B 的数据范围有点不正常，马上想到 $2^k$ 枚举，但是 $m$ 非常大。想了好久才想到只用保留 $m=n-1$，可能慢了（真的吗，可能就几分钟，但相比于有些题是直觉秒出满了很多）。哦，我会 $O(nk2^k\log(nk))$，好像不行。能不能去做树形 DP 而不是跑 Kruskal 呢？想到了切成若干连通块，但是 $k$ 个特殊点放到一起做好像不行啊。哎不是，我咋还自己发明最小生成树新算法了，似乎发明出来就要拿 xx 奖了，放弃了。（虽然说发现自己发明一些常见问题的更优算法是大概率大概率就可以 skip 这个想法，但是本题树拼上菊花的最小生成树确实有不用并查集的线性做法）。好像可以 DFS 加特殊点。归并排序一下然后跑 Kruskal，$O(n2^k\alpha(n))$，写。感觉会挂就上对拍。花了十分钟，怎么过去这么久了，快 16:00 了。被 B 硬控了，有点慌。

C 很快想到了中间一段不同的要对应上，两边是前缀关系。我竟然在这种情况下没能马上发现 Trie 上祖先关系，是个二维数点，鉴定为压力过大。不过好在马上发现了可以给一个串上可持久化 Trie 放另一个串（本质和二维数点，遍历第一棵树，在第二棵树做加法，第二棵树暴力查是一样的，只是一个离线一个可持久化）。复杂度 $26len$，写+调，花了好久。Bug 可持久化插入写错了，以及没注意到询问在 Trie 上跳到空节点就 break。跑的还算比较快，似乎 17:40 了。不过想 C 的时候看了几分钟 D，所以没有特别慌。

D 应该跟 CF1608F 完全一样的套路吧。DP 很快编出来了。但是转移一直想不清细节。到 18:05 的时候写了个指数+n=m 暴力先垫着。20 多分的时候先建了提交的文件夹，然后继续改。在 26 分左右竟然过了第二个样例。测样例脚本启动，发现有点数组访问越界 -1，简单改了改就过没有越界。但是来不及卡 n^3 空间到滚动数组 n^2。

大概 28 分修改了提交的文件夹。赶紧运行四题的测样例脚本，在距离考试结束 20 秒左右的时候关掉了所有页面，有个文件夹页面卡住了，好像是考试过程中在搜索栏输入导致的，问监考老师他说没事。

$100+100+100+48=\boxed{348}$，唉不是去年怎么试图冲 $348$ 分失败了，这么呼应。

如果不 #define int long long 说不定赢了。但是已经不重要了，结果就是这样了。某同学跟我说快速在乘法用 long long 的方法：* 替换成 *1ll*，好牛，但是只有 3 分钟的时候我应该不敢吧。

被 B 卡了，菜就多练。因为心态不稳导致调 C 的速度下降，调题的时候产生了许多杂念，心态也是实力的一部分。

也许我不给 B 上拍或者给 D 垫暴力就 AK 了，但是我比较求稳。在实力一定的时候高回报必然伴随着高风险（D 题可能没分），自己的策略再回过来看我感觉是没有问题的。有 B 的 $O(n2^k)$ 的树形 DP 做法但是也不能 $k$ 个点一起做，听说可以证明（构造某个特殊的图）没有 $O(m\log m+n\text{poly}(k))$ 做法。

周围有几个同学 AK 了，但是输一点又何妨，我曾经赢过很大一次呢。

能不能像上个赛季一样 NOIP 比 CSP 排名更靠前，省选再靠前。/fendou

此刻成绩 = 过去努力的化石，而非未来成就的保证。

NOIP 加油。I deserve it。