资讯 / 正文

【真题复盘】CSP-J/S 第二轮认证真题复盘:提高组四道题,三道是图:卡住的不是算法

2026-11-06 16:22

PART.01

这一轮考了什么

2026 年 10 月 31 日下午 14:30—18:30，CSP-J/S 2026 第二轮认证提高组（CSP-S2）开考。四个小时，四道程序题，满分 400 分。

考完当天，群里最常见的两句话是「迁徙把人迁走了」和「研发基地连题都没读懂」。这篇把四道题的真题内容一次讲完：考什么、样例怎么读、正解卡在哪一步、拿不到正解还能拿哪一档分。

认证名称CCF 非专业级别软件能力认证 CSP-J/S 2026 第二轮（提高组）

主办单位中国计算机学会（CCF）

认证时间2026 年 10 月 31 日 14:30—18:30

题目与分值4 道程序题，满分 400 分

题目目录名crystal / subway / migrate / hub

每题时限前三题 1.0 秒，第四题 3.0 秒

测试点20 / 25 / 25 / 20 个，每个测试点等分

评测环境NOI Linux 2.0，内存 1024 MiB，-O2 -std=c++14

PART.02

四道题考什么

四道题里三道属于图论与树，但真正难的不是算法本身，而是把题目里的东西挑成结点和边。下面这张图把四道题的核心考点和最容易卡住的地方排在一起。

四道题各自的分工

✓第一题是送分题。排序之后答案一定落在一段连续区间里，想通这一点，滑动窗口十分钟就能写完。

✓第二题是关键题。算法只有最短路，难点在建图：站点能到 50 万，线路却不到 500，把整条线路当成一个点，规模立刻降下来。

✓第三题是拉分题。先证明最短路径不折返，再按层扩展；计数只需要保留每层末尾的一两个状态。

✓第四题是压轴题。二分答案加逐轮删叶，暴力枚举点集能先占住一档底分。

PART.03

四道题逐题拆

提高组这四道题，三道属于图论与树。下面按题号顺序，每题讲清题意、样例、正解的关键一步，以及部分分从哪来。

提高组四道题：真题内容与正解

01 能量水晶 crystal

n 颗水晶各有能量值，可以进行至多 m 次操作，每次选一颗把能量值加 1，同一颗可以反复选。要用若干颗合成一颗大水晶，参与合成的必须能量值相同，问最多能用上几颗。样例 1 是 1、2、4、8、9，操作 5 次，把 1 加 3、2 加 2 都变成 4，能用上 3 颗。样例 2 专门放了负数：-3、-1、2、2、7，8 次操作，前四颗都变成 2，答案是 4。先想清楚一件小事：选定一批之后，目标值定在哪里最省？因为只能加不能减，目标不能低于这批里最大的那个，再往上抬只会多花操作，所以目标就是最大值。由此得到正解：排序之后，最优方案一定是一段连续区间。理由很朴素——跳过一颗离目标更近的、去选一颗更远的，操作数只会更多不会更少。于是变成滑动窗口：右端点当目标值，代价等于目标值乘区间长度减去区间和，一旦超过 m 就把左端点右移。数据范围要留意：m 到 10 的 18 次方，能量值到 10 的 12 次方，代价会远远溢出 int，全程 long long。

02 地铁 subway

m 个地铁站，n 条线路，每条线路经过若干站。从地铁口走到站厅要 w[v]，从站厅走到某条线路的站台要 t，站内换乘必须走「站台 → 站厅 → 另一条线路站台」。q 个询问，每次问从 x 站地铁口到 y 站地铁口的最小总步行时间。样例 1 有五站两条线，两条线在第 2 站相交，从 1 到 3 是 32，从 1 到 2 是 17。这题的难点不在算法，在建图。两个规模给了提示：站点总数可以到 50 万，线路数却不超过 500。同一条线路上坐车不产生步行时间，所以可以把一整条线路当成图上的一个点。建图前先算清一件事：从线路 i 换到线路 j 要走多少？在两线共同经过的站 v 上，代价就是「站厅走到线路 i 站台」加「站厅走到线路 j 站台」；两条线路有多个公共站，取最便宜的那个当边权。线路数不到 500，跑一遍最短路就得到任意两条线路之间的最小换乘代价。回答询问时枚举起点的线路和终点的线路：进站、上站台、中间换乘、下站台、出站，取最小。最容易多算的一处是中途的 w——站内换乘只经过站厅，不走地铁口，所以只有在起点和终点才计进出站的时间。

03 迁徙 migrate

n 座岛屿自北向南排成一条直线，坐标严格递增。海鸟每次飞行距离不超过 d，两岛坐标差不超过 d 就能直飞。若从 u 到 v 的最短路径恰好有两条，就称这对岛屿是双径岛屿对，求这样的对数。样例里，坐标 1、2、3、4 配 d 等于 2，答案是 1：从 1 到 4 有 1 到 2 到 4、1 到 3 到 4 两条最短路径。坐标 1 到 5、d 等于 2 时，答案是 2。第一步不是想算法，是证明一件事：最短路径一定不折返。坐标有序，一次折返等于连续三个位置出现局部极大或极小，而首尾两点的距离不超过那两步里较长的一步，中间那步可以直接跳过。所以从 u 到 v 的最短路径每一步都朝右。有了这条性质，按层扩展时每一层都是连续的一段区间。预处理每个岛一步能到的最右位置，用双指针线性求出；当前层右端点是 i，下一层就是 i 后面到最右位置那一段。真正难的是计数。每个点的最短路径条数只可能记成 1、2、3（3 表示至少三条，截断一下防止数值爆掉），而且同一层从左到右不会增加。要判断「恰好两条」，只需要知道每层末尾一两个点的计数——前面的点一旦到了三条，后面不可能再产生恰好两条。把每层压成有限种状态，就能线性递推。部分分入口是小数据逐源搜索：从每个起点做一次按层扩展，累加路径条数。

04 研发基地 hub

n 座城市的道路构成一棵树。要选恰好 k 座城市建基地，选中的点在树里形成不超过两个连通块。每座城市的通勤距离是它到最近基地的距离，通勤半径是所有城市通勤距离的最大值，求所有合理方案里通勤半径的最小值。样例里，五个点一条链、k 等于 2 时答案是 1；十个点的树、k 等于 3 时答案是 2。先想暴力：枚举点集、再判连通块数，只能过最小的几个点。正解分两层。第一层把「让最大值最小」变成可判定的问题：二分答案 r，判断能不能选出 k 个点、连通块不超过两个，让所有点到最近选中点的距离都不超过 r。第二层是这个判断怎么做：从叶子往里逐轮剥，距离超过 r 的叶子一定先要有人管，剥到某个位置就得在附近放一个基地；按这条路线把 k 个基地放完，再看剩下的部分能不能被覆盖、连通块数有没有超过两个。难点在两处：证明「至多两个连通块」可以这样转化，以及剥叶的过程不能漏情况。这也是四道题里最难拿分的一道。

PART.04

四个小时怎么分

提高组的分数差，很大一部分不在最后一道题，而在前两题有没有稳稳拿到手、后两题有没有把能拿的部分分拿到。

一份可以直接照着用的时间表

✓前两题是全卷基本盘，一小时出头应该拿下。第三题想不出来时，先回头看前两题有没有漏测、有没有该开的 long long 没开。

✓第一题 25—35 分钟。排序加双指针的框架很短，难的是把「选哪些数」想成「排序后的连续一段」，这一步想通，代码十分钟就写完了。

✓第二题 45—55 分钟。建模比代码重要：先把「线路当结点、换乘当代价」写清楚，再动键盘。Floyd 是三行，建图是三十行。

✓第三题 60—70 分钟，但先写能拿分的那一版。小数据逐源搜索通常比正解好写，交上去再想办法优化。

✓第四题至少留 50 分钟。暴力枚举点集先占住底分，有余力再去做二分答案加剥叶。

PART.05

出分前的复盘

这一年的提高组，考的是「把陌生问题变成会做的模型」