CSP-S 2025 游记
FQR_
·
·
生活·游记
初赛
感觉今年的题很好啊，没有神秘文常、历史题。虽然出了若干个锅，但是完全不影响答题。
## 复赛
进入考场后，系统一直没好，直到比赛开始系统都没好，所以比赛延时了 15min。
比赛开始后，电脑仍然没有断网。有个小孩大喊了一句“还能上Deepseek！”。然后主办方立马把网断了。
先看 T1。看到“一半”，立马就能想到，至多有一个选项不满足条件。进而想到，把不满足条件的选项进行调整，一定满足条件。然后就做完了。
再看 T2。$2^k$ 枚举后，就变成了最小生成树。看到 $n$ 较小，$m$ 较大，可以想到，只保留原图的最小生成树。
跑最小生成树时，写一个形如 $11$ 个指针一起扫的东西，每次取最小的边权，可以做到 $O(2^knk\alpha(n))$。
随了一个极限数据，跑了 1.5s。然后加了两条优化：
- 发现已经连成一棵树时，立即 break。
- 发现当前的边权和已经超过以前的答案，立即 break。
极限数据跑了 0.5s。
切掉前两题总共用了 40min。然后看 T3。
发现对于一组 $(s_1,s_2)$，可以对它们的 LCP、LCS、以及两个串的剩下部分分别考虑。题意可以转化为：
- 先给定若干组字符串 $(a,b,c,d)$。
- 每次询问 $(a',b',c',d')$，求有多少组给定的字符串 $(a,b,c,d)$，满足：
- $a=a'
考虑全部离线下来，对每个 (a,b,c,d)，求出它对哪些 (a',b',c',d') 有贡献。
我先猜想了一个结论：
- 将所有询问按照 a',b',c',d' 的字典序排序。则 (a,b,c,d) 的贡献是一段区间。
过了小样例，但是没过大样例。发现结论假了，有点恼火。
但是立马发现一个新结论：
- 将所有询问按照 a',b',c' 的字典序排序。则对于 (a,b,c,d)，满足前三个条件的询问是一段区间。
这个结论就很正确了。记录每个 (a,b,c,d) 的区间和 d 的哈希值，扫描线一下就做完了。
此时距离考试结束只剩 50min，决定去打 T4 的暴力。
先打了状压的 20 分。然后思考特殊性质 A，发现不好做。然后思考 m=1，发现很简单。获得了 32 分。
预估分数 100+100+100+32=332。
赛后
看了各种群，发现 T3 不保证 |t_1|\neq |t_2|（？？？）。
然后有人说 T4 很简单，有点慌。
11 月 5 日
通过网站的 bug 查到了分数。一分都没挂，100+100+100+32=332。
感谢 CCF 不卡 T3 的 |t_1|\neq |t_2|。orz orz orz。