CSP-S（提高级）复赛为上机编程，4道题，限时4小时。知识点覆盖难度系数5~8级，在CSP-J全部知识点基础上新增以下内容。算法相关知识点占比最大（约47.2%），其次为数据结构和数学。复赛注重算法思维、代码实现与复杂度优化。
竞赛环境与代码规范（复赛深化）
1.1 Linux系统下的文件操作（绝对路径与相对路径）
1.2 Linux终端中编译与运行（g++ -o program program.cpp -O2 -std=c++17）
1.3 Linux下使用time命令测量程序运行时间
1.4 GDB调试器的基本使用（break、run、next、step、print、backtrace）
1.5 大型数组必须开在全局/静态区（防止栈溢出）
1.6 多组输入数据时的EOF判断（while(scanf(...) != -1)）
1.7 文件输入输出重定向（freopen的写法与注意事项）
1.8 内存限制换算（256MB约可开$6.7 \times 10^7$个int）
1.9 递归深度限制（约$10^5$层可能爆栈，考虑迭代或增大栈空间）
1.10 关闭同步流（ios::sync_with_stdio(false)）的时机与副作用
C++高级特性与STL（复赛应用）
2.1 类（class）的定义与使用
2.2 运算符重载（用于结构体/类的比较、排序）
2.3 函数对象（仿函数）与lambda表达式在sort中的应用
2.4 set与multiset的有序去重与查找（$O(\log n)$）
2.5 map与multimap的键值对存储与遍历
2.6 unordered_set与unordered_map的哈希存储（$O(1)$平均）
2.7 deque双端队列的用法（push_front、pop_front、push_back、pop_back）
2.8 priority_queue优先队列（默认大根堆，greater<T>为小根堆）
2.9 bitset位集合的操作与优化（空间压缩为1/8）
2.10 tuple元组（C++11）与pair的对比
2.11 STL算法中的自定义比较函数（cmp与lambda）
2.12 STL算法中的函数对象（greater、less、plus等）
数据结构进阶
3.1 单调栈（求下一个更大/更小元素，$O(n)$）
3.2 单调队列（滑动窗口最值，$O(n)$）
3.3 并查集的路径压缩与按秩合并（时间复杂度接近$O(\alpha(n))$）
3.4 带权并查集（维护节点到根的距离/关系）
3.5 可持久化并查集的基本思想
3.6 二叉堆的手写实现（上滤、下滤、建堆）
3.7 ST表（Sparse Table）解决RMQ问题（$O(n \log n)$预处理，$O(1)$查询）
3.8 树状数组（Fenwick Tree）支持单点修改+前缀查询
3.9 树状数组的扩展（区间修改+单点查询、区间修改+区间查询）
3.10 线段树的基本结构（递归建树、单点修改、区间查询）
3.11 线段树的懒标记（Lazy Propagation）实现区间修改
3.12 线段树的动态开点（处理大范围离散化）
3.13 链式前向星（用数组模拟邻接表，竞赛常用）
3.14 树的DFS序与欧拉序（将子树转化为区间）
3.15 树链剖分（轻重链剖分，将树路径转化为区间）
3.16 笛卡尔树（Treap/平衡树思想）
3.17 可持久化线段树（主席树）的基本思想
3.18 哈希表的手写实现（开放定址法、链地址法）
搜索进阶
4.1 DFS的剪枝优化（可行性剪枝、最优性剪枝、上下界剪枝）
4.2 记忆化搜索（DFS+备忘录，本质是DP）
4.3 双向BFS（从起点和终点同时搜索，减少状态数）
4.4 迭代加深搜索（IDS，结合DFS的空间与BFS的完备性）
4.5 IDA（迭代加深+A估价函数）
4.6 A*算法的基本原理（$f = g + h$，可采纳启发函数）
4.7 状态压缩BFS（用整数表示状态，位运算加速）
图论算法
5.1 最短路算法对比（Dijkstra、SPFA、Floyd的适用场景与复杂度）
5.2 Dijkstra算法的堆优化（$O(m \log n)$）
5.3 Dijkstra处理负权边的问题（不能处理负权）
5.4 SPFA（队列优化的Bellman-Ford，处理负权、判负环）
5.5 Floyd-Warshall（全源最短路，$O(n^3)$，可判负环）
5.6 差分约束系统（最短路/最长路建模）
5.7 最小生成树的两种算法（Prim $O(n^2)$ / 堆优化$O(m \log n)$，Kruskal $O(m \log m)$）
5.8 Kruskal重构树的基本思想
5.9 拓扑排序的两种实现（Kahn算法、DFS后序）
5.10 拓扑排序判断有向图是否有环
5.11 欧拉路径与欧拉回路的Hierholzer算法
5.12 强连通分量（Tarjan算法，求SCC）
5.13 强连通分量缩点（将原图转化为DAG）
5.14 割点与割边的判定（Tarjan算法，low[]与dfn[]）
5.15 点双连通分量与边双连通分量
5.16 二分图的判定（染色法）
5.17 二分图最大匹配（匈牙利算法，增广路思想）
5.18 最近公共祖先（LCA）的倍增法（$O(\log n)$查询）
5.19 LCA的Tarjan离线算法（并查集+DFS）
5.20 树的重心与树的直径的求法
5.21 树上差分（点差分、边差分）
5.22 子树和与树上倍增
5.23 同余最短路（模意义下的最短路建模）
动态规划进阶
6.1 DP的优化方法总览（空间优化、时间优化）
6.2 滚动数组优化空间（只保留前两维/前一维）
6.3 树形DP（树上最大独立集、树上最小点覆盖、树上背包）
6.4 树形DP换根（二次扫描，求所有节点的答案）
6.5 区间DP（石子合并、矩阵链乘、括号匹配）
6.6 区间DP的四边形不等式优化（$O(n^3) \rightarrow O(n^2)$）
6.7 数位DP（按位统计，状态设计，记忆化搜索实现）
6.8 状态压缩DP（旅行商问题TSP，集合覆盖）
6.9 状态压缩DP的优化（预处理合法状态、转移）
6.10 多维动态规划
6.11 斜率优化DP（维护凸包，单调队列优化）
6.12 四边形不等式优化DP（区间DP的决策单调性）
6.13 单调队列优化DP（滑动窗口最值加速转移）
6.14 数据结构优化DP（线段树/树状数组维护区间最值）
6.15 矩阵快速幂优化DP递推（线性递推加速）
字符串算法
7.1 KMP算法（前缀函数$\pi[i]$，next数组求法，$O(n+m)$匹配）
7.2 KMP的next数组理解与应用（循环节、最小周期）
7.3 字符串哈希（滚动哈希，双哈希防冲突）
7.4 Manacher算法（求最长回文子串，$O(n)$）
7.5 Trie树（字典树，插入、查找、前缀统计）
7.6 Trie树的应用（自动补全、异或最大对）
7.7 AC自动机（多模式串匹配，Trie树+KMP思想）
7.8 后缀数组（SA）的基本概念
7.9 后缀自动机（SAM）的基本概念
7.10 扩展KMP（Z Algorithm，$O(n)$求每个后缀与前缀的LCP）
算法策略
8.1 扫描线算法
8.2 扫描线求矩形面积并/周长并
8.3 扫描线在三维/多维问题中的扩展
8.4 分块算法（根号平衡，大块维护+小块暴力）
8.5 莫队算法（离线区间查询，$O((n+q)\sqrt{n})$）
8.6 带修莫队（支持单点修改的区间查询）
8.7 整体二分（离线解决多个二分答案问题）
8.8 CDQ分治（偏序问题，分治+数据结构）
8.9 倍增法在各类问题中的应用（LCA、RMQ、树上跳）
数学进阶
9.1 扩展欧几里得算法（exgcd，解$ax+by=\gcd(a,b)$）
9.2 模逆元的三种求法（扩展欧几里得、费马小定理、线性递推）
9.3 中国剩余定理（CRT，模数互质）
9.4 扩展中国剩余定理（EXCRT，模数不互质）
9.5 欧拉函数的线性筛法（同时筛质数与欧拉函数）
9.6 快速幂（$O(\log n)$求$a^b \bmod p$）
9.7 矩阵快速幂（加速线性递推，如斐波那契）
9.8 高斯消元法（解线性方程组，$O(n^3)$）
9.9 高斯消元求矩阵的秩
9.10 线性基（求异或空间的最大值/第k小）
9.11 组合数取模（Lucas定理，预处理阶乘与逆元）
9.12 容斥原理在计数问题中的应用
9.13 卡特兰数的递推与通项公式
9.14 离散随机变量的期望与方差
贪心与构造
10.1 贪心正确性的严格证明（交换论证、反证法、归纳法）
10.2 排序贪心的经典模型（区间调度、任务安排）
10.3 优先队列贪心的经典模型（合并果子、哈夫曼编码）
10.4 二分答案+贪心检验（最大化最小值/最小化最大值）
10.5 构造题的基本思路（特殊化、归纳构造、调整法）
10.6 构造题的输出格式与方案验证
时间复杂度与空间复杂度分析（复赛关键）
11.1 数据范围与算法选择的对应关系（$n \le 20$→状压/搜索，$n \le 5000$→$O(n^2)$，$n \le 10^5$→$O(n \log n)$，$n \le 10^6$→$O(n)$）
11.2 常数优化技巧（位运算替代乘除、循环展开、减少取模）
11.3 内存占用的精确计算（int 4B、long long 8B、bool 1B、指针8B）
11.4 递归栈空间的风险评估
11.5 多组测试数据的总复杂度计算
代码调试与对拍技巧
12.1 中间结果输出调试法（printf/cout打印关键变量）
12.2 断言（assert）的使用
12.3 小数据对拍（随机生成+暴力验证）
12.4 边界数据的构造与测试（$n=0$、$n=1$、最大值）
12.5 极端数据的压力测试（内存与时间）
12.6 静态查错（逐行阅读，检查变量名、数组大小、循环边界）
教学 — 2026年7月15日