CSP-S 专题 · 非专业级软件能力认证（提高级）

CSP-S 提高级进阶算法

CSP-S 是 CCF 非专业级软件能力认证的提高级别，与 CSP-J 同一天分两场进行。第一轮为集中笔试，第二轮为上机编程。它是 NOIP 的门票——CSP-S 成绩优异者有机会获得 NOIP 参赛资格。本专题把提高级的考点按模块拆开，每个模块都给出「考什么 + 本站对应章节 + 刷什么」的明确路径。

一、考试概览与晋级规则

项目	说明
全称	非专业级软件能力认证（提高级），英文缩写 CSP-S
主办方	中国计算机学会（CCF）
面向对象	初中生至高中生，编程基础扎实、有一定竞赛经验的学习者
编程语言	C++（本站聚焦 C++ 方向）
第一轮	集中笔试，约 9 月举行，考察理论、算法概念与阅读理解
第二轮	上机编程，约 10 月举行，限时完成编程题
与 NOIP 关系	成绩优异者有机会获得 NOIP 参赛资格（以 CCF 当年公告为准）

提示第一轮笔试不是「考背诵」。选择题占比高但覆盖面广，很多题考的是「你知不知道这个算法能解决什么问题」，而不是背公式。建议按本专题的模块顺序过一遍，能在第二轮省下大量时间。

二、高级数据结构

提高级的分水岭模块。第一轮考概念辨析，第二轮直接上模板题。

知识点	典型应用	对应章节
树状数组	单点修改 + 前缀/区间和查询，O(log n)；求逆序对、区间最值配合其他结构	10 树与二叉树
线段树	区间查询 + 区间修改（懒标记），是提高级第一轮/第二轮的高频考点	10 树与二叉树
ST 表	静态区间最值 / 最值计数，配合倍增或容斥使用	10 树与二叉树
并查集	连通性维护，配合路径压缩 + 按秩合并	07 STL
平衡树	Treap / Splay 入门：动态插入删除并支持第 K 大、区间第 K 大	07 STL
可持久化	主席树（可持久化线段树）入门：区间第 K 小、静态区间查询	13 分治

树状数组 · 单点加 + 前缀和（模板）

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, m;
int tree[N];

void add(int x, int v) {          // a[x] += v
  for (; x <= n; x += x & -x) tree[x] += v;
}

int sum(int x) {                   // a[1..x] 之和
  int res = 0;
  for (; x > 0; x -= x & -x) res += tree[x];
  return res;
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    int a; cin >> a; add(i, a);
  }
  while (m--) {
    int op, x, y; cin >> op >> x >> y;
    if (op == 1) add(x, y);                  // a[x] += y
    else if (op == 2) add(x, -y);            // a[x] -= y
    else cout << sum(y) - sum(x - 1) << '\n';  // 区间和
  }
  return 0;
}

易错提醒

树状数组下标必须从 1 开始，add(0, v) 会死循环。
求逆序对时用树状数组时，要先离散化：数据范围可能达到 1e9。
线段树懒标记下传时忘记清空标记，会导致答案莫名偏大。

三、图论进阶

相比 CSP-J 的「图的遍历」，提高级要求掌握带权图与复杂网络模型。

算法	用途	复杂度
堆优化 Dijkstra	非负权单源最短路，边数大时优于朴素版	O((n+m) log n)
Floyd	全源最短路，n ≤ 100 时的万能解；也用于传递闭包	O(n³)
SPFA / Bellman-Ford	含负权边；SPFA 会被卡，需谨慎	最坏 O(nm)
Kruskal / Prim	最小生成树，常配合并查集与 Kruskal 重构树	O(m log m)
拓扑排序	DAG 上的转移；关键路径、判断环、字典序最小拓扑	O(n+m)
Tarjan SCC	强连通分量、割点、桥；缩点后变 DAG 再做 DP	O(n+m)
LCA	倍增或树剖求最近公共祖先，树上路径问题基础	O(n log n)

高频陷阱

Dijkstra 不能处理负权边——这是选择题最爱考的概念辨析。
求「次短路」时不能用 Dijkstra 直接改标记，要用 A* 思想或多源扩展。
最小生成树不保证最短路：MST 只最小化边权之和，任意两点距离可能比最短路大得多。
邻接表存图时 边数 × 2 容易漏加无向边的反向边。

四、字符串算法

提高级开始出现「整章字符串」，不再是单纯的字符串输入输出。

算法	解决的问题	关键思路
KMP	字符串匹配、求最短周期、失配数组	前缀函数 next 数组，避免主串指针回退
字符串哈希	子串相等判断、去重、计数	哈希冲突概率高，需双哈希降低风险
Trie 树	单词查找、前缀统计、01-Trie 求异或极值	按字符建树，查询复杂度 O(len)
AC 自动机	多模式串同时匹配、多关键词文本过滤	Trie + fail 指针，fail 树上做统计
Manacher	最长回文子串 O(n)	用哨兵统一奇偶，记住中心扩展的复用公式

五、动态规划进阶

CSP-J 已经会线性 DP 和背包；提高级考的是模型识别——同一个「树形 / 区间 / 状压 / 数位」前缀，题目可以完全换皮。

类型	识别特征	对应章节
树形 DP	在树或 DAG 上做转移，答案由子树合并而来；常与 Tarjan 缩点联动	10 树与二叉树
区间 DP	操作区间左端或右端，如「区间合并」「石子合并」	15 DP 入门
状压 DP	状态用二进制位表示，n 通常 ≤ 20；与最短路状压优化同源	17 位运算与状态压缩
数位 DP	统计满足数位约束的整数个数，如「区间内不含 13 的数」	15 DP 入门
背包进阶	分组背包、依赖背包、多重背包的单调队列优化	15 DP 入门
单调队列 / 斜率优化	把 DP 转移从 O(n²) 压到 O(n)，本题要求能看懂推导	15 DP 入门

做题方法论

遇到 DP 题先问三句话：状态是什么？转移从哪来？顺序和初值是什么？比直接套模板可靠得多。DP 写错几乎都是这三问答不全，不是模板不熟。

六、数学建模与数论

提高级的「数学分」占比不低，且往往是拉开差距的部分。

知识点	典型场景	对应章节
快速幂	大数乘法取模，复杂度 O(log n)	16 数论基础
乘法逆元	模意义下的除法；费马小定理求逆	16 数论基础
扩展欧几里得	解同余方程 ax + by = gcd(a,b)	16 数论基础
中国剩余定理	合并多个同余条件求最小正解	16 数论基础
组合数取模	大 n 下求 C(n,m) mod p；杨辉三角 vs 快速幂组合数	13 分治
容斥原理	统计「至少满足 k 个条件」的方案数	12 贪心
矩阵快速幂	线性递推求第 n 项，转移矩阵化	16 数论基础

快速幂 · 计算 a^n mod m（模板）

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll qpow(ll a, ll n, ll mod) {
  ll res = 1;
  a %= mod;
  while (n > 0) {
    if (n & 1) res = res * a % mod;   // 当前二进制位为 1
    a = a * a % mod;                     // 位间平方
    n >>= 1;                          // 右移一位
  }
  return res;
}

int main() {
  cout << qpow(2, 10, 1000) << '\n';  // 24
  return 0;
}

七、机考形式与时间分配

阶段	建议策略
第一轮 · 笔试	概念辨析题先做；算法题按「是否能写出核心伪代码」判断是否会做；留足时间做最后的大题
第二轮 · 上机	先通读全部题目，把「一看就有思路」的题拿下，再回头攻难题；绝不在一道题上卡超过总时长的 1/3
读题阶段	标出输入范围（决定用 int 还是 long long、是否离散化）
调试阶段	先写暴力小数据验证逻辑，再优化；`freopen`、文件读写是否要求务必看清题面
提交前	用样例跑通、检查数组越界、检查是否有多组数据未清空、确认答案范围用 long long

八、刷题路径与能力自测

能力自测（能独立写出来才算过关）

序号	自测项	掌握度
1	树状数组：单点改 + 区间求和，以及用它求逆序对	□ 熟练 □ 看模板 □ 没思路
2	线段树：带懒标记的区间加 + 区间和	□ 熟练 □ 看模板 □ 没思路
3	堆优化 Dijkstra，并能说明为什么不能处理负权边	□ 熟练 □ 看模板 □ 没思路
4	Tarjan 求 SCC 并缩点，再在 DAG 上拓扑 DP	□ 熟练 □ 看模板 □ 没思路
5	KMP 求失配数组及字符串最小周期	□ 熟练 □ 看模板 □ 没思路
6	树形 DP：树上选点使收益最大且相邻不同时选	□ 熟练 □ 看模板 □ 没思路
7	数位 DP：统计区间内不含某数字的整数个数	□ 熟练 □ 看模板 □ 没思路
8	快速幂 + 费马小定理求逆元算组合数取模	□ 熟练 □ 看模板 □ 没思路

九、高频失分点

这些坑，几乎每届都有人踩

整数溢出：n ≤ 1e9 的平方会爆 int。凡是乘法想 long long，乘法本身先转 (ll)a * b。
数组开小：值域最大到 1e6 却按 n 开数组，或多组数据时上一组的值没清空。
递归爆栈：链状图 DFS 深度到 1e5 会爆栈，改用显式栈或 BFS。
忘了离散化：坐标值 1e9 开不了数组，又忘离散化直接 RE。
精度问题：涉及除法时改用整数运算或乘法交叉相乘，避免浮点误差。
复杂度超标：n = 1e5 时 O(n²) 必然 TLE，先估复杂度再写代码。
想清楚再动手：第一轮笔试的算法设计题，思路错误比写不完扣分更重。

总结

CSP-S 的核心不是「学过多少算法」，而是能否在限定时间内识别出题目属于哪个模型，并写出模板。建议把上面的自测表打印出来，每一项达到「熟练」再进入下一阶段。相关理论细节可回看 20 机考应对与坑点与 19 竞赛技巧与复杂度。

十、CSP-S 配套模拟题

下面 20 道题按单选 → 程序阅读 → 编程三类组织，覆盖本页五大模块的核心考点。题库为教学自编，用于配套练习与自测，不是官方历年真题。作答后立即判分并给出解析。

本页目录

一、考试概览与晋级规则二、高级数据结构三、图论进阶四、字符串算法五、动态规划进阶六、数学建模与数论七、机考形式与时间分配八、刷题路径与能力自测十、配套模拟题九、高频失分点

← 上一站：CSP-J 专题下一站：NOIP 专题 →