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. 文件输入输出
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. 必备模板
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
八、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。
* 数学：数论、组合、矩阵、高斯消元、博弈。
备考建议
1. 初赛：刷近 10 年真题，限时训练，错题本记录易错点。
2. 程序阅读：手算模拟，画出变量表、递归树、栈帧。
3. 完善程序：先读题意，再看上下文，注意初始化、边界、复杂度。
4. 复赛：专题突破，模板熟练，每类算法至少 10 题。
5. 对拍：暴力 + 生成器 + 对拍，确保正确性。
6. 比赛策略：先易后难，前两题保稳，后两题骗部分分。
7. 时间分配：读题 10 分钟，前两题 60~90 分钟，后两题剩余时间。
8. 代码规范：变量名清晰，函数封装，边界特判。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十一、附录：常用公式、复杂度与模板索引
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、剪枝、记忆化搜索。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
最后提醒：
初赛决定能否进复赛，复赛决定奖项。初赛靠真题和细节，复赛靠模板、思维和代码能力。把本文当目录，逐项补漏，效果最好。
