CSP-S 2025 游记

· · 生活·游记

Day -1

同学推荐 [BJOI2019] 奥术神杖——也就是一道很板的 AC 自动机上 dp 的题，于是复习了一下 AC 自动机（伏笔）然后写，但是被卡精度调试参数一万年

然后开始和同学研究 [CSP-S 2019] 树的重心，得知了一个很厉害的结论

接着开始研究 CSP 暴力分，先后写了 [CSP-S 2019] 划分 的 64 分暴力和 [CSP-S 2024] 擂台游戏 的 48 分暴力，感觉良好

Day 1

早上

写 【模板】缩点 并得出感想——有向图问题一定不要建双向边（doge

然后看了一会不熟悉的反悔贪心

本来还想写 \operatorname{exgcd} 的板子，但是实在太想颓，看了一眼代码就去 b 站刷视频了

中午

赶往考场

六中校门被我们省实学生占领了

然后开始和同学开始讨论早上 CSP-J 的题，听了一下 T4，发现我好像一眼瞪不出来若干个线段能组成多边形的充要条件？？？诶诶诶 CCF 怎么在题目里给了，这不是【模板】背包问题吗？CCF 真是没题出了

回想去年 CSP-J T4>CSP-S T3，（尽管去年我切了 CSP-J T4（其实被卡常了）但是被 CSP-S T3 肘击），真的感叹远不如去年

但是可能 CSP-J 简单了 CSP-S 就会难，要提高警惕了

下午

我怎么坐在最后面的角落？

怎么就开考了？

先看 T1，这不一眼贪？

发现最多只有一个队的人数大于 \frac{n}{2}，于是先贪心选，如果有多的队就贪心选最小损失值退到 \frac{n}{2} 个人就行了

直接开写！大概 15 \operatorname{min} 过大样例

好，来看 T2

这不是 MST 问题吗？让我烧烤一下，诶我怎么不会？诶诶诶 k 这么小复杂度不会带 2^{k} 吧！好那我会正解了——让我们二进制枚举一下重建的城市，然后直接把这些城市和 n 个点直接的连边以及原图的边拉到一起跑 MST 就行了

直接狂暴开写！嗯嗯？怎么第二个大样例跑得这么慢，让我卡一下常——不对！复杂度怎么是 O(2^{k}(m+nk)\log(m+nk)) 的，炸缸

让我烧烤一下——保留原图 MST 上的边是对的吗？好像我证伪了它？嗯我证伪了我的证伪？好的那就是 O(2^{k}nk\log(nk)) 了，那我会了，直接狂暴开写

于是在 1.5\operatorname{h} 左右通过了大样例

但是怎么跑的这么慢？

查看了一下大样例——不是满的？？？CCF 你无敌了

让我先加个快读——诶怎么跑得这么快？

让我测一下极限数据——4 \sim 5 \operatorname{s}？？？不是说 CCF 不卡常的吗？？？

不急，先在外面分别排序，然后归并一下——怎么变成 O(2^{k}nk^{2}) 了？赶紧回档，直接上 radix_sort，这下真是 O(2^{k}nk) 了

极限数据跑到了 2.5 \operatorname{s}

然后开 NOI Linux 测一下，好像差不多

此时已经开赛 2 \operatorname{h} 了，都怪 CCF 卡常

不慌，2 \operatorname{h} 随便写点 T3,T4 部分分然后直接下班

开 T3——这不一眼字符串多模匹配，恰好我写了 [BJOI2019] 奥术神杖，我将以【AC 自动机】形态出击！

让我们将这被匹配串和匹配串分别放在两个 AC 自动机中，然后在每次询问中直接两个字符串分别在两个自动机上跑，然后找一下每一位两个状态 fail 链上储存的 id 交大小——另外还要限制一下深度——让我尝试用数据结构优化它，嗯 fail 链是 DAG？这不炸缸了，直接退化到 O(nL_{2}) 了？

不急，让我看 T4，好我会 20 分了，让我 dp 一下，怎么转移不了？算了不想了，直接开写

为什么我调了这么久？为什么我的

void add(int &x,int y){
    x+=y;
    if(x>=MO) x-=MO;
}

写成了

void add(int &x,int y){
    x+=y;
    if(x>=MO) x-=y;
}

？？？（这个东西样例测不出，幸亏我瞪出来了，CCF 你无敌了）

只剩 1\operatorname{h} 多一点，不管了，直接开写 T3 暴力跳 fail 链

很快就过了样例，甚至大样例 3 和 4 都可以跑！？一个 3\operatorname{s}，一个 10\operatorname{s}，而且答案都对了，这我就放心了

最后 20\operatorname{min} 用 NOI Linux 测了一下代码，都没有 CE，好耶！

晚上

估分：100+[80,100]+[25,?]+20=[225,?]

出来后 scz 说用 Trie 套 Trie 过了 T3，神秘

问了一下 wwjjrr，他说 400，我说 ?00？他说 400，微距了

ywl 说他 306，本以为他是写了 T3 一个 \log，没想到他是把部分分拼满了，微距了

lys 说他 265，写了 T3 的 L_{1},L_{2} \le 2000 和 q=1

我不成垫底了？？？直接红了

后记

第二天忍不住默写了代码

洛谷：100+80+30+20=230

云斗：100+80+55+20=255

为什么要卡我常！？T3 还是随机分数，我直接自闭了

最终：100+80+45+20=245，T3 跑过了 q=1 的点，CCF 你略微洗白了

什么 fail 链是树？那我会 T3 O((L_{1}+L_{2}) \log^{2} (L_{1}+L_{2})) 了

wwjjrr 曰：“你的字符集难道不是 26 \times 26 的吗？”

哦可以把两个串压到一起！？那我会 T3 O(L_{1}|\Sigma|^{2}+L_{2} \log L_{1}) 了

什么可以直接放在一起匹配？可以做到 O(L_{1} |\Sigma|+L_{2})！？

事实证明只需要在考场上多思考 eps 秒都可以在 T3 拿到远高于 45 分的分数，那我什么？我是肘克吗？