CSP-S 2025 游记：拼尽全力无法战胜人行道吗？
Kazemaru
·
·
生活·游记
我永远不会忘记这沉重的一天 QwQ。
中午吃完饭坐车去考场。13:32 到了考场门口，下车。
然后，我在下车的时候，直接踩进绿化带并且没有注意脚下。
那个绿化带里面有个大坑？？？我踩进去摔了一跤。。。
当时我正在背包，双手被牵制着，于是我像个人机一样往人行道上倒。
然后就摔惨了。当时情况比较严重，没来得及拍下事故现场。
带着伤强行走到了考点门口（谁把路程设设么远啊），然后请校医帮忙处理了一下。
起码没骨折，成功参加了比赛。
——你怎么摔成这样的？
——走路摔跤，很难吗？
——摔成这样挺难的。
环境：高价值目标
【 I 】双手受伤，灵活程度降低 15\%。
【I I】双手受伤，灵活程度降低 30\%。
【III】双手受伤，灵活程度降低 50\%。
源石环境：侵蚀
【 I 】双腿受伤，灵活程度降低 20\%。
【I I】双腿受伤，灵活程度降低 40\%。
【III】双腿受伤，灵活程度降低 55\%。
环境：交战区
【 I 】前往考点所需的步行距离延长。
【I I】前往考点所需的步行距离大幅延长，且无法使用电梯。
环境：施工需求
【 I 】禁止使用草稿纸
难以想象以前随手写的 OI 赛制危机合约变成回旋镖打到了我自己身上。
听说还有同学点了【III】级的高价值目标，不知道他考得怎么样。
接下来是考场环节，如果你需要 VP 请酌情跳过。
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 还是相当魔怔的。
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 抽自己出来了，她果然爱我！
---
大家下车一定要看脚下啊。
后记：第二天还是好疼。