专栏文章

CSP-S 2025 游记

zzhoumurui
生活·游记参与者 5已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@minumr65
此快照首次捕获于
2025/12/02 08:37
3 个月前
此快照最后确认于
2025/12/02 08:37
3 个月前
查看原文
是不是该写游记了。

9.19（距离 CSP-S1 还有 1 天）

放一张图，转自 Moya_Rao。注意到图中出现了我。

9.20（CSP-S1）

没什么可写的吧。
You have no egg!

10.31（距离 CSP-S2 还有 11 天）

CSP-S RP++！

11.1（CSP-S2 当天）

上午一觉睡到十点，起来打板子。
打了三种 tarjan 就去吃饭了。吃完睡个午觉就退了房，坐车到考场。
进场先打缺省源，打完缺省源发现题目已经发了。于是看题。
T1 一眼唐题，只要先贪心分配然后如果有超员的部们再贪心分给别的部门就可以了。二十分钟写完开 T2。
T2 注意到数据范围 k≤10k \le 10，很快考虑枚举哪些乡村要升级。但是如果每次都求一遍最小生成树的话，复杂度就直接炸掉了。
T2 想不出来去看 T3。注意到这个替换就是纯诈骗，因为只能替换一次，所以真正有用的就是 t1t_1 和 t2t_2 去掉最长公共前缀和最长公共后缀的部分。
推了一下感觉纯唐题，直接上一个 trie 套 trie 就做了。但是开始写的时候，发现并没有这么简单，因为 s1s_1 和 s2s_2 没用的部分也需要和 t1t_1 和 t2t_2 没用的部分匹配上。
先去想 T2。想了一下觉得原图中最小生成树以外的边是没有用的，就先求了一遍最小生成树把它们筛掉了。那之后就只剩下 knkn 条边可能会用到，就有了一个 O(nk2klog⁡n)O(nk2^k \log n) 的做法。
大样例跑得飞快，感觉不对劲。发现大样例并不是极限数据。自己搓了一个极限数据，发现跑了两秒。
思考了一下能不能优化，无果。于是随手加了个剪枝，一秒，跑路。
瞄一眼 T4。感觉很困难，而且部分分很碎。还有两个小时，重新看 T3T3，我觉得它是可做的。（记住这句话）
考虑将 s1,s2s_1,s_2 分解成 CADCAD 和 CBDCBD，t1,t2t_1,t_2 分解成 EAFEAF 和 EBFEBF，那么 s1,s2s_1,s_2 能贡献 t1,t2t_1,t_2 当且仅当 CC 是 EE 的后缀且 DD 是 FF 的前缀，也就是 C∣DC|D 是 E∣FE|F 的子串（∣| 是占位符）。
然后感觉可以直接上 AC 自动机做（实际上就是多测版的 P3808）。这时还有一个小时，光速开写，花了半个小时写了个大概。侧样例发现没过。
发现不能直接在自动机上跳，每次跳了以后需要统计从当前位置沿着 fail 树向上跳经过的位置的答案。但是如果暴力向上跳的话，每次询问都会花费 O(Trie 树大小)O(\text{Trie 树大小}) 的复杂度，那么它就假掉了。
紧急思考了一下能不能优化它。但是还有二十分钟，只能考虑暴力跳 Trie，O(L1q)O(L_1 q) 跑路得了。
结果样例 22 RE 了。在剩下的时间里没能调出来，耻辱下播。
检查了下文件写没写错，22 年就是因为文件写错痛失提高组二等奖，血的教训。
100+[80,100]+0+0=[180,200]100 + [80,100] + 0 + 0 = [180,200]。感觉 77 级钩没有了，而且是在 JX 毫无竞争力的一个分。
出来之后再次雷击，因为有学弟把我 T2 的做法 Hack 了，认为把最小生成树以外的边全叉了是错的，应该保留和最小生成树最长边相等的边。（当然后来询问了队爷，他 Hack Failed 了。）
再后来，发现样例 22 RE 是因为我没判 t1,t2t_1,t_2 不等长，血亏若干分。
啊别的不说了，等 CCF 开死亡证明吧。

11.2 （CSP-S2 后 11 天）

还原了一下在考场上写的代码。
T1 过了。
T2 冲过了民间数据，最慢点 600ms。不加剪枝的话最慢点 1500ms，看 CCF 会不会卡我了。
T3 没必要测了，样例都 RE 肯定爆零了。

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...