CSP2025-J/S 总结

· · 生活·游记

早上 7:20 从家出发，7:35 到达了重庆一中，此时距离集合时间 7:40 只有 5 分钟。但在门口没有找到几个人，问了问保安，才发现是南门，火速赶到西门，初一教练 GM 已经带人进去了。冲到科技楼下面，刚好拍合照，我挤到 wyh 旁边的时候正好拍照。

到 4 楼的时候人很多，都挤在名单那块，就跟旁边同学闲聊，2 班几个同学故意一直问带队教练 GM 如果电脑死机了怎么办。好不容易等人少了点看看名字，在四机房。

进入考场，在考室门口排队过安检（？快轮到我了抬头一看发现排的是三机房。早上起来脑袋有点晕，跑到四机房坐下吃了点巧克力感觉要好一点了。

为什么 vscode 没有 CPH。

打了个带 freopen 的主函数，放在四个 .cpp 里面，静等发题。一个老师跑过来跟我们说解压密码，密码大概是 ShangShanRuoShui 太突出了，导致那 4 个数字最后才说，听得整个机房的人云里雾里的，好在最后把密码发下来了。

看 T1 的第一秒，桶排序一眼秒掉，代码 2\operatorname{min} 就写完了，写着写着觉得可能有答案为 0 的情况，直到看见 数据范围 才发现 CCF 是如此的善良。最终时间复杂度 O(n)，预期得分 100\operatorname{pts}。

T2 感觉甚至比 T1 还简单，数学方法可能一眼就看出来了。但是赛后想起来有可能模数 n 写成了 m，因为两种都能过所有样例，赛时也没搞对拍，毕竟对拍程序感觉和答案也没有什么区别。最终时间复杂度 O(1)，预期得分 100\operatorname{pts}。

T3 看到异或的一瞬间，就知道是前缀异或和，因为似乎题目只能出前缀异或和相关的吧 其实平方过不了才应该是主要原因。一眼感觉就是贪心，考虑如果当前能够满足有一串异或值等于 k，那么应该直接 ans++，因为后续值的数量更多肯定是更有可能有满足答案的情况吧。想了一下按照思路遍历一下就好，把前面的异或结果存储起来再与当前的值异或就可以找到答案的值。遍历之前出现过的异或值肯定会 T 飞，故直接用 set 存储之前出现的异或值中有没有 k\oplus sum，甚至还有方便的 lower_bound 可供查找 考完得知可以桶排。最终时间复杂度 O(n\log_2n)。

此时时间仅仅过去 30\operatorname{min}。

果不其然 T3 WA 了，查错半小时发现错因竟是位运算优先级太低，果断以后位运算都要打 ()。预期得分 100\operatorname{pts}。

即使 T3 弱智错误查错半小时，但仍有两个半小时可供 T4 挥霍。总感觉每次考试都必有一题是 dp，看了一眼发现 dp 能做，果断 dp。直接甩出三维 dp[i][j][k]，O(n^4) 的空间复杂度让计算机高兴坏了。直接开滚动，两个小时写满草稿纸试图降成一维，始终不行。最后半小时灵光乍现 干嘛非要 n -> 1，n -> 2 不好吗。但还是只滚了一维，能得 80\operatorname{pts} 其实也挺不错了。结果一紧张少打了个 0，数组没开够。CSP-J 预期得分 368\operatorname{pts} 遗憾离场。

中午抢到抄手，发现后面排了一长队人，吃完了 zyc 和 wyh 才拿到饭。回去睡了一觉，一觉醒来天塌了，已经错过了集合时间。

S 组 T1 一看 就逝 就是 dp。打了部分分之后打不动了，就去看 T2 了 虽然后来标答是贪心。最终时间复杂度 O(n^2)，预期得分 60\operatorname{pts}。

T2 一眼 MST。复杂度 O(2^k((m+nk)\log_2(m+nk)+\alpha(m+nk))) 打完发现最后一个大样例会 TLE。运用一些神奇的优化方法竟然通过了这个神奇的样例，最后得分 [64,100]\operatorname{pts}。最终时间复杂度 O(2^k((m+nk)\log_2(m+nk)+\alpha(m+nk)))。

T3 看起来像 KMP？但应该会超时，又不会 AC 自动机，直接看 T4 去了。

T4 直接打局部性质，大样例一直对不了，最后才发现样例中含有 c_i=0 的情况，今后一定要仔细观察数据范围！预期得分 4\operatorname{pts}。