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 函数

最优化

  • 单纯形法

计算几何

  • 点，线，面之间位置关系的判定
  • 一般图形面积的计算
  • 二维凸包
  • 半平面交

信息论

  • 熵，互信息，条件熵，相对熵

其 他

  • 信息复杂度的概念
  • 描述复杂度的概念
  • 通讯复杂度的概念