CSP-J/S 2025 游记

初赛模拟豪取机房 rk 倒一 /ll

上午 J 组，也许比去年难一点？只提前了 10min 做完，最后一道补全程序还是有点意思的，不过没有严格证明，总之理解一个大概就好了。

下午 S 组，面到了一些学长，至于题目，感觉比去年简单，虽然做得慢，但前两个大题只错了 2 个判断，剩下的错都在最后一个程序阅读里，看了几遍题意和代码实在不大懂，使用排除法 + 猜等方式选出答案，对了 3 个，那很好了。

询问同学估分，一问 97，再问 97，又问 100，一堆人 S1 > J1，那我是什么躺尸，又要垫底了 /ll

有人 J1 判断题打 √/× 写成 T/F 了，好在 S1 及时发现并修改了问题，不会真出现 J 没过 S 过的人吧 /jk

欸这个 whk 怎么这么坏

第一轮出成绩日，J1 95，S1 91，发现 S1 90+ 也没那么大众，那很好了。顺便得知第二轮的比赛日期是我生日，不是哥们。

欸这个 whk 怎么这么坏

CQ J 分数线 54.5，S 分数线 49.5，不是哥们，又这么低？不过我感觉复赛一等线又要起飞了。（伏笔）

脱产 whk，据说我们考完复赛就要期中，能不能不去考啊（

联考卡题时：这啥玩意儿怎么这么难想了那么久都不会能做我吃好吧

看题解后：这啥玩意儿怎么这么简单还想了么久都不会我诗人我吃好吧

别样的板子题大赛，发现自己还没学圆方树和动态 dp，要完蛋了！于是下午把圆方树学了，由于 manacher 降为了提高组知识点，所以也学了，然后发现很久没考串串题了，S 组不会真要考吧（伏笔）。

应该是最后一年打 J 组了

T1 简单贪心。

T2 简单模拟。

T3 读错题卡了会儿，只要熟悉异或的结论那就是简单题，记下当前同一前缀异或和的最靠后的位置优化 dp 的转移即可。

感觉 T4 比 T3 更典，考虑动态规划，将 a 从大到小排序，那么最前的位置一定能作最大值，第二维记录和会有大量无用状态，考虑记当前长度和与两倍最大值加一的差，显然状态数减至 5001（差小于等于 $0$ 的情况都能视作 $0$），由于害怕空间不够于是开了滚动数组。

总之 50min AK，感觉今年 T4 比去年 T4 简单好多。

T1 比去年难不少啊，虽然反悔贪心挺好想的，但感觉很容易卡题，由于犯了一些糖代码打得很长，20min 做完。

原计划是 1h 过 T1/T2，但我不幸卡 T2 了，有些措手不及。

T2 想了半天才意识到要先做一次 MST 把普通边的边数缩成 $O(n)$，然后想了好几个做法都否掉了，其中包括单独处理 $2^k$ 种城市化状态，但显然每次排序复杂度是 $O(2^k n \log n + m \log m)$，于是只能一起处理，复杂度降至 $O(2^k n k + m \log m)$，时间 1e8，还带并查集的阿克曼，空间也有 1e7，比较极限，但感觉不好优化了，这时候还把开始时间记成 14:00，以为 T2 做了很久，心态不是很好，写了写调了调就过了大样例，静态查错几遍，1h10min 做完，然后发现只过了 1.5h，心态好了很多。

原以为 T1/T2 超过预期时间已是较严重的失误，没想到竟是噩梦的开始。

开 T3，怎么真是串串题，这一年几乎没怎么练啊，比较紧张，想了一会儿感觉要用哈希，然后没太大进展。

先看一眼 T4，感觉只会暴力状压，没观察出任何性质，于是扔了回去看 T3。

继续想 T3，在还剩 1h 多的时候大致想到了一个思路：对于每个 $t_1,t_2$ 判掉 $|t_1| \ne |t_2|$ 的情况，枚举 $t_1$ 替换的右端点，可以先用 $O(\sum_{i = 1}^{q} |t_{i,1}|)$ 的复杂度确定这个右端点最左的位置，然后就是串串题的经典套路：由已知信息优化求未知信息的复杂度，我们考虑找到每个的右端点 $r$ 在 $t_1$ 上能经过替换变为 $t_2$ 的最靠左位置 $l$，设此时替换的字符串二元组是 $(x,y)$，当 $r$ 确定且存在合法的 $l$ 时，$(x',y')$ 也能通过选择 $t_1$ 的 $r$ 为右端点进行替换，当且仅当 $x'$，$y'$ 分别是 $x$，$y$ 的后缀，且满足 $x$，$y$ 前缀上的其它位置有 $x_i = y_i$，证明显然。那么我们考虑先按 $|s_{i,1}|$ 的大小从小到大排序，设当前枚举到 $s_1,s_2$，求出满足 $\forall i | 1 \le i \le k，s_{1,k} = s_{2,k}$ 的最大 $k$ 值，从后往前地进行哈希，就能找出 $s_{i,1}$ 的所有后缀的哈希值（当然此时要同时对 $s_{i,2}$ 进行哈希，与 $s_{i,1}$ 的处理方式类似），合理运用 map 就能用 $O(L \log L)$ 完成预处理。那么问题只剩求所有 $t_1$ 的每个 $r$ 的 $l$，好像可以用 ACAM 做到 $O(L)$，但我一年没打 ACAM 了，还剩一条路就是倍增哈希（显然倍增直接匹配串是困难的，但倍增/二分 $t_{1,l} \sim t_{1,r}$ 是否为某个 $s_1$ 的后缀就具有单调性了，求出这个后缀以后其它信息也能更容易的求出了），总复杂度 $O(L \log^2 L)$。

然后发现 $L \le 2000$ 是一个档，下一个档 $L \le 10^6$，接着心态就爆了，我完全没想到思考这么久的做法竟与暴力一个分，此时大脑一片空白，完全无法思考，过了一段时间立即反应过来再不拼暴力就真的爆了，感觉这个东西很难优化，只好拼完 $L \le 2000$ 的暴力就跑路，这东西只有 $25pts$。

立即打完 T4 的 $O(n2^n)$，这玩意儿只有 $20pts$，还不确定挂不挂，有点崩溃。

这么 jb 难一等线起飞个屁。

忘了

老师说半期选择性参考，你考不考，你死都得考。

忘了

J 没挂

S T2 $100$ --> $80$，虽然不是正解，但放过 $O(2^km)$ 卡掉 $O(2^knk)$ 这个操作我确实没看懂。

总之就是 $100 + 80 + 25 + 20 = 225$，烂完了。

忘了

教练发话不考半期，这很好了。

T2 卡卡常过了，lg 最慢点 1.2s，T3 打了 6.1KB，二维数点做法还是太长了。

忘了

把 S T4 补了，我一直以为我想到的做法是 $O(n^4)$ 的，后来发现其实是 $O(n^3)$，不对啊怎么跑了 16s，卡卡常变成 6s，咋还是这么慢 /fn

忘了

一年过去差点把 S 1= 丢了，现在状态真的很不好，继续加油吧