夜雨聆风学习资料网

ARTICLE · 1391277

CSP-S 2026 完整版题解(含源码与数据)

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倍增虚树

如果对你有帮助,感谢关注、、分享、、留言

回首页,搜索你想要的文档

在首页搜索框输入关键词,快速定位资料

文库首页搜索指引 立即搜索

相关学习资料