CSP
2026-09-17 22:08:15
发布于：广东
1阅读
0回复
0点赞
CSP-J/S 初赛与复赛知识整合
覆盖：知识点、易错点、重难点、考点、备考价值内容。
适用：CSP-J（入门级）、CSP-S（提高级）第一轮初赛 + 第二轮复赛。
一、考试概览
| 项目 | CSP-J（入门级） | CSP-S（提高级） |
|---|---|---|
| 初赛形式 | 第一轮笔试，通常 120 分钟，满分 100 | 第一轮笔试，通常 120 分钟，满分 100 |
| 初赛题型 | 单选 15×2=30；阅读程序 3×20=40；完善程序 2×15=30 | 同左，但阅读程序与完善程序难度更高 |
| 复赛形式 | 上机，通常 3.5 小时，4 题，总分 400 | 上机，通常 4 小时，4 题，总分 400 |
| 难度定位 | 入门到普及+/提高- | 提高到省选- |
| 语言 | C++ | C++ |
初赛核心能力
- 计算机基础、网络、操作系统、进制与编码。
- 数据结构性质与计算：树、图、排序、哈希。
- 算法复杂度、递归、分治、贪心、DP、搜索。
- 程序阅读：手动模拟、递归展开、边界判断。
- 完善程序：根据题意和上下文补全代码。
复赛核心能力
- 建模：把题目转化为图论、DP、数据结构问题。
- 实现：模板熟练，边界清晰，调试高效。
- 优化：时间复杂度、空间复杂度、常数优化。
- 策略：保前两题，争后两题部分分。
二、初赛通用知识
1. 计算机基础
| 模块 | 重点 |
|---|---|
| 硬件 | CPU、运算器、控制器、寄存器、Cache、RAM、ROM、外存、总线、I/O 设备 |
| 软件 | 系统软件、应用软件、编译与解释、源程序、目标程序、可执行文件 |
| 操作系统 | 进程、线程、死锁、文件系统、Linux 常用命令 |
| 网络 | OSI 七层、TCP/IP、IP 地址、子网掩码、DNS、HTTP、FTP、路由器、交换机 |
| 数据表示 | 二进制、八进制、十六进制、原码、反码、补码、浮点数、ASCII、Unicode |
2. 进制与编码
- 二进制转十进制：按权展开。
- 十进制转二进制：整数除 2 取余倒序；小数乘 2 取整正序。
- 二、八、十六进制互转：3 位一组或 4 位一组。
- 原码：最高位符号位，0 正 1 负，其余为绝对值。
- 反码：正数同原码；负数符号位不变，数值位取反。
- 补码：正数同原码；负数 = 反码 + 1。
- n 位补码范围：
-2^(n-1) ~ 2^(n-1)-1。 - 8 位补码范围：
-128 ~ 127。
易错：
原码和反码有 +0 与 -0，补码 0 唯一；补码减法转加法，最高进位丢弃；溢出判断看符号位是否异常。
3. 逻辑运算
| A | B | AND | OR | XOR | NAND | NOR | XNOR |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
- 德摩根定律：
(A·B)' = A' + B'，(A+B)' = A'·B'。 - 异或性质：
a^a=0，a^0=a，异或可交换、可结合。
4. 数据结构
| 结构 | 重点 |
|---|---|
| 线性表 | 数组、链表、栈、队列、双端队列、串 |
| 树 | 二叉树性质、遍历、BST、堆、哈夫曼树、完全二叉树、树状数组、线段树 |
| 图 | 邻接矩阵、邻接表、DFS、BFS、最短路、生成树、拓扑排序、连通性 |
| 哈希 | 哈希函数、冲突处理、开放地址法、链地址法 |
二叉树必记：
- 叶子结点数：
n0 = n2 + 1 - 总结点：
n = n0 + n1 + n2 - 完全二叉树编号从 1 开始：左孩子
2i，右孩子2i+1，父结点i/2
5. 排序与查找
| 算法 | 平均 | 最坏 | 空间 | 稳定 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(k) | 稳定 |
- 二分查找必须有序，注意边界
l <= r与mid = l + (r-l)/2。 - 哈希查找平均 O(1)，最坏 O(n)。
6. 算法思想
- 枚举、模拟、递归、分治、贪心、动态规划、搜索、图论、字符串、数学。
- 复杂度：
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)。 - 主定理可用于分析分治复杂度。
7. 数学基础
- 数论：质数、筛法、GCD、LCM、同余、快速幂、逆元。
- 组合：排列组合、二项式定理、杨辉三角、卡特兰数、容斥原理。
- 概率与期望：古典概型、条件概率、期望线性性。
- 进制与位运算：与、或、异或、取反、移位。
三、CSP-J 初赛重点
1. 基础语法与程序阅读
- 变量、数据类型、运算符、优先级、类型转换。
- 分支、循环、数组、字符串、函数、递归。
- 结构体、指针、引用、STL 基础。
- 阅读程序常考：循环模拟、递归展开、字符串处理、排序过程、位运算。
2. 数据结构重点
- 栈：后进先出，括号匹配、表达式求值。
- 队列：先进先出，BFS、模拟。
- 链表：插入、删除、遍历。
- 二叉树：遍历、性质、完全二叉树编号。
- 堆：优先队列、堆调整。
3. 算法重点
- 排序：冒泡、选择、插入、归并、快排、计数排序。
- 查找：顺序、二分。
- 贪心：区间调度、背包分数、哈夫曼。
- 枚举与模拟：日期、进制、矩阵、字符串。
- 简单 DP：背包、LIS、LCS、数字三角形。
- 搜索：DFS、BFS、回溯、剪枝。
- 图论：存图、DFS/BFS、Floyd、Dijkstra、Kruskal。
4. 完善程序常考
- 枚举优化、贪心选择、二分答案。
- 简单 DP 状态与转移。
- 字符串处理、排序、递归。
四、CSP-S 初赛重点
1. 复杂数据结构
- 线段树、树状数组、并查集、堆、平衡树、Trie、哈希表。
- 树链剖分、可持久化、分块、莫队。
2. 图论
- 最短路：Dijkstra、Floyd、Bellman-Ford、SPFA。
- 生成树：Kruskal、Prim。
- 拓扑排序、强连通分量、割点、桥、二分图。
- 差分约束、网络流、费用流、2-SAT、欧拉路。
3. 字符串
- KMP、Z 函数、哈希、Trie、AC 自动机。
- 后缀数组、后缀自动机、回文自动机。
4. 动态规划
- 树形 DP、状压 DP、数位 DP、区间 DP。
- 单调队列优化、斜率优化、四边形不等式、矩阵快速幂。
- 概率期望 DP、DP 套 DP。
5. 数学
- 数论：扩欧、逆元、CRT、BSGS、莫比乌斯反演。
- 组合：组合数取模、容斥、卡特兰、斯特林数。
- 矩阵、高斯消元、博弈论、FFT/NTT、计算几何。
6. 程序阅读与完善
- 复杂递归、STL、位运算、指针、类、模板。
- 完善程序常考高级算法：DP 优化、图论、数据结构。
五、初赛易错点与重难点
易错点
- 补码范围、溢出、原反补转换。
- 二叉树
n0=n2+1、完全二叉树编号、哈夫曼 WPL。 - 图论握手定理：所有顶点度数之和 = 2×边数。
- 排序稳定性、时间复杂度、空间复杂度。
- 二分边界、死循环、
mid取值。 - 位运算优先级：
&低于==，要加括号。 - 浮点误差、整数除法、类型转换。
- 字符串函数：
strlen、strcpy、strcmp、getline。 - 指针与引用、数组越界、野指针。
- 递归调用栈、爆栈、重复计算。
- 哈希冲突、装填因子。
- 卡特兰数、组合数取模、容斥。
- 逻辑门德摩根、异或性质。
- 网络协议层次、IP 地址、子网掩码。
- 存储容量计算：
1KB=1024B，1MB=1024KB。
重难点
- 程序阅读：手动模拟、递归展开、边界判断。
- 完善程序：根据上下文补全，注意初始化、边界、复杂度。
- 数据结构性质：树、图、堆、哈希。
- 算法复杂度：主定理、均摊分析。
- 组合数学：排列组合、卡特兰、容斥。
六、复赛通用知识
1. 文件输入输出
freopen("problem.in", "r", stdin);
freopen("problem.out", "w", stdout);
// 注意文件名必须与题目要求完全一致
2. 常用 STL
| 容器/算法 | 用途 |
|---|---|
vector |
动态数组 |
queue / deque |
队列 / 双端队列 |
stack |
栈 |
priority_queue |
优先队列 / 堆 |
set / map |
有序集合 / 映射 |
unordered_set / unordered_map |
哈希集合 / 哈希映射 |
sort / lower_bound / upper_bound |
排序 / 二分查找 |
next_permutation |
全排列 |
3. 数据类型与边界
int约 2.1×10^9，超过用long long。long long约 9.2×10^18。- 浮点用
double，比较用fabs(a-b) < eps。 - 数组大小开够，防止越界；大数组开全局，避免爆栈。
- 多测要清空：数组、并查集、图、DP、标记。
4. 调试与对拍
- 写暴力程序 + 数据生成器 + 对拍脚本。
- 随机种子固定，便于复现。
- 小数据手算，大数据测复杂度。
- 使用
assert、输出中间变量、分块调试。
七、CSP-J 复赛重点
1. 常考算法
- 模拟、枚举、贪心、二分、前缀和、差分、双指针。
- 搜索：DFS、BFS、回溯、剪枝、记忆化。
- DP：线性 DP、背包、区间 DP、树形 DP、状压 DP 基础。
- 图论：存图、DFS/BFS、拓扑、Dijkstra、Floyd、Kruskal/Prim。
- 数据结构：栈、队列、优先队列、并查集、链表、哈希、树状数组。
- 字符串：模拟、哈希、KMP 基础。
- 数学：GCD、快速幂、质数筛、组合数、高精度。
2. 常考模型
- 区间合并、区间覆盖、区间选点。
- 背包：01 背包、完全背包、多重背包。
- LIS、LCS、数字三角形。
- 网格图 BFS/DFS、连通块。
- 最短路、最小生成树。
- 二分答案 + 贪心检查。
- 前缀和 + 差分优化。
3. 必备模板
// 并查集
int fa[N];
int find(int x){ return fa[x]==x ? x : fa[x]=find(fa[x]); }
void merge(int x,int y){ fa[find(x)]=find(y); }
// 快速幂
long long qpow(long long a,long long b,long long mod){
long long res=1%mod;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
八、CSP-S 复赛重点
1. 高级动态规划
- 树形 DP、状压 DP、数位 DP、区间 DP。
- 单调队列优化、斜率优化、四边形不等式。
- 概率期望 DP、DP 套 DP、矩阵快速幂优化。
2. 数据结构
- 线段树：懒标记、动态开点、线段树合并、扫描线。
- 树状数组：单点修改区间查询、区间修改单点查询、二维。
- 平衡树：Treap、Splay、FHQ Treap。
- 可持久化：主席树、可持久化并查集。
- 树链剖分、LCT、分块、莫队。
3. 图论
- 最短路、生成树、拓扑排序。
- 强连通分量、割点、桥、二分图匹配。
- 差分约束、网络流、费用流、2-SAT、欧拉路。
4. 字符串
- KMP、Z 函数、哈希、Trie、AC 自动机。
- 后缀数组、后缀自动机、回文自动机。
5. 数学
- 数论：扩欧、逆元、CRT、BSGS、莫比乌斯反演。
- 组合：组合数取模、容斥、卡特兰、斯特林数。
- 矩阵、高斯消元、博弈论、FFT/NTT、计算几何。
6. 搜索与技巧
- 剪枝、迭代加深、A*、双向 BFS、DLX。
- 离线、CDQ 分治、整体二分、随机化、模拟退火。
九、复赛易错点与重难点
易错点
freopen文件名错误，导致 0 分。- 数组越界、开小、爆栈。
int溢出，乘法未转long long。- 多测未清空。
- 边界：
n=1、空数据、重复、负数、0。 - 复杂度超时：O(n²) 过大，STL 常数大。
- 递归深度过大爆栈。
- 取模负数：
(a%mod+mod)%mod。 - 字符串末尾
'\0'，cin与getline混用。 - 图论重边、自环、无向边双倍。
- 二分死循环，边界更新错误。
- DP 初值错误、转移顺序错误、空间优化越界。
- 排序比较函数必须严格弱序。
- 编译标准、头文件、变量名冲突。
重难点
- J 组：DP、搜索剪枝、图论、二分、贪心证明。
- S 组：高级 DP、数据结构、图论建模、数学推导、代码实现。
- 共同难点：把题意转化为模型，并在限定时间内写对。
十、高频考点与备考建议
初赛高频考点
- 进制转换、原码反码补码、逻辑运算。
- 树与二叉树性质、图论度数、排序复杂度。
- 递归、分治、贪心、简单 DP、搜索。
- 网络、操作系统、计算机组成。
- 程序阅读与完善程序。
J 组复赛高频考点
- 模拟、枚举、贪心、二分、前缀和、差分。
- DP：背包、LIS、LCS、区间、树形。
- 搜索：DFS/BFS、剪枝、记忆化。
- 图论：最短路、生成树、拓扑。
- 数据结构：栈、队列、优先队列、并查集、树状数组。
S 组复赛高频考点
- DP：树形、状压、数位、区间、优化。
- 数据结构：线段树、树状数组、平衡树、可持久化。
- 图论：SCC、割点、二分图、网络流、差分约束。
- 字符串：KMP、哈希、Trie、ACAM。
- 数学：数论、组合、矩阵、高斯消元、博弈。
备考建议
- 初赛：刷近 10 年真题，限时训练，错题本记录易错点。
- 程序阅读：手算模拟，画出变量表、递归树、栈帧。
- 完善程序：先读题意，再看上下文，注意初始化、边界、复杂度。
- 复赛：专题突破，模板熟练，每类算法至少 10 题。
- 对拍：暴力 + 生成器 + 对拍，确保正确性。
- 比赛策略：先易后难，前两题保稳，后两题骗部分分。
- 时间分配：读题 10 分钟，前两题 60~90 分钟，后两题剩余时间。
- 代码规范：变量名清晰，函数封装，边界特判。
十一、附录：常用公式、复杂度与模板索引
1. 常用公式
- 二叉树：
n0 = n2 + 1，总结点n = n0 + n1 + n2。 - 完全二叉树：编号从 1 开始，左孩子
2i，右孩子2i+1。 - 图论：所有顶点度数之和 =
2m，m为边数。 - 卡特兰数：
C_n = C(2n,n)/(n+1)。 - 组合数：
*****) = C(n-1,m) + C(n-1,m-1)。 - 等比数列求和：
S_n = a1(1-q^n)/(1-q)。 - 主定理：
T(n)=aT(n/b)+f(n)。
2. 复杂度速查
| 复杂度 | 典型算法 |
|---|---|
| O(1) | 哈希查找、位运算 |
| O(log n) | 二分、快速幂 |
| O(n) | 线性扫描、前缀和 |
| O(n log n) | 归并排序、快排、堆排 |
| O(n²) | 冒泡、选择、插入、Floyd |
| O(2^n) | 子集枚举、状压搜索 |
| O(n!) | 全排列枚举 |
3. 模板索引
- 并查集、快速幂、GCD、扩展欧几里得。
- Dijkstra、Floyd、Kruskal、拓扑排序。
- 线段树、树状数组、LCA、KMP。
- 01 背包、完全背包、LIS、LCS、区间 DP。
- DFS、BFS、剪枝、记忆化搜索。
最后提醒：
初赛决定能否进复赛，复赛决定奖项。初赛靠真题和细节，复赛靠模板、思维和代码能力。把本文当目录，逐项补漏，效果最好。
这里空空如也
有帮助，赞一个