ARTICLE · 1391277
CSP-S 2026 完整版题解(含源码与数据)
官方测试数据出来了,带你一步步优化到最优解。
往年题解列表
NOIP :2025-A2025-B2025-D2024-A
NOIP-J:20072006200520042003200220012000199919981997
NOIP-S:20042003200220012000199919981997
NOI:1998-day11998-day21997-day11997-day2
CSP-J :202620252024202320222022-SD202120202019
CSP-S :2026-D2026-C2026-B2026-A202520242023202220212020
备考:得分技巧环境准备CSP-J 题型分析CSP-S 题型分析必备26个初级算法
算法:二分线段树状态最短路动态规划数学常见算法和数据结构DFS序单调栈/队列倍增ST表LCA倍增虚树

零、背景

之前单独分享了《CSP-S 2026 A题 能量水晶 题解》、《CSP-S 2026 B题 地铁 题解》、《CSP-S 2026 C题 迁徙 题解》、《CSP-S 2026 D题 研发基地 题解》。
2026 年 CSP-S 的官方数据、分数线出来有段时间来。
最近工作比较忙,一直没写 CSP-S 2026 的完整版题解。
最近抽出时间,写一下完整版题解。
PS: CSP-S 的题目、官方测试数据、各种题解的源码也上传到网盘,有需要的可以关注公众号,回复 CSP-S-2026 获取。

一、能量水晶(crystal)
题意:给 n 个能量水晶,每次可以选择一颗水晶球,把能量值加一。最多操作 m 次,问最多可以得到多少个能量值相同的水晶球。
分析:假设最终可以得到 k 个相同的能量值是 V,可以得到几个明显的结论。
结论1:V 肯定是输入的某个能量值。
反证法:如果 V 不是输入的某个能量值,假设小于 V 的最大能量值为 A,则这 k 个能量值到达 A 时就停止操作,显然可以节省了更多操作。
故,可以把 V 限制在输入的能量值集合中。
结论2:k 个水晶球的输入能量值肯定是连续的,不存在中间某个能量值不在 k 里面。
反证法:令 k 个水晶球里面最小的能量值为 L。
假设存在一个能量值为 X,X 满足 L < X <= V,且 X 不在 k 个水晶球里面。
则把水晶球 L 替换为 X 后,则可以用更少的操作次数,得到 k 个能量值为 V 的水晶球。
故,需要对输入的能量值排序。
基于这两个结论,来看如何做出这道题。
算法1:暴力枚举 - 45分
对于每个能量值为 V 的水晶,向左边从大到小枚举是否还可以操作,使得其能量值增加至 V。
复杂度:O(n^2)。
通过用例:1~9。
得分:45 分。
算法2:去重优化 - 60分
第 10~12 组测试用例的值域不超过 100,这意味着有很多相同值。
如果最终能量值为 V,显然所有值为 V 的水晶都需要选择,所以相同值只需要枚举最后一个位置。
复杂度:O(100 * n)。
通过用例:1~12。
得分:60分。
算法3:性质A 优化 - 75分
第 13~15 组测试数据满足特殊性质 A,所有数字连续递增。
确定右端点 R 后,从右往左第一个水晶增加 0,第二个增加 1,第三个增加 2,依次递推。
令 x = R - L,总共增加 m。
可以解方程 (0 + x) * (x + 1) / 2 <= m。
直接得到 L = R - x。
复杂度:O(n)。
通过用例:1~15。
得分:75分。
算法4: 性质B 优化 - 90分
第 16~18 组测试数据满足特殊性质 B,所有数字形成等差数列,公差为 d。
可以套用性质 A 的解法,只是方程更复杂:(0 + xd) * (1 + x) / 2 <= m。
解得 x <= (sqrt(d^2 + 8dm) - d) / (2d),直接计算即可。
复杂度:O(1)。
通过用例:1~17。
得分 85 分。
第 18 个样例因为精度问题,没有通过。
所以不能直接解方程,改用二分求方程的解。
判断条件还是 (0 + xd) * (1 + x) / 2 <= m,但全部用整数运算,避免精度问题。
复杂度:O(log n)。
通过用例:1~18。
得分: 90 分。
算法5:二分 - 100分
对于第 R 个水晶,假设最多可以修改到第 L 个水晶。
可以发现,对于 [0, L) 都是不满足条件的,对于 [L, R] 都是满足条件的,满足单调性。
所以可以二分找到这个分界点 L,区间长度就是 R - L + 1。
那对于任意一个位置 L,如何快速判断是否满足条件呢?
可以利用前缀和,快速判断 [L, R] 需要加多少次才能使得所有值都等于 nums[R]。
公式也很简单:sum(L, R) + m >= (R - L + 1) * nums[R]。
复杂度:O(n log n)。
通过用例:1~20
得分: 100 分。
算法6: 双指针 - 100分
对于每个右边界 R ,可以发现,L 是单调非递减的。
故可以使用一个左边界游标,复用上次的左边界,从而快速找到当前的左边界 L。
复杂度:O(n)。
通过用例:1~20。
得分: 100 分。
详细题解参考文章:《CSP-S 2026 A题 能量水晶(6个解法)》。


二、地铁(subway)
题意:有 m 个地铁站,地铁站有三部分:地铁口、地铁厅、地铁站台。有 n 条地铁线路,每条地铁会经过若干地铁站。
换乘时,需要先从一条地铁线上下来到站台,然后走到大厅,最后走到另一条地铁线的站台。
地铁口到地铁大厅、地铁大厅到某条线的站台都需要花费若干走路时间。
问从 A 地铁口到 B 地铁口,最少的走路时间。

分析:显然是最短路问题,关键是看如何构图。
算法1:线路+站点构图,全源最短路,44分
线路和地铁站都当作一个点,构图,求全源最短路。
Floyd 算法可以直接求任意两个节点之间的最短路。
复杂度 O(V^3)。
通过用例:1~11。
得分:44 分。
算法2:性质B,边权相同,44分
性质 B 保证所有 t 相同,于是图上所有边权相同。
边权全部相同时,Dijkstra 的优先队列退化为普通队列,直接 BFS 即可。
复杂度从 O(E log V) 降到 O(E)。
通过用例:1~11。
得分:44 分。
算法3: n<=2 特判 ,52分
n = 1 时,只有一条线路,所有地铁站都在这一条线路上,全程无需换乘。
hash 表预处理每个站到该线路站台的步行时间即可。
n = 2 时,最多换乘一次,即从 1 条线换到另 1 条线。
换乘只能发生在两条线路共同经过的站点 v。
两个线路可能有多个共同站点,需要取最小换乘时间。
得分:52分。
算法3:线路图 + Floyd,100分
线路数最多是 500,如果能以线路为点构图,即可接受 O(n^3) 的复杂度。
构图:对每个地铁站的线路两两连边即可。
复杂度:O(m d^2)
全源最短路:使用 Floyd 算法求最短路。
复杂度:O(n^3)
询问:枚举两个站点的线路对,求最小换乘时间。
复杂度:O(q * d^2)
得分:100分
详细题解参考文章:《CSP-S 2026 B题 地铁 题解》。

三、迁徙(migrate)
题意:有 n 个岛屿排成一排,海鸟每次飞行的最大距离不超过 d。
问有多少个岛屿二元组,从从一个岛屿飞到另外一个岛屿最短路恰好有两条。
分析:首先可以确定两个结论。
结论1:最短路不会往回飞。
反证法:假设存在往回飞的路径,往回飞后还要再飞回来,这样反而多消耗一次直飞。
因此从两个岛屿之间的最短路径,坐标一定是严格递增的。
结论2:路径数大于 2 是都不是答案,没区别。
路径数一旦到 3,后面不管怎么走都不可能再变回 2,所有大于 2 的值完全可以统一记成 3。
算法1:暴力 DP(24 分)
题目是问有多少个二元组,其最短路的不同路径恰好有 2 个。
最简单的做法是求出所有二元组的最短路与不同路径个数,然后判断是否等于 2。
状态定义:dpStep[l][r] 节点 l 到节点 r 的最短路。
dpPath[l][r] 节点 l 到节点 r 的不同路径个数。
状态转移方程:枚举 r 的上一跳节点 k,判断先从 l 若干次到 k,再从 k 直接到 r 是否更优。
复杂度:O(n^3)。
通过过用例:1~6。
得分:24分。
算法2:利用单调性,两次二分,40分
枚举 v 的上一跳 k 时,k 越大离 l 越远,最少飞行次数只可增减。
所以固定 l 时 dpStep[l][k] 关于 k 单调不减。

于是最优的上一跳,一定是 r 向左能直飞到的最靠左那个点,记作 minKFirst。
由于只增不减,意味着还有连续相等的点。
与它 step 相同的 k 必然也连成一段,右端记作 minKLast。
路径数就是这一段上 dpPath[l][k] 的和。
minKFirst 是第一个满足 x_k >= x_r - d 的位置,直接 lower_bound。复杂度 O(log n)。
用 upper_bound 找第一个大于 dpStep[l][minKFirst] 的位置,然后再减一,就是最后一个与 minKLast 值相等的位置。
复杂度也是 O(log n)。
有了左右边界,路径数就是 dpPath[l][minKFirst] 到 dpPath[l][minKLast] 的和。
这就要求维护一个前缀和,来快速计算区间和。
复杂度:O(n^2 log(n))得分:24 分。
算法3:二分转双指针,40分
既然满足单调性,可以使用双指针代替二分,消除一个 log。
第二个 log 是为了找到最后一个相等的值。
题目只要求找到 2个路径,所以相等值超过3个就确定没答案。
故只需要枚举前三个值即可。
复杂度 O(n^2)。
通过用例:1~10。
得分 40 分。

算法4:性质A,48分
分析性质 A,数据构成等差数列。
等差数列有一个性质,就是任意两个相邻的元素的差值都是相等的。
所以,如果区间 [l,r] 是答案,那 [l+k,r+k] 肯定也都是答案。
分析答案,只有一种情况,才会只有两条路径。
假设答案是 [l,r],那么 [r-d,l+d] 内恰好只有两个点。

假设 d 可以覆盖 cnt 个间隔,显然, cnt 必须大于等于 2。则 r-l 需要有 2*cnt-1 个间隔,构成一个答案。
共有 n-r+1个答案。
复杂度:O(1)。
通过用例:1~12。
得分:48分
算法5:性质B,最多两跳,56分
性质B是存在一座岛屿,使得海鸟可以从该岛屿直接飞到任意其他岛屿。
结合性质A得到的结论,可以确定,如果存在答案,那么只能选择三个点,且中间那个点有两种选择。
枚举所有左端点 l,找到最大步长 d,假设可以覆盖的最后三个点,记作 l1,l2,l3,满足 l1 <= l2 <= l3。
右端点 r 必须满足 l1 < r-d <= l2,即 l3 只能覆盖 l2和l3,不能覆盖 了。
二分查找出所有满足条件的 r,就是答案。
复杂度:O(n log(n))。
通过用例:1~14。
得分:56分

算法6:枚举 + 二分
根据性质 A 和性质 B,已经可以看出来,要构造恰好有2条最短路路径的图,必然是存在连续两跳,中间这一跳有两种选择都可以到达下个点。

如果我们枚举这两个关键点,就可以构造出满足要求的长度为 3 的双路径最短路。
如下图,枚举点是 (L,R),右侧最后一个答案是 RD[L],往前,直到 RD[L-1]+1 都是满足的。
也就是右侧 (RD[L-1], RD[L]] 区间内的点都可以形成长度为 3 的双路径最短路。

同理,左侧也可以计算出同样的满足双路径的区间。
左右区间大小相差,就是所有长度为 3 的双路径最短路。
路径长度如果要再增加,这些路径就必须是只有一跳的,不能产生冗余的路径。
故,其他边必须选择最远的端点,否则就会产生冗余路径,从而得到大于2的路径。
如下图,(L,R)的下一跳必须选择最远的可到达的 P,然后 P 的下一跳可选择就多了。
与前面的类似,需要 P 可到达,但是 P-1 不可到达。共有 RD[P] - RD[P-1] 种情况。

依次递推,对于确定的 (L,R),右侧的答案都是确定的,分别如下
第一跳:RD[L] - RD[L-1]第二跳:RD[P] - RD[P-1], P=RD[R]第三跳: RD[Q] - RD[Q-1], Q=RD[P]=RD[RD[R]]...
如果从后到前算,就可以利用后缀和,把每一跳的答案都计算出来。
复杂度:O(n log(n)) 。
得分:100分
算法7:双指针 100分
老优化了,使用双指针代替二分。
总复杂度 O(n)。
得分 100 分。
详细题解参考文章:《CSP-S 2026 C题 迁徙 题解》

四、研发基地(hub)
题意:给一棵树,选择 k 个节点,需要满足 k 个节点形成的图不超过两个连通块,且其他节点到达这个连通块的最大距离最小。

解法1:暴力枚举,80分
最大中求最小,显然需要二分答案。
二分最大距离 R,判断是否满足形成的图不超过两个连通块。
定义一个点到叶子的距离为高度。
显然,高度小于 R 的点都不需要选。
只要选高度大于等于 R 的点,高度小于 R 的点就能在 R 距离内到达连通块。
所以判断时,先把所有高度小于 R 的点删掉。
对于剩下的点,要么组成一个连通块,要么是两个连通块。
如果是一个,只要剩下的点数不超过 k,O(1) 就能判断。
如果剩下的点数大于 k,就只能拆成两个连通块。
删掉了高度小于 R 的点之后,这两个连通块肯定是被一条链分割的。

枚举这些链,问题就转化成:给若干个数字,选一个定长的区间,区间上每个点都要满足到左右其中一个端点的距离不超过指定值,问是否存在这样的区间。
暴力枚举是 O(n^2)。
综合复杂度:O(n^2 log(n))。
得分:80分。
解法2:滑动窗口,80分
暴力做法是固定区间后,枚举区间内的点,判断是否可以到达区间的两端。
其实可以反过来看,判断两个端点可以覆盖的最远点。
如果可以把整个区间覆盖,则存在答案。
分三种情况。
1)左端向右、右端向左,最远点交叉,所有点都能覆盖。
2)两个最远点相邻,还是能覆盖。
3)中间留了空档,这些点谁也无法覆盖,这个区间就不是答案。

设左端点 l 最远可以覆盖到 right[l]。
那么 l+1 肯定也能覆盖到 right[l],因为新端点离得更近。
这样使用双指针,所有左端点的最远覆盖位置就能都算出来了,复杂度 O(n)。
右端点向左同理,复杂度O(n)。
最后枚举所有区间,两个最远位置交叉或者相邻就可行,每种区间 O(1) 判断。
二分的一次判断始终是 O(n)。
综合复杂度 O(n log(n))。
得分:80 分。
删点与枚举链的常数太大,得分还是 80 分。
解法3:常数优化,85分
首先,可以把所有的一维 vector 都换成定长数组。
对于图,是二维的,可以缓存数组邻接表。
输入数据量比较大,换成 fastRead。
复杂度还是 O(n log(n))。
得分:85 分。
解法4:剪枝优化,95分
回顾算法流程:二分、复制图、两轮DFS删点、枚举链。
第一轮 DFS 删点之后, 可能就满足一个连通块了,可以提前判断。
第二轮 DFS 删点之后,再判断依次。
接下来这个剪枝很容易忽略。
假设剩余 leftNode 个点,名额只有 k 个,得继续删除 leftNode - k 个点,而且它们只能落在一条链上。
链两端各有一片选中点,每片沿着链最多往内覆盖 R 步,合起来最多覆盖 2R 个链上点。
如果要删的点超过 2R,无论挑哪条链都没答案,可以直接剪枝。
复杂度 O(n log(n))。
得分:95 分。
解法5:原图遍历枚举,100分
复制图与删除图太浪费性能了。
所以,把高度定义为到叶子的距离,则可以通过节点距离 与 R 的关系,即可知道这个点是不是被删除了。
通过这个优化,就可以得满分了。
详细题解参考文章:《CSP-S 2026 D题 研发基地 题解》

五、最后
这次比赛感觉题目出的并不好。
第一题还好,很容易想到二分,从而拿到满分。
第二题就比较令人头疼了,光是读题,就需要读半个小时。
读懂后,可以发现就是一个全源最短路,只是点有点多,涉及的数据比较多,需要各种转换。
使用暴力全源最短路可以得到 44 分。
发现线路不多后,为线路构图,从而得到 100 分。
第三题很有意思。
如果时间关系想拿部分分,也可以暴力DP,就是24分。
DP 简单优化下,就可以得到 40 分。
根据性质A和性质B差不多就可以想出这道题的正解了。
保险起见,先把性质A和性质B的分拿到,得 48分。
最后再枚举两个路径的相邻点,结合二分或双指针,拿到100分。
PS:如果是我,可能只能拿 48 分,正解一开始没想好的话,代码量太大了。
第四题也不好,卡常数。
我可能敲一个滑动窗口就结束了,只能拿到 80分。
这样看起来,如果我参加比赛,前两题可以拿满分。
第三题一开始会先拿48分。
最后一题肯定一气呵成拿到80分,然后还有时间回去优化第三题。
不过第三题大概率拿不到满分,毕竟做这道题时,也调试了好久,后面才把整个构造过程想的清楚。
总的下来,至少能拿到328分。
-EOF-
往年题解
NOIP :2025-A2025-B2025-D2024-A
NOIP-J:20072006200520042003200220012000199919981997
NOIP-S:20042003200220012000199919981997
NOI:1998-day11998-day21997-day11997-day2
CSP-J :202620252024202320222022-SD202120202019
CSP-S :2026-D2026-C2026-B2026-A202520242023202220212020
备考:得分技巧环境准备CSP-J 题型分析CSP-S 题型分析必备26个初级算法
算法:二分线段树状态最短路动态规划数学常见算法和数据结构DFS序单调栈/队列倍增ST表LCA倍增虚树
如果对你有帮助,感谢关注、、分享、、留言















































































