专栏文章

CSP-S 2025 游记

FFQR_
生活·游记参与者 3已保存评论 2

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@mhz4uv0h
此快照首次捕获于
2025/11/15 01:29
4 个月前
此快照最后确认于
2025/12/02 00:30
3 个月前
查看原文

初赛

感觉今年的题很好啊，没有神秘文常、历史题。虽然出了若干个锅，但是完全不影响答题。
98.598.5。

复赛

进入考场后，系统一直没好，直到比赛开始系统都没好，所以比赛延时了 15min。
比赛开始后，电脑仍然没有断网。有个小孩大喊了一句“还能上Deepseek！”。然后主办方立马把网断了。
先看 T1。看到“一半”，立马就能想到，至多有一个选项不满足条件。进而想到，把不满足条件的选项进行调整，一定满足条件。然后就做完了。
再看 T2。2k2^k 枚举后，就变成了最小生成树。看到 nn 较小，mm 较大，可以想到，只保留原图的最小生成树。
跑最小生成树时，写一个形如 1111 个指针一起扫的东西，每次取最小的边权，可以做到 O(2knkα(n))O(2^knk\alpha(n))。
随了一个极限数据，跑了 1.5s。然后加了两条优化：
  • 发现已经连成一棵树时，立即 break。
  • 发现当前的边权和已经超过以前的答案，立即 break。
极限数据跑了 0.5s。
切掉前两题总共用了 40min。然后看 T3。
发现对于一组 (s1,s2)(s_1,s_2)，可以对它们的 LCP、LCS、以及两个串的剩下部分分别考虑。题意可以转化为：
  • 先给定若干组字符串 (a,b,c,d)(a,b,c,d)。
  • 每次询问 (a′,b′,c′,d′)(a',b',c',d')，求有多少组给定的字符串 (a,b,c,d)(a,b,c,d)，满足：
    • a=a′a=a'
    • b=b′b=b'
    • cc 是 c′c' 的前缀
    • dd 是 d′d' 的前缀。
考虑全部离线下来，对每个 (a,b,c,d)(a,b,c,d)，求出它对哪些 (a′,b′,c′,d′)(a',b',c',d') 有贡献。
我先猜想了一个结论：
  • 将所有询问按照 a′,b′,c′,d′a',b',c',d' 的字典序排序。则 (a,b,c,d)(a,b,c,d) 的贡献是一段区间。
过了小样例，但是没过大样例。发现结论假了，有点恼火。
但是立马发现一个新结论：
  • 将所有询问按照 a′,b′,c′a',b',c' 的字典序排序。则对于 (a,b,c,d)(a,b,c,d)，满足前三个条件的询问是一段区间。
这个结论就很正确了。记录每个 (a,b,c,d)(a,b,c,d) 的区间和 dd 的哈希值，扫描线一下就做完了。
此时距离考试结束只剩 50min，决定去打 T4 的暴力。
先打了状压的 2020 分。然后思考特殊性质 A，发现不好做。然后思考 m=1m=1，发现很简单。获得了 3232 分。
预估分数 100+100+100+32=332100+100+100+32=332。

赛后

看了各种群，发现 T3 不保证 ∣t1∣≠∣t2∣|t_1|\neq |t_2|（？？？）。
然后有人说 T4 很简单，有点慌。

11 月 5 日

通过网站的 bug 查到了分数。一分都没挂，100+100+100+32=332100+100+100+32=332。
感谢 CCF 不卡 T3 的 ∣t1∣≠∣t2∣|t_1|\neq |t_2|。orz orz orz。

评论

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

正在加载评论...