CSP-S 2025 游记：拼尽全力无法战胜人行道吗？

我永远不会忘记这沉重的一天 QwQ。

中午吃完饭坐车去考场。13:32 到了考场门口，下车。

然后，我在下车的时候，直接踩进绿化带并且没有注意脚下。

那个绿化带里面有个大坑？？？我踩进去摔了一跤。。。

当时我正在背包，双手被牵制着，于是我像个人机一样往人行道上倒。

然后就摔惨了。当时情况比较严重，没来得及拍下事故现场。

带着伤强行走到了考点门口（谁把路程设设么远啊），然后请校医帮忙处理了一下。

起码没骨折，成功参加了比赛。

——你怎么摔成这样的？

——走路摔跤，很难吗？

——摔成这样挺难的。

环境：高价值目标
【 I 】双手受伤，灵活程度降低 $15\%$。
【I I】双手受伤，灵活程度降低 $30\%$。
【III】双手受伤，灵活程度降低 $50\%$。

源石环境：侵蚀
【 I 】双腿受伤，灵活程度降低 $20\%$。
【I I】双腿受伤，灵活程度降低 $40\%$。
【III】双腿受伤，灵活程度降低 $55\%$。

环境：交战区
【 I 】前往考点所需的步行距离延长。
【I I】前往考点所需的步行距离大幅延长，且无法使用电梯。

环境：施工需求
【 I 】禁止使用草稿纸

难以想象以前随手写的 OI 赛制危机合约变成回旋镖打到了我自己身上。

听说还有同学点了【III】级的高价值目标，不知道他考得怎么样。

T1，贪就完了。

T2，开场先猜复杂度，想必是 $O(n2^k)$ 或者 $O(n2^k\alpha(n))$。

证明一通发现证的是经典结论：$W(MST(E_1\cup E_2))=W(MST(MST(E_1)\cup MST(E_2)))$。

此处 $MST(E)$ 表示以 $E$ 为边集跑最小生成树，返回值是树边构成的边集。$W(E)$ 表示 $E$ 中所有边的边权和。

先排序，然后 dfs 枚举，在 dfs 的过程中不断用证过的结论，保证边集大小始终是 $n+\epsilon$，总复杂度是 $O(n2^k\alpha(n))$。你别说今年 T2 还是相当魔怔的。

$n\leq 10^4$，不加按秩合并感觉还会更快，懒得写了下一题。

T3，稍微处理一下字符串，等价于给定若干 $s_i$，询问 $t_j$，输出有多少 $s_i$ 是 $t_j$ 的子串。

并且保证每个 $s_i$ 至多在每个 $t_j$ 中出现一次。

2G，那就是 AC 自动机模板题。时空都是 $O(L_1\Sigma+L_2)$。区区 $2\times 10^8$ 怕什么包过的。

T4，一开始有点蒙，但是看到数据范围是 $500$。

记 $d_x$ 表示 $c_i=x$ 的人数。

DP 是一定的，多半要记录：考虑了前 $i$ 个位置，有 $k$ 个人没被录用。

但是只记录这些信息当然是不够的，所以大概要再加一维。着重考虑这一维是什么。

发现只需要再记录一下，当前有 $j$ 个位置还没有放人，这些人必须满足 $c_i>k$。

朴素转移就不说了。特别地，当 $k\to k+1$ 时，这 $j$ 个位置中会有若干被填上 $c_i=k+1$ 的人，直接枚举一个 $t$ 表示有多少个这样的位置，系数是组合数。

表面 $O(n^4)$，实则 $t\leq d_{k+1}$，所以枚举的 $(k,t)$ 总数是 $O(n)$，故最终复杂度为 $O(n^3)$。

写了将近 3h，还是没能战胜 HXH 大人吗。

晚上和 HXH，HMZ，LKY，LMR（线上参加）一起找了一家火锅店。

可惜海底捞太火了只能去隔壁的自助，不过明日方舟联动应该早发完了？

然后把手机放在一起同步抽凛御银灰和圣聆初雪。最有节目效果的一集。

到最后本来想 300 井个缪的，结果 200 抽自己出来了，她果然爱我！

大家下车一定要看脚下啊。

后记：第二天还是好疼。