2026 CSP-J/S 复赛 真题与解析（10月31日）

说明

本文档为 2026 年 CCF 非专业级软件能力认证（CSP-J/S）第二轮（复赛）真题与参考解法的民间整理，题目来源于公开流出的考生回忆与培训机构题面，非 CCF 官方发布，正式成绩与官方题面以 CCF 公布为准。

整理时间：2026-11-01。代码均为参考实现（民间解法），用于复盘与自学，不保证与官方标程一致。

考试概况

• 提交文件名须为英文小写：
• J组：travel.cpp / string.cpp / and.cpp / card.cpp；
• S组：crystal.cpp / subway.cpp / migrate.cpp / hub.cpp。

• 强制文件 I/O（freopen 或文件流），编译选项 -O2 -std=c++14 -static，内存限制 1024 MiB（J）/ 1024 MiB（S，migrate 3s）。

---

第一部分　CSP-J（入门组）

T1　旅游（travel）

难度：入门　考点：模拟 / 字符串判断

题目描述

小 R 和小 X 准备坐高铁出门旅游，买了两张二等座车票。列车由 17 节车厢组成，编号 01–17，其中 01 和 16 号是一等座车厢，其余是二等座车厢。每节二等座车厢有 18 排，每排 5 个座位，座位号由两位排号 + 一位大写字母组成（如 03C 表示第 3 排 C 座）。每排从左到右为 A B C | D F，C 与 D 之间是过道。

两人希望座位相邻。请你依次判断两张票：

1. 是否在同一节车厢；

1. 是否在同一节车厢的同一排；

1. 是否在同一节车厢同一排且位于过道同一侧（A/B/C 同侧，D/F 同侧）；

1. 是否相邻（同一排、同一侧、且在该侧座位序列中相邻：A-B、B-C、D-F）。

输入格式

从文件 travel.in 读入。第一行四个字符串 c1 s1 c2 s2，分别为小 R 的车厢号、座位号和小 X 的车厢号、座位号。

输出格式

输出到 travel.out。一行一个长度为 4 的 01 字符串，依次表示上述四个问题的答案（1 是，0 否）。

样例

输入 #1:  02 01A 02 01B   输出 #1: 1111 输入 #2:  02 01C 02 01A   输出 #2: 1110 输入 #3:  02 01C 02 01D   输出 #3: 1100 输入 #4:  02 02B 02 01A   输出 #4: 1000 输入 #5:  02 01A 03 01A   输出 #5: 0000

样例 3 解释：01C 与 01D 中间隔着过道，不相邻，输出 1100。

数据范围

• c1,c2
   是 01–17 之间除 01 和 16 外的两位车厢号；

• s1,s2
   前两位是 01–18 的排号，末位是 A/B/C/D/F；

• 两张票不是同一个座位；

• 特殊性质 A：两座位在同一车厢（即 c1==c2）。

题解思路

四个问题是逐级嵌套的：不同车厢 → 后三问全假；不同排 → 后两问全假；不同侧 → 最后一问假。输出只可能是 0000 / 1000 / 1100 / 1110 / 1111 五种。

关键坑位：右侧只有 D、F，没有 E。若按字母表顺序算距离，D(4) 与 F(6) 差 2 会被误判不相邻。正确做法是用一个映射把座位映射到过道两侧的物理位置：A→0, B→1, C→2, D→4, F→5（过道占 3 号位），这样 C-D 差 2 不相邻、D-F 差 1 相邻同时成立。

参考代码

#include <bits/stdc++.h>usingnamespace std;// 把座位字母映射到过道两侧的物理位置（过道占 3 号位）int pos(char c) {if (c == 'A') return0;if (c == 'B') return1;if (c == 'C') return2;if (c == 'D') return4;return5; // 'F'}int main() {freopen("travel.in", "r", stdin);freopen("travel.out", "w", stdout);ios::sync_with_stdio(false);cin.tie(0);string c1, s1, c2, s2;cin >> c1 >> s1 >> c2 >> s2;bool car  = (c1 == c2);                                  // 同车厢bool row  = car && s1[0] == s2[0] && s1[1] == s2[1];     // 同排（排号两位）bool side = row && (s1[2] <= 'C') == (s2[2] <= 'C');     // 同侧bool adj  = side && abs(pos(s1[2]) - pos(s2[2])) == 1;   // 相邻cout << car << row << side << adj << '\n';return0;}

---

T2　回文串（string）

难度：入门　考点：双指针 / 段压缩

题目描述

小 R 有一个长度可能很长的字符串 S，由 n 段连续段组成。第 i 段由 a_i 个相同的小写字母 c_i 构成，依次拼接得到 S。小 X 想把 S 改成回文串（反转后与原串相同），可以修改任意位置的字符为其他小写字母。求最少需要修改多少个位置。

输入格式

从文件 string.in 读入。第一行一个正整数 n；接下来 n 行，每行一个正整数 a_i 和一个小写字母 c_i。

输出格式

输出到 string.out。一行一个整数，表示最少修改次数。

样例

输入 #1: 

3 2 a 2 b 1 c

输出 #1: 2        （S = aabbc，改为 aabaa，改 2 处）  

输入 #2: 

2 2 a 3 a 

输出 #2: 0        （S = aaaaa，已是回文）  

输入 #3: 

6 1000000000 a 1000000000 a 1000000000 a 1000000000 b 1000000000 b 1000000000 b 

输出 #3: 3000000000

数据范围

• 1 ≤ n ≤ 2×10^5
  ；

• 对所有 i，1 ≤ a_i ≤ 10^9，字符串总长度可达 2×10^14，不能展开；

• 测试点分层：小 n、小段长、大段长、大 n 等梯度。

题解思路

回文串要求对称位置字符相同。一对对称位置字符不同，至少需修改其中一个，且各对互不影响，所以最少修改次数 = 对称位置上字符不同的配对数。

由于总长可达 2×10^14，不能展开。直接在压缩后的段上用双指针：左指针 l 指向最左未处理段，右指针 r 指向最右未处理段，每次取 t = min(左段剩余, 右段剩余) 个字符配对；若两段字符不同，答案加 t；两端各扣 t，某段耗尽则指针向中间移动。注意答案可能超过 int，用 long long。

参考代码

#include <bits/stdc++.h>usingnamespace std;constint N = 200100;using P = pair<int, char>;int n;longlong ans;P num[N];int main() {freopen("string.in", "r", stdin);freopen("string.out", "w", stdout);ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++) cin >> num[i].first >> num[i].second;int l = 1, r = n;while (l < r) {int t = min(num[l].first, num[r].first);   // 本轮可配对的字符数if (num[l].second != num[r].second) ans += t;        num[l].first -= t;        num[r].first -= t;if (num[l].first == 0) l++;if (num[r].first == 0) r--;    }cout << ans << '\n';return0;}

---

T3　按位与（and）

难度：普及　考点：位运算 / 贪心

题目描述

给定 n 个非负整数，从中恰好选出 m 个，对选出的数做二进制按位与运算。求所有选法中，按位与结果的最大值。

输入格式

从文件 and.in 读入。第一行两个正整数 n, m；第二行 n 个非负整数。

输出格式

输出到 and.out。一行一个非负整数，表示按位与的最大值。

样例

输入 #1: 4 2 3 15 12 12 输出 #1: 12       （选 15,12 或 12,12，按位与均为 12）  输入 #2: 5 3 31 3 1 15 7 输出 #2: 7        （选 31,15,7）

题解思路

按位与的某一位为 1，当且仅当参与运算的所有数该位都是 1。因此要答案某位为 1，必须存在至少 m 个数在该位上都是 1。

从高位到低位贪心：第 29 位往第 0 位扫。因为 2^29 > 2^0+2^1+...+2^28，高位的一个 1 比低位全 1 都值钱，所以优先保高位。维护已确定的掩码 mask，尝试把第 b 位置 1 得 cand = mask | (1<<b)；统计有多少个数满足 (x & cand) == cand（即这些位全为 1），若 cnt >= m 则保留该位。注意条件是 >= m 而非 == m——够 m 个包含 cand 所有位的数后，随便挑 m 个，按位与仍带这些位。

参考代码

#include <bits/stdc++.h>usingnamespace std;constint N = 200100;int n, m, num[N];// 能否选出 m 个数，使它们的按位与包含 x 中所有为 1 的位bool judge(int x) {int cnt = 0;for (int i = 1; i <= n; i++)if ((num[i] & x) == x) cnt++;return cnt >= m;}int main() {freopen("and.in", "r", stdin);freopen("and.out", "w", stdout);ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) cin >> num[i];int ans = 0;for (int i = 29; i >= 0; i--)if (judge(ans | (1 << i))) ans |= (1 << i);cout << ans << '\n';return0;}

---

T4　纸牌游戏（card）

难度：普及+/提高　考点：链式传递 / 计数 DP

题目描述

给定一串牌面点数 a_1, a_2, ..., a_n（点数范围 1–m）。共进行 n 局游戏，第 i 局从第 i 张牌开始，依次处理到第 n 张，每局开始时桌面为空。

处理一张点数为 k 的牌时：

• 若桌面没有点数 k 的牌，直接放到最右边；

• 若桌面已有点数 k 的牌，则删除这张牌及其右侧的所有牌，再把新牌放到最右边。

求所有游戏结束后，对于每种点数 1..m，有多少局的桌面上还保留着该点数的牌。

输入格式

从文件 card.in 读入。第一行两个正整数 n, m；第二行 n 个整数 a_1..a_n。

输出格式

输出到 card.out。一行 m 个整数，第 i 个表示点数 i 在多少局结束后仍保留在桌面上。

样例与思路（以民间样例说明）

样例：a = [3,1,2,1,3,2,3,1,2,1]，m=3。

记 L(v) 为点数 v 最后一次出现的位置：L(1)=10, L(2)=9, L(3)=7。

• 第 1 局从位置 1 出发，a_1=3 不是最后一次出现 → 跳到 L(3)=7；a_7=3 是最后一次 → 走到 8；a_8=1 不是最后一次 → 跳到 L(1)=10；a_10=1 最后一次 → 走到 11 结束。链上经过的 3、1 去重为 {3,1}。

• 关键结论：一个点数 v 是否在某局桌面上，只看 L(v) 是否在该局出发的链上。设 f[p] 为经过位置 p 的起始局数，链严格向前，递推 f[p] = 1 + Σ f[下一步]，则 ans[v] = f[L(v)]。

时间复杂度 O(n + m)。

参考代码

#include <bits/stdc++.h>usingnamespace std;constint N = 500100;int n, m;int num[N];    // 每张牌的点数int ans[N];    // ans[x]: 结束时桌面上有点数 x 的牌的游戏局数int nxt[N];    // nxt[i]: 右侧下一张与第 i 张同点数的牌的位置，无则为 0int pos[N];    // 从右往左扫描时，各点数最近出现的位置int cnt[N];    // cnt[i]: 转移到位置 i 时，尚需处理的游戏数量int main() {freopen("card.in", "r", stdin);freopen("card.out", "w", stdout);ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) cin >> num[i];// 预处理每张牌之后下一张同点数牌的位置for (int i = n; i >= 1; i--) {        nxt[i] = pos[num[i]];        pos[num[i]] = i;    }// 每个位置本身对应一局从这里开始的游戏for (int i = 1; i <= n; i++) cnt[i] = 1;// 所有转移都向右，按下标递增处理for (int i = 1; i <= n; i++) {if (!nxt[i]) ans[num[i]] += cnt[i];   // 后面无同点数牌，当前牌必保留到结束        cnt[nxt[i] ? nxt[i] : i + 1] += cnt[i];    }for (int i = 1; i <= m; i++) cout << ans[i] << (i == m ? "" : " ");cout << '\n';return0;}

---

第二部分　CSP-S（提高组）

T1　能量水晶（crystal）

难度：普及/提高−　考点：排序 + 双指针（滑动窗口）

题目描述

小 R 有 n 颗能量水晶，第 i 颗能量值为整数 a_i。可进行至多 m 次操作，每次任选一颗水晶使其能量值 +1（同一颗可重复选）。希望选出尽可能多颗水晶，使它们的能量值完全相同。求最多能用多少颗水晶合成一颗大水晶。

输入格式

从文件 crystal.in 读入。第一行 n, m；第二行 n 个整数 a_i。

输出格式

输出到 crystal.out。一行一个正整数。

样例

输入 #1:  5 5 / 1 2 4 8 9   输出 #1: 3 输入 #2:  5 8 / -3 -1 2 2 7  输出 #2: 4

数据范围

• 1 ≤ n ≤ 5×10^5
  ，0 ≤ m ≤ 10^18，-10^9 ≤ a_i ≤ 10^9（民间整理数据，个别来源记 |a_i| ≤ 10^12，以官方为准）；

• 特殊性质 A：a_i = i；特殊性质 B：a_i 构成等差数列。

题解思路

能量只能增加，选中的水晶最终都变成其中的最大值最省。排序后，最优解一定是排序后的一段连续区间[l, r]：把所有数升到 a[r] 的代价为 a[r]×(r-l+1) - Σa[l..r]。固定右端点 r，左端点 l 随代价超预算单调右移（滑动窗口）。复杂度 O(n log n)。注意负数处理（代价公式直接代入，不要先取绝对值）和大整数用 long long。

参考代码

#include <bits/stdc++.h>usingnamespace std;int n, ans;longlong m, a[500005];int main() {freopen("crystal.in", "r", stdin);freopen("crystal.out", "w", stdout);ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];sort(a + 1, a + n + 1);int l = 1;longlong sum = 0;for (int r = 1; r <= n; r++) {        sum += a[r];while (a[r] * (r - l + 1LL) - sum > m) {  // 预算不足，移出最左端            sum -= a[l];            l++;        }        ans = max(ans, r - l + 1);    }cout << ans << '\n';return0;}

---

T2　地铁（subway）

难度：普及+/提高　考点：图论建模（以线路为结点）+ Floyd 最短路

题目描述

B 市有 m 个地铁站（1–m），每站有站厅，地铁口到站厅步行 w_v 时间（往返相同）。有 n 条线路，第 i 条经过 k_i 个站 a_{i,1}..a_{i,k_i}；在站 a_{i,j} 处，站厅到第 i 条线路站台步行 t_{i,j} 时间。同一条线路不重复经过同一站；每站最多 d 条线路经过；网络连通。有 q 个出行计划，从 x 站口到 y 站口，途中可站内换乘（换乘 = 从原线路站台走回站厅，再走到另一线路站台）。总步行时间 = 进出站 + 换乘步行时间之和。求每次出行的最小总步行时间。

输入格式

从文件 subway.in 读入。第一行 c n m d q（c 为测试点编号，c=0 表示样例）；第二行 m 个 w_v；接下来 n 行，第 i 行先 k_i，再 a_{i,1} t_{i,1} ... a_{i,k_i} t_{i,k_i}；最后 q 行，每行 x y。

输出格式

输出到 subway.out。q 行，每行一个最小总步行时间。

样例

输入 #1: 0 2 5 20 2 4 1 9 2 5 3 1 5 2 7 4 6 3 2 3 3 4 5 7 1 3 1 2 输出 #1: 32 / 17  输入 #2: 0 3 7 20 2 8 3 6 1 7 2 9 3 1 4 2 5 5 100 3 2 6 3 1 7 2 4 3 2 5 100 4 6 6 7 1 6 2 3 输出 #2: 35 / 16

数据范围

• 0 ≤ c ≤ 25
  ，1 ≤ n ≤ 500，Σk_i ≤ 5×10^5，1 ≤ d ≤ 20，1 ≤ q ≤ 10^5；

• 1 ≤ w_v, t_{i,j} ≤ 10^9
  ；每条线路内站号互异；

• 特殊性质 A：每条线路至多经过 2 个站（k_i=2）；特殊性质 B：所有 t_{i,j} 等于同一正整数 T。

题解思路

沿线路乘车不计费，只计步行。若以地铁站为结点，同线路上的站两两连边边数过大；正确建模是以线路为结点（至多 500 个）。两条线路在站 v 相交则连边，边权为两次站厅-站台步行时间之和 t_{i,j}+t_{i',j'}，多站相交取最小。用 Floyd 求线路间最小换乘步行 f[i][j]，询问时枚举起点站所属线路 i 与终点站所属线路 j，答案为 min(tx_i + f[i][j] + ty_j) + w_x + w_y。复杂度 O(n^3)。

参考代码

#include <bits/stdc++.h>usingnamespace std;constint M = 500005;constlonglong INF = (1LL << 60);int c, n, m, d, q, tot;int w[M], head[M], id[M], t[M], nxt[M];longlong f[505][505];longlong ans;void floyd(int sz) {for (int k = 1; k <= sz; k++)for (int i = 1; i <= sz; i++) {longlong fik = f[i][k];for (int j = 1; j <= sz; j++)if (fik + f[k][j] < f[i][j]) f[i][j] = fik + f[k][j];        }}void line() {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) f[i][j] = INF;        f[i][i] = 0;    }for (int v = 1; v <= m; v++)for (int j = head[v]; j; j = nxt[j])for (int k = head[v]; k; k = nxt[k]) {longlong val = 1LL * t[j] + t[k];                f[id[j]][id[k]] = min(f[id[j]][id[k]], val);            }    floyd(n);}int lx[25], ly[25];longlong tx[25], ty[25];void query(int x, int y) {int cx = 0, cy = 0;for (int j = head[x]; j; j = nxt[j]) { cx++; lx[cx] = id[j]; tx[cx] = t[j]; }for (int k = head[y]; k; k = nxt[k]) { cy++; ly[cy] = id[k]; ty[cy] = t[k]; }    ans = INF;for (int i = 1; i <= cx; i++)for (int j = 1; j <= cy; j++) {longlong val = tx[i] + f[lx[i]][ly[j]] + ty[j];if (val < ans) ans = val;        }    ans += w[x] + 1LL * w[y];}int main() {freopen("subway.in", "r", stdin);freopen("subway.out", "w", stdout);ios::sync_with_stdio(false);cin.tie(0);cin >> c >> n >> m >> d >> q;for (int i = 1; i <= m; i++) cin >> w[i];for (int i = 1; i <= n; i++) {int len; cin >> len;for (int j = 1; j <= len; j++) {int v, val; cin >> v >> val;            tot++;            id[tot] = i; t[tot] = val;            nxt[tot] = head[v]; head[v] = tot;        }    }    line();while (q--) {int x, y; cin >> x >> y;        query(x, y);cout << ans << '\n';    }return0;}

---

T3　迁徙（migrate）

难度：提高+/省选−　考点：最短路计数 + BFS 分层 + 状态压缩 + 线性 DP

题目描述

海上有 n 座岛屿，自北向南坐标严格递增 x_1 < x_2 < ... < x_n。海鸟每次飞行距离不超过 d，即 |x_u - x_v| ≤ d 时可直接飞抵。从 u 到 v 的一条路径形如 u=a_0,a_1,...,a_k=v，长度为 k（飞行次数）。若从 u 到 v 的最短路径恰好有两条，称 (u,v) 为双径岛屿对（两条路径经过的岛屿序列不同）。求双径岛屿对数量。

输入格式

从文件 migrate.in 读入。多组数据：第一行 c t（c 为测试点编号，t 为组数）；每组第一行 n d，第二行 n 个严格递增坐标。

输出格式

输出到 migrate.out。每组一行一个非负整数。

样例

输入 #1: 0 2 4 2 1 2 3 4 5 2 1 2 3 4 5 输出 #1: 1 / 2 （第一组只有 (1,4)：1→2→4 与 1→3→4；第二组为 (1,5) 与 (2,5)）  输入 #2: 0 2 5 3 -2 -1 0 1 2 6 2 -4 -3 -2 -1 3 6 输出 #2: 0 / 1

数据范围

• 1 ≤ T ≤ 10
  ，Σn ≤ 2×10^6；2 ≤ n ≤ 2×10^6，1 ≤ d ≤ 10^9，-10^9 ≤ x_i ≤ 10^9；

• 特殊性质 A：坐标为等差数列；B：存在一座岛可直达任意其他岛；C：d ≤ 20（部分来源记为 x_n - x_1 ≤ 10·d）。

题解思路

只需区分最短路条数为 1 / 2 / ≥3（≥3 截断为 3）。岛屿按坐标有序，BFS 每层是连续区间。定义六种层状态（最右点条数、倒数第二点条数等），相同「右端点 p + 层状态 s」的后续层完全相同，可合并计算。设 f[p][s] 表示以右端点 p、状态 s 的这一层之后各层中共有多少个终点恰好有两条最短路，逆序填表，起点贡献为 f[p][0]。复杂度 O(Σn)。下方为民间整理参考实现（含快读）。

参考代码（核心逻辑）

#include <bits/stdc++.h>usingnamespace std;constint M = 2000005;int n;int r[M];                 // r[i]: 从 i 向右一次最远能到达的岛屿longlong d, x[M], ans;void init() {int j = 1;for (int i = 1; i <= n; i++) {        j = max(j, i);while (j < n && x[j + 1] - x[i] <= d) j++;        r[i] = j;    }}int last[6] = {1,1,1,1,2,2};int pre[6]  = {0,1,1,3,0,3};int need[6] = {1,2,3,2,1,2};int ways(int p, int s, int v) {if (s == 2 && v <= r[p - 2]) return3;if (pre[s] != 0 && v <= r[p - 1]) returnmin(3, last[s] + pre[s]);return last[s];}int f[M][6];int main() {freopen("migrate.in", "r", stdin);freopen("migrate.out", "w", stdout);int c, t; cin >> c >> t;  // 实际提交建议用快读while (t--) {cin >> n >> d;for (int i = 1; i <= n; i++) cin >> x[i];        init();        ans = 0;for (int p = n; p >= 1; p--)for (int s = 0; s < 6; s++) {                f[p][s] = 0;if (r[p] == p) continue;// step(p,s): 计算本层新增双径终点数 add 与下一层状态 nxtint add = 0;if (last[s] == 2) add = r[p] - max(p, (pre[s]?r[p-1]:p));elseif (pre[s] == 1) { /* 见完整版状态转移 */ }                f[p][s] = add;// if (nxt != -1) f[p][s] += f[r[p]][nxt];            }        printf("%lld\n", ans);    }return0;}

注：T3 满分实现涉及较复杂的六状态线性 DP 与快读，上方为逻辑骨架，完整可编译版本建议以培训机构发布的标程为准（如优编程教练组题解），此处为帮助理解建模思路。

---

T4　研发基地（hub）

难度：省选/NOI−　考点：二分答案 + 树上删叶 + 链上连续段判定

题目描述

小 W 选恰好 k 座城市建研发基地，选中的城市在树 T 中形成的连通块数量不超过 2。对方案 S，城市 u 的通勤距离为 min_{v∈S} dist(u,v)，方案通勤半径为 max_u dist(u,S)。求所有合理方案的最小通勤半径。

输入格式

从文件 hub.in 读入。多组数据：第一行 c t；每组第一行 n k，接下来 n-1 行每条边 u v。

输出格式

输出到 hub.out。每组一行一个非负整数（最小通勤半径）。

样例

输入 #1: 0 2 5 2 1 2 2 3 3 4 4 5 10 3 1 2 1 3 2 4 2 5 3 6 3 7 3 8 7 9 9 10 输出 #1: 1 / 2 （第一组选 {2,3} 或 {3,4} 半径 1；第二组选 {4,5,10} 半径 2）

数据范围

• 1 ≤ T ≤ 10
  ，Σn ≤ 10^6；1 ≤ k ≤ n ≤ 10^5（部分来源记 n ≤ 10^6）；

• 特殊性质 A：存在正整数 L 使 k=2L-1 且树呈毛毛虫形态。

题解思路

「至多两个连通块」等价于断开树上一条边，把树分成两部分各一个连通块。对固定半径 r，逐轮删去度数 ≤1 的叶结点，删 r 轮后剩余集合 C 必须被基地覆盖；最少基地数即 |C|（C 空则为 1）。二分 r：若 |C| ≤ k 一个块可行；否则需从 C 中去掉链上连续至少 |C|-k 个城市。实现：整树删叶得删除顺序并重编号，对每条非度数 2 城市出发的链做线性扫描判定。复杂度 O(n log n)。

参考代码（核心框架）

#include <bits/stdc++.h>usingnamespace std;constint M = 1000005;int c, t, n, k, tot;int head[M], to[M*2], nxt[M*2], deg[M];int lay[M], q[M], id[M], ly[M], st[M+1], adj[M*2], hgt[M];bool used[M];int h[M], lim[M];void add(int u, int v) {    tot++; to[tot] = v; nxt[tot] = head[u]; head[u] = tot; deg[u]++;}int peel() {                       // 返回最大层数（删除轮数）int l = 0, r = 0;for (int i = 1; i <= n; i++) {        lay[i] = 0;if (deg[i] <= 1) { lay[i] = 1; q[++r] = i; }    }while (l < r) {int u = q[++l];for (int e = head[u]; e; e = nxt[e]) {int v = to[e]; deg[v]--;if (deg[v] == 1 && !lay[v]) { lay[v] = lay[u] + 1; q[++r] = v; }        }    }return lay[q[r]];}bool check(int r) {int pos = 0;while (pos < n && ly[pos + 1] <= r) pos++;int sz = n - pos;if (sz <= k) returntrue;int need = sz - k;// 对每条度数≠2 城市出发的链做连续段判定（详见完整标程）returnfalse;  // 骨架，实际判定见完整实现}int main() {freopen("hub.in", "r", stdin);freopen("hub.out", "w", stdout);cin >> c >> t;while (t--) {cin >> n >> k; tot = 0;for (int i = 1; i <= n; i++) { head[i] = 0; deg[i] = 0; }for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; add(u, v); add(v, u); }int l = 0, r = peel();// relabel(); 重编号并建 adjwhile (l < r) {int mid = (l + r) / 2;if (check(mid)) r = mid; else l = mid + 1;        }        printf("%d\n", l);    }return0;}

注：T4 满分实现含重编号、链上连续段判定与快读，上方为算法骨架，完整可编译版本建议以培训机构发布的标程为准。

---

第三部分　题目 ↔ NOI 考纲知识点对照（复习索引）

本部分依据《全国青少年信息学奥林匹克竞赛大纲2025版（CSP-J/S 对应「入门级 / 提高级」）》的模块划分，将每道题映射到具体考纲条目，并给出复习落点。考纲分三级：入门级（对应 CSP-J）、提高级（对应 CSP-S）、NOI 级（省选/NOI）。2026 年 J/S 复赛全部题目均未超出「入门级 + 提高级」基础区，T4(hub) 是最接近提高级上限的一题。

一、对照总表

一句话结论：

• J 组四题 100% 落在入门级
  模拟、字符串、贪心、位运算、递推/简单 DP，是入门级考纲的「标准考题组合」。

• S 组呈梯度
  T1 是「排序+贪心+双指针」（提高级基础区），T2 是「图论建模+最短路」（提高级核心），T3 跨「图论+DP+搜索」三模块（提高级中上），T4 是「二分+树」（提高级上限、接近省选）。

二、分题详解（知识点 ↔ 考纲 → 复习落点）

J1　travel 旅游 —— 入门级 · 模拟 / 字符串判断

• 关联考纲
  入门级 1.2（程序基本概念、分支与循环、字符串处理）、入门级 1.4（模拟）。

• 本题如何考
  本质是「读入字符串 → 逐级 if 判定 → 输出 01 串」的纯模拟。难点只在「右侧无 E 座、过道隔断」这一现实建模（用映射 A0 B1 C2 D4 F5 解决），不涉及任何高级数据结构。

• 复习落点
  练「多级条件嵌套 + 字符串下标解析」。对应入门级真题风格题：洛谷 P5709（浏览器）、P5710（衣服）、P5711（闰年）。重点巩固 string 下标、字符比较、freopen 文件 I/O。

J2　string 回文串 —— 入门级 · 双指针 / 贪心

• 关联考纲
  入门级 1.2（字符串）、入门级 1.4（贪心、双指针/两端扫描）、入门级 1.5（大整数 long long）。

• 本题如何考
  回文 = 对称位相同，最少修改 = 对称位不同的配对数（贪心：每对独立，改一处即可）。总长度 2×10^14 不能展开 → 在压缩段上用双指针配对，是「数据范围倒逼算法」的典型。

• 复习落点
  练「双指针 + 贪心 + 大数溢出」。变式：普通回文（P1205 回文数）、区间配对。注意 long long 与 int 混用导致的溢出坑。

J3　and 按位与 —— 入门级 · 位运算 / 贪心

• 关联考纲
  入门级 1.5（位运算：与/或/异或、二进制表示）、入门级 1.4（贪心、按位贪心）。

• 本题如何考
  按位与某位为 1 当且仅当所有选中数该位为 1 → 高位优先贪心，逐位尝试置 1 并验证「≥m 个数满足」。是「二进制 + 按位独立」思想的入门代表题。

• 复习落点
  练「(x & mask)==mask 判定、从高位 29→0 贪心」。同类：P1010 进制转换、位运算基础、子集按位枚举。理解「高位 1 比低位全 1 都大」是核心直觉。

J4　card 纸牌游戏 —— 入门级 · 递推 / 计数 DP（链表思想）

• 关联考纲
  入门级 1.3（线性表：链表、next 指针思想）、入门级 1.4（递推、简单动态规划、模拟）。

• 本题如何考
  用 nxt[i] 存「右侧下一张同点数牌的位置」是链表思想的数组实现；答案靠「每个位置代表一局、向右转移计数」的递推（cnt 数组）完成，O(n+m)。是从「模拟」升维到「递推/计数」的过渡题。

• 复习落点
  练「nxt 数组预处理（从右往左扫）」「递推/计数 DP 的状态转移」。同类：P1160 队列、P1996 约瑟夫、链表插入删除。理解「一局游戏可用链/指针而非真的模拟每一步」。

S1　crystal 能量水晶 —— 提高级 · 排序 / 滑动窗口（贪心）

• 关联考纲
  提高级 2.2（排序）、提高级 2.4（贪心）、提高级 2.4（双指针 / 滑动窗口）、提高级 2.1（复杂度分析）。

• 本题如何考
  能量只能加 → 选中段升到最大值最省 → 排序后最优解必是连续段 → 固定右端点、左端点随预算单调右移（滑动窗口）。m ≤ 10^18、答案用 long long，负数直接代入公式。

• 复习落点
  练「排序 + 双指针/滑动窗口 + 前缀和」。同类：P1827 贪心、P1106 删数、区间和最值。重点：单调性证明（为什么左端点只会右移）、前缀和防溢出。

S2　subway 地铁 —— 提高级 · 图论建模 / 最短路

• 关联考纲
  提高级 2.3（图论建模/建图技巧）、提高级 2.3（最短路：Floyd）、提高级 2.3（邻接表）。

• 本题如何考
  关键建模突破——以「线路」而非「地铁站」为结点（站为结点边数爆炸）。两线路在同站相交则连边，边权为两段步行之和；Floyd 求线路间最小换乘步行，询问时枚举起讫线路。是「建图方式决定成败」的范本。

• 复习落点
  练「多对结点建图、Floyd O(n^3)、邻接表」。同类：P1119 灾后重建（Floyd 分层）、P2910 最优贸易（图建模）、各种「以 ×× 为结点」的建模题。重点吃透「什么时候要换建图角度」。

S3　migrate 迁徙 —— 提高级 · 图论 + 动态规划 + 搜索（综合）

• 关联考纲
  提高级 2.3（图论：最短路、连通性）、提高级 2.4（动态规划：线性 DP、状态压缩 DP）、提高级 2.4（搜索：BFS 分层）。

• 本题如何考
  鸟飞距离 ≤ d 构成图，求「最短路恰好两条」的岛屿对数。岛屿按坐标有序 → BFS 每层连续区间；只需区分条数 1/2/≥3（状态压缩成 6 种层状态），相同「右端点+状态」可合并，逆序线性 DP 计数。是「图论 + 计数 DP + 状态压缩」三合一。

• 复习落点
  先补「最短路计数（Dijkstra/BFS 计数）」「BFS 分层」「线性 DP + 状态压缩」。同类：P1144 最短路计数、P1602 奶牛跳跃（状态压缩最短路）。重点：理解「只关心 1/2/≥3 而非精确条数」的截断思想。

S4　hub 研发基地 —— 提高级 · 二分答案 / 树（接近省选）

• 关联考纲
  提高级 2.4（二分答案）、提高级 2.3（图论：树、连通块、删叶/拓扑思想）、提高级 2.4（递推与判定）。

• 本题如何考
  「至多两个连通块」等价于断一条边分两半 → 二分半径 r，按层删去度数 ≤1 的叶结点 r 轮，剩余集合 C 规模 ≤ k 即一个块可行；否则需从 C 中去掉链上连续 |C|-k 个城市（线性扫描判定）。是「二分 + 树操作 + 判定」的综合。

• 复习落点
  先补「二分答案模板」「树的中心/重心/删叶（拓扑）」「连通块判定」。同类：P1122 最大子树、P1395 会议（树重心）、P3853 路标（二分答案）。重点：把「几何/覆盖」问题转成「删叶后规模判定」。

三、复习路径建议（按考纲模块回刷）

使用说明

对照总表用于「看到题就知道考什么」，分题详解用于「知道考点后回扣考纲条目」，复习路径表用于「按模块成体系回刷」。三表联动即可把 2026 真题转化为一份考纲驱动的复习地图。

---

来源与声明

• J 组题面与参考代码
  综合自「青少年信息学编程服务站」「核桃编程」等公众号公开题解与考生回忆。

• S 组题面与参考代码
  综合自「新东方优编程教练组」「猿编程」「核桃编程」等公众号公开题解（含完整标程）。

• 民间数据自测
  洛谷已上传自制民间数据，可搜索 2026 CSP-J2 / CSP-S2 相关比赛自测。

• 重要声明
  本文档为考试后民间整理，非 CCF 官方资料。题面细节（尤其 J 组部分数据范围、S 组 T3/T4 完整标程）以各培训机构发布的完整题解为准；正式成绩与划线以 CCF 官方公告为准。复盘时建议结合官方题面与多来源题解交叉核对。

分数线参考（民间预测，非官方）：S 组全国一等基准线预计从 2025 年的 131 分回升至 155–165 分，强省（重庆/浙江/广东/山东等）涨幅更大；J 组因题目偏易，分数线逐年走高。具体以 CCF 公告为准。