CCF考纲
CSP-J
程序基本概念1.0
- 标识符，关键字，常量，变量，字符串，表达式的概念
- 常量与变量的命名，定义及作用
- 头文件与名字空间的概念
- 编辑，编译，解释，调试的概念
基本数据类型
- 整数型：
int，long long - 实数型：
float，double - 字符型：
char - 布尔型：
bool
程序基本语句
cin语句，scanf语句，cout语句，printf语句，赋值语句，复合语句if语句，switch语句，多层条件语句for语句，while语句，do while语句- 多层循环语句
基本运算
- 算术运算：加，减，乘，除，整除，求余
- 关系运算：大于，大于等于，小于， 小于等于，等于，不等于
- 逻辑运算：与（\(\&\&\)），或（\(||\)），非（\(!\)）
- 变量自增与自减运算
- 三目运算
- 位运算：与（\(\&\)），或（\(|\)），非（~）， 异或（^），左移（\(<<\)），右移（\(>>\)）
数学库常用函数
- 绝对值函数，四舍五入函数
- 下取整函数， 上取整函数
- 平方根函数，常用三角函数
- 对数函数，指数函数
结构化程序设计
- 顺序结构，分支结构和循环结构
- 自顶向下，逐步求精的模块化程序设计
- 流程图的概念及流程图描述
数组
- 数组与数组下标
- 数组的读入与输出
- 二维数组与多维数组
字符串的处理
- 字符数组与相关函数
- string 类与相关函数
函数与递归
- 函数定义与调用，形参与实参
- 传值参数与传引用参数
- 常量与变量的作用范围
- 递归函数
结构体与联合体
- 结构体
- 联合体
指针类型
- 指针
- 基于指针的数组访问
- 字符指针
- 指向结构体的指针
文件及基本读写
- 文件的基本概念，文本文件的基本操作
- 文本文件类型与二进制文件类型
- 文件重定向，文件读写等操作
STL 模板
- 算法模板库中的函数：
min，max，swap，sort - 栈 （
stack），队列 （queue），链表 （list），向量（vector）等容器
线性结构
- 链表：单链表，双向链表，循环链表
- 栈
- 队列
简单树
- 树的定义与相关概念
- 树的表示与存储
- 二叉树的定义与基本性质
- 二叉树的表示与存储
- 二叉树的遍历：前序，中序，后序
特殊树
- 完全二叉树的定义与基本性质
- 完全二叉树的数组表示法
- 哈夫曼树的定义和构造，哈夫曼编码
- 二叉搜索树的定义和构造
简单图
- 图的定义与相关概念
- 图的表示与存储：邻接矩阵
- 图的表示与存储：邻接表
算法概念与描述
- 算法概念
- 算法描述：自然语言描述，流程图描述， 伪代码描述
入门算法
- 枚举法
- 模拟法
基础算法
- 贪心法
- 递推法
- 递归法
- 二分法
- 倍增法
数值处理算法
- 高精度的加法
- 高精度的减法
- 高精度的乘法
- 高精度整数除以单精度整数的商和余数
排序算法
- 排序的基本概念
- 冒泡排序
- 选择排序
- 插入排序
- 计数排序
搜索算法
- 深度优先搜索
- 广度优先搜索
图论算法
- 深度优先遍历
- 广度优先遍历
- 泛洪算法（flood fill）
动态规划
- 动态规划的基本思路
- 简单一维动态规划
- 简单背包类型动态规划
- 简单区间类型动态规划
数及其运算
- 自然数，整数，有理数，实数及其算术运算（加，减，乘，除）
- 进制与进制转换：二进制，八进制， 十进制，十六进制
初等数学
- 代数（初中部分）
- 几何（初中部分）
初等数论
- 整除，因数，倍数，指数，质（素） 数， 合数
- 取整
- 模运算与同余
- 整数唯一分解定理
- 辗转相除法（欧几里得算法）
- 素数筛法：埃氏筛法与线性筛法
离散与组合数学
- 集合
- 加法原理
- 乘法原理
- 排列
- 组合
- 杨辉三角
其他
- ASCII 码
- 格雷码
CSP-S
类（class）
- 类的概念及简单应用
- 成员函数和运算符重载
STL 模板
- 容器（
container）和迭代器（iterator） - 集合（
set），多重集合（multiset） - 双端队列（
deque），优先队列（priority_queue） - 映射（
map），多重映射（multimap） - 算法模板库中的常用函数
线性 结构
- 双端栈
- 双端队列
- 单调队列
- 优先队列
- ST 表（Sparse Table）
集合与森林
- 并查集
- 树的孩子兄弟表示法
特殊 树
- 二叉堆
- 树状数组
- 线段树
- 字典树（Trie 树）
- 笛卡尔树
- 平衡树：AVL，treap，splay 等
常见图
- 稀疏图
- 偶图（二分图）
- 欧拉图
- 有向无环图
- 连通图与强连通图
- 双连通图
哈希表
- 数值哈希函数构造
- 字符串哈希函数构造
- 哈希冲突的常用处理方法
复杂度分析
- 时间复杂度分析
- 空间复杂度分析
算法策略
- 离散化
基础 算法
- 分治算法
排序 算法
- 归并排序
- 快速排序
- 堆排序
- 桶排序
- 基数排序
字符串相关算法
- 字符串匹配：KMP 算法
搜索 算法
- 搜索的剪枝优化
- 记忆化搜索
- 启发式搜索
- 双向广度优先搜索
- 迭代加深搜索
图论 算法
- 最小生成树：Prim和 Kruskal 等算法
- 次小生成树
- 单源最短路：Bellman-Ford，Dijkstra， SPFA 等算法
- 单源次短路
- Floyd-Warshall 算法
- 有向无环图的拓扑排序
- 欧拉道路和欧拉回路
- 二分图的判定
- 强连通分量
- 割点，割边
- 树的重心，直径，DFS 序与欧拉序
- 树上差分，子树和与倍增
- 最近公共祖先
动态 规划
- 树型动态规划
- 状态压缩动态规划
- 动态规划的常用优化
初等 数学
- 代数（高中部分）
- 几何（高中部分）
初等 数论
- 同余式
- 欧拉定理和欧拉函数
- 费马小定理
- 威尔逊定理
- 裴蜀定理
- 模运算意义下的逆元
- 扩展欧几里得算法
- 中国剩余定理
离散与 组合数学
- 多重集合
- 等价类
- 多重集上的排列
- 多重集上的组合
- 错排列，圆排列
- 鸽巢原理
- 二项式定理
- 容斥原理
- 卡特兰（Catalan）数
线性代数
- 向量与矩阵的概念
- 向量的运算
- 矩阵的初等变换
- 矩阵的运算：加法，减法，乘法与转置
- 特殊矩阵的概念：单位阵，三角阵， 对称阵和稀疏矩阵
- 高斯消元法
NOI
线性结 构
- 块状链表
序列
- 跳跃表
复杂树
- 树链剖分
- 动态树：LCT
- 二维线段树
- 树套树
- k-d 树
- 虚树
可合并堆
- 左偏树
- 二项堆
可持久化数据结构
- 可持久化线段树
- 其他可持久化数据结构
算法 策略
- 分块
- 离线处理思想
- 复杂分治思想
- 平衡规划思想
- 构造思想
字符串算法
- Manacher 算法
- 扩展 KMP 算法
- 有穷自动机
- AC 自动机
- 后缀数组
- 后缀树
- 后缀自动机
图论算 法
- 基环树
- 最小树形图
- 2-SAT
- 网络流
- 图的支配集，独立集与覆盖集
- 匈牙利算法
- KM 算法
- 一般图的匹配
动态规 划
- 复杂动态规划模型的构建
- 复杂动态规划模型的优化
初等数 论
- 原根和指数
- 大步小步（Baby Step Giant Step，BSGS） 算法
- 狄利克雷（Dirichlet）卷积
- 二次剩余
- 二次同余式
离散与组 合数学
- 群及其基本性质
- 置换群与循环群
- 母函数
- 莫比乌斯反演
- Burnside 引理与 Pólya 定理
- 斯特林（Stirling）数
- 无根树的 Prüfer 序列
线性 代数
- 逆矩阵
- 行列式
- 向量空间与线性相关
高等数学
- 多项式函数的微分
- 多项式函数的积分
- 泰勒（Taylor）级数
- 快速傅里叶变换
概率论
- 概率的基本概念
- 随机变量的期望与方差
- 条件概率
- 贝叶斯公式
博弈论
- 尼姆（Nim）博弈
- SG 函数
最优化
- 单纯形法
计算几何
- 点，线，面之间位置关系的判定
- 一般图形面积的计算
- 二维凸包
- 半平面交
信息论
- 熵，互信息，条件熵，相对熵
其 他
- 信息复杂度的概念
- 描述复杂度的概念
- 通讯复杂度的概念