CSP-S 2025 游记

· · 生活·游记

CSP-S 游记

出分了，感谢 CCF 神仙评测机。

最有节目效果的一集。

CSP 经典环节：早上睡大觉。本次的起床时间是 11:00，打破了以往 CSP-S 的纪录！（

起床后直接吃午饭，然后继续午睡，13:00 前往考场。

由于正在举行广交会，琶洲大桥上少见地在中午出现了堵车。幸好提前出门。

考场在广大附，艺术楼 101。

8:27，允许解压缩。然而我的位置离公示密码的白板太远，看清密码花了不少时间（

接下来进行了一圈配置（虚拟机、Dev-C++、控制台、etc.），大概 8:32 开始做题。

打开 T1。立刻猜测每个人先取最大然后调整的策略，但一时半会想不到证明。思考了一小会决定先写。写完过一会证出来了。测了大样例没问题，跳过对拍。

打开 T2。获得 O((2^k\alpha(n)+\log n)(m+kn)) 做法。猜测原图只有最小生成树上的边会被使用，稍加思考完成了证明。此时达到 O((2^k\alpha(n)+\log n)kn)，算了一下在 ?\times10^8 附近，决定写这个。完成代码部分后发现大样例不是极限样例，于是手造了一组极限样例，跑了 800ms。同样跳过对拍。

打开 T3。题意转化成“给一个串以及一个子区间，求选定一对 s 和一个 t 上子区间的方案，使得选定的子区间包含给定的子区间，且选定子区间与 s 相等”。至此大约是 ACAM 上二维数点问题。思考一会后发现设字符集为 26^2 即可把两个串变成一个串，于是变成 Fail 树上链求和问题。目前是 O(L\log L)，感觉常数不大（？）然后开始写。测了大样例发现跑了 1.1s 左右。想到去年 NOIP 时我在同一个学校考试，考场机器测试我的 T4 时跑了 2.7s，但是 CCF 处通过了，我本机跑了 1.5s，洛谷上跑了 1.2s，我开始认为这是机器太烂了。感受了一下看起来数据不好造，于是暂时跳过卡常和测速，开 T4。

人是铁饭是钢，我感到饿了，于是申请去考场外吃零食。

打开 T4。n=500、排列计数提示三维 DP。有一维用于 DP 顺序（下标），一维用于要求计数的东西（即有多少个人被录取），剩下一维只能用于优化计数。思考了按下标 DP 还是按值 DP，发现由于每个位置的合法决策和前方的录取情况强相关，暂定按下标 DP。接下来的问题是怎么把已经选择的人的信息压到一维里面。发现可以使用一个经典技巧：在某个位置即将放一个“心理素质强”（即 c_i 足够大）的人时，不进行决策究竟放哪个人而是打一个标记延后决策，在被拒的人数达到 c_i 时再选择一个标记位置把 i 放过去。于是 O(n^3) 状态，O(1) 转移，代码也很好写。（T4 怎么做得比 T3 快？）

于是，开赛两小时二十分钟左右，我自认为 AK 了。上厕所+吃零食以庆祝。

配置 checker，检查所有题目的文件 IO，上 NOI Linux 开 -fsanitize 测大样例。（小技巧：在虚拟机开机前把考场的 D 盘配置为共享文件夹，这样可以实时测试工作环境中的代码，省去了复制到虚拟机中的环节。）基础检查结束，我决定开始 T3 的卡常。稍微卡了一会常，把本机大样例运行速度压到了 950ms。

思考了一下，造了一个把我的 T3 卡满的数据（n=10^5，s_{i,1/2} 为长为 25 的、字符在小写字母内均匀随机的字符串，m=1，t_1=\texttt a^{2,500,000},t_2=\texttt b+\texttt a^{2,499,999}）。发现跑了 1.7s 左右。观察考场机器配置，CPU 标注运行速度为 3.7GHz。观察评测机配置，CPU 标注运行速度为 3.9GHz。感觉倒闭了。此时剩余的时间还有 80min。

在一些测试之后，我发现我的 O(L) 建立 AC 自动机和 O(L\log L) 倍增差不多快。我开始认为性能瓶颈是 unordered_map 存储的 AC 自动机建立的时候进行了太多次访问。试图改为 cc_hash_table 与 gp_hash_table，发现更慢了。剩余 70min。

我突然发现，其实不需要令字符集为 26^2：只要把两个小写字母排在一起就能达到一样的效果，于是可以把 u-map 去掉，改用数组存储。稍加思考，我认为这是好的，于是立即开始写代码。由于时间紧迫，我决定写 O(L\Sigma) 的建立 AC 自动机。我认为这个 AC 机相对于 O(L) 的方法更好写，且性能损失不大。

写完了，剩余 45min。发现还是过不去，于是彻底红温。开始把矛头转向倍增。我开始认为，也许把询问离线，在 Fail 树上 DFS 时记录到根的链的信息可以做到 O(L)。很遗憾，这是错的。我发现了这一点后，把 DFS 的部分改成了基于树状数组的修改查询，发现自造样例跑了 2.2s。此时剩余 20min。已绝望。此时，我把 T3 改回了最初的版本。

我转而继续进行基础性的检查，时而又回头看看 T3 的代码，试图找到可以进行常数优化的位置。最后也只能看着电脑上的时钟走到 18:27，停止答题，关闭所有窗口。

结束了。假设我 T3 L=5\times10^6 的点全都 TLE，我的估分是 100+100+60+100=360。

出考场问了一圈，周围有若干 300+，Dairuichen007、OtomachiUna AK 了。有一位学弟的 T3 和我使用了类似的做法。他设法把后续的倍增优化掉了，并且令字符集为 26，用 map 存储自动机，跑得很快，大样例不到 0.1s。反观我的 AC 自动机，在大样例下仅仅建立自动机就花了 700ms 左右。这是为什么呢？？？

我向同学报出我的估分的时候，他们都感到疑惑，并询问我为什么做不出 T4。我满脸问号。与同学们交流后，我发现我 T3 还是没有做足观察，其实可以进一步转化成标准的多模式串匹配问题。

在 LA 群里，我发现我许久未见的朋友 Disjoint_cat 在线。我们进行了交流。他似乎没有判 |t_1|\ne |t_2|。默哀。

我在 LA 群里大致描述了我的 T3 遭遇。在一秒数条的消息洪流中，我仍然收到了三个 “拥抱” 回应表情。

在考场附近的饭店吃饭后，我决定前往珠江边散心。全运会+广交会+周末 buff 叠满，超级多人。而且由于全运会彩排，海心沙公园进不去了。于是我沿着珠江靠近天河区的岸边散步，21:30 返程。

没能 AK 有些遗憾，但是这个分应该够去 WC 了。希望别挂分。

11 月 6 日 20:00，我通过申诉通道查分。怎么 T3 过了？？？上厕所+吃零食以庆祝。

水群，各位群友也出现了反向挂分的情况。据说 T2 的 O(2^km\log m)、T3 的 O(L\log^2L) 都可以通过，而且 T3 没有 |t_1| \ne |t_2| 的数据。CCF 真神了。

upd：

ios::sync_with_stdio(false);
......
while(m--){
    string x,y;
    cin>>x>>y;
    if(x.size()!=y.size()){
        puts("0"); // 这里！！！
        continue;
    }
......

于是我在 |t_1|\ne |t_2| 的时候也会挂。幽默。