CSP-S 2025

· · 生活·游记

T3 我将获得随机分数，第一次这么希望数据造水。

如果分数可以看的话我就把游记贴上来。

下面是原游记，考完写的。

打的还行，心里没底，[300,400]，出分再看。

开场先看题，T1 挺简单，T2 没啥思路，T3 很奇怪，T4 看起来很难。

写 T1，T2 发现 m = 10^6 比较假其实有用的只有 nk 条边，时间复杂度 2^k kn \alpha 直接做，极限数据跑 1.5s，时限 1s，相信 ccf 机子。

T3 想了一想发现只需要 trie 就够了。写了很久，一遍过大样例，最后发现其实是大样例很水，这是后话了。极限数据 2s，原因是我看错数据范围成原来的两倍了。

此时过去 2.5h，看 T4 一会儿想出一个 n^4 的做法，本着写暴力的想法试试，写完抱着侥幸心理测了一下 500 的大样例结果发现跑在一秒以内？我整个人都懵了，心止不住地狂跳，研究一下发现这份代码均摊一下其实是 n^3 的！我这就 AK 了？？梦里也不敢这么想。

乐极生悲了说是。后面 20\text{min} 我就开始检查，结果最后两分钟的时候才发现 T3 我没有判 t_1,t_2 长度不相等的情况。想改的时候由于很急并且监考老师不让我写了，就没有改。这既可能导致诡异的溢出又可能让答案变大，完全不理解大样例是怎么过的。

最后 T3 数据里面没有 \left|t_1\right| \neq \left|t_2\right|，但是我一个 q 写成 n 挂了 10 分，令人唏嘘。

最终分数：100 + 100 + 90 + 100 = 390。