2026 CSP-S 复赛总结

时间分配

T1（能量水晶）用时约 15 分钟，通过。T2（地铁）用时约 1 小时 30 分钟，通过。T3（迁徙）未冲正解，拿下部分分。T4的思路对了一部分，但未完成代码实现，且下来发现思路有错误之处。剩余时间用于检查文件（输入输出重灾区）和对拍。

做题反思

T1 能量水晶（crystal）

题意是把若干水晶通过“只能增加、不能减少”的操作拉到同一个能量值，问最多能让多少颗参与合成。

刚拿到题就发现了性质：最终合成时的能量值一定是在数组中出现过的，因为如果目标值不在数列里，全部降到选定的数在原数组中的最大值一定不劣。而且，选定目标之后，优先选比目标值小的数中尽可能大的。因此对数组排个序，再对每个位置上的值，二分查找它之前尽可能长的符合条件的序列即可。

三、T2 地铁（subway）

T2 可以直接看我写的题解：

题目大意：每条线路经过若干站点，在每个站点换乘的时间不同。求两个地铁站之间，经过若干次换乘，步行时间最少的方案。

地铁站数量 \(5\times 10^5\)，对地铁站跑最短路显然不现实。注意到每个站点最多换乘的线路 \(d\) 非常小，只有 \(20\)，因此可以从起点站和终点站选择的线路下手。

令 \(S_i\) 表示经过地铁站 \(i\) 的线路，\(t_{x,p}\) 表示在起点站选择 \(p\) 号线，进站所需的时间，\(t_{y,q}\) 表示坐 \(q\) 号线抵达终点站后，出站所需的时间，那么最终的 \(\mathit{ans}\) 就等于

[

\mathit{ans}= \min_{p\in S_x}\min_{q\in S_y}\big{,t_{x,p}+t_{y,q}+\mathit{dist}_{p,q},\big}

]

其中，\(\mathit{dist}_{p,q}\) 表示从 \(p\) 号线换乘到 \(q\) 号线所需的最短步行时间。

发现了吗？问题从两个地铁站之间的步行时间，转化为了两条线路之间换乘的最短步行时间。

又注意到 \(n\le 500\)，因此问题就变成了求一张 \(500\) 个点的图上任意两点之间的最短距离。

考虑如何建图。此时再次注意到 \(d\le 20\) 这个性质。对每个地铁站，枚举两条线路，那么就相当于这两条线之间有一条长度为两线到站厅时间之和的边。

那还说啥了，这不就多源最短路板子吗？

建边后对每个点跑一次 Dijkstra 完事。复杂度 \(O(n^2\log n + d^2 q)\)。

在考场上思考了30分钟想出正解，但是在代码实现时没有想到对每个点跑 Dijkstra 的方法，用了Floyd算法，导致 \(O(n^3)\) 的时间卡着线过。下次完成题目后，应该再思考一下复杂度更优的方法，避免复杂度高被卡常。

T3 迁徙（migrate）

T3 的题意是：岛屿排成一条直线，海鸟单次飞行距离不超过 (d)，问有多少对 ((u,v)) 的最短路径恰好有两条。这是一个计数题，正解是双指针和维护“唯一最短路径层”的结构，我在考场上没有推出完整做法。

不过，在考场上发现了11~12测试点的特殊性质，拿了8pts的部分分。

T4 研发基地（hub）

T4 是树上的二分 + 贪心合并 / 换根类问题：二分通勤半径，判断能否选出总大小不超过 (k) 的连通块覆盖整棵树。我在考场上尝试了T4，但没有思考出完全正确的解法，代码实现也失分糟糕。不过，以我平时的能力，不借助外力显然也无法完成这种难度的题，更应该多拿点特殊性质分。

总结

总体来说，如果 T2 能拿满，我感觉这次应该还算是比较稳定发挥。主要问题在于：1.T2只写了 \(O(n^3)\) 的Floyd做法，没想到 \(O(n^2\log n)\) 的Dijkstra算法。2.T3和T4本来还能再多拿点部分分，但由于都去想不属于我这个难度的题的正解了，导致浪费大量时间还没写出来，错过了T3和T4十几分的部分分。