OI (Olympiads in Informatics)，国内译作信息学竞赛（或信息学奥林匹克、程序设计竞赛、算法竞赛）。本文为知识大纲，点击知识点即可进入对应讲义，但大纲是按照知识点归类排序的，与学习顺序并不完全相同，各个讲义是按照学习顺序编号的。信息学竞赛参赛过程、升学政策与各年级学习安排具体见：《NOIP 00 信息学竞赛与升学》

• C++入门

  1. 入门：基本数据类型，常量与变量，赋值，算术表达式，整除与求余，模运算，数制转化，输入输出，文件操作
  2. 程序的控制结构，逻辑表达式，逻辑运算，关系表达式，复合语句，条件语句，循环语句，条件嵌套，循环嵌套
  3. 数组：一维数组，二维数组，字符数组，字符串string，字符串cstring，高精度计算
  4. 指针，引用
  5. 函数，常用数学函数（幂函数、指数函数、对数函数、三角函数、随机函数）
  6. 结构体，自定义数据类型

• 算法普及组：

  1. 时间复杂度，空间复杂度
  2. 位运算
  3. 模拟，枚举，回溯
  4. 排序：选择，插入，冒泡；堆排序，归并，快排；计数，基数，桶排序
  5. 搜索，深度优先搜索DFS，广度优先搜索BFS，剪枝
  6. 贪心
  7. 递归
  8. 分治，二分
  9. STL算法

• 数据结构普及组

  1. 线性数据结构：顺序表，数组（C++入门讲过了），向量（或动态数组），链表，双端队列，栈，队列，优先队列，STL顺序容器和容器适配器]
  2. 树：二叉树的存储与遍历，STL关联容器，集合，映射
  3. 图：邻接矩阵，邻接表，图的遍历，用DFS求连通块，用BFS求最短路，Euler回路，Hamiltonian回路

• 数学普及组：

  1. 数论：素数与合数，最大公约数，辗转相除法（Euclidean算法），最小公倍数，互质数，整数的质因数分解，筛法
  2. 快速幂运算：反复平方法（Russian Peasant算法）
  3. 排列组合与集合：加法原理，乘法原理，圆排列，可重集排列，鸽笼原理，容斥原理，二项式定理与杨辉三角形

• 动态规划普及组：数字三角形，记忆化搜索，最长上升子序列LIS，最长公共子序列LCS，背包

• 数学提高组：

  1. 数论：拓展欧几里得算法，**剩余定理，剩余类，费马小定理，欧拉定理，母函数
  2. 概率，数学期望
  3. 矩阵，线性方程组
  4. 解析几何
  5. 函数的连续性、单调性和极值，数列与级数

• 动态规划提高组：有向无环图DAG上的动态规划，树形动态规划，环形动态规划，后效性处理，状态压缩，倍增优化

• 数据结构提高组：

  1. 二叉堆， 并查集，线段树，主席树，二叉索引树/树状数组BIT，区间最值问题RMQ，ST算法，哈夫曼Huffman树
  2. 字典树Trie，哈希表Hash与字符串，KMP算法，AC自动机，后缀数组，后缀树

• 图论提高组：

  1. 最小生成树MST，Kruskal算法，Prim算法，最近公共祖先LCA，最小有向生成树/最小树形图
  2. 单源最短路SSSP，Dijkstra算法，Bellman-Ford算法及其SPFA优化，Floyd-Warshall算法，负环/负圈，差分约束
  3. 连通性：强连通分量SCC，Trajan算法，Kosaraju算法，2-SAT问题
  4. 拓扑排序

• 数学决赛：

  1. 博弈论SG函数，Nim
  2. 群，置换群，Burnside定理，Polya原理
  3. 快速傅里叶变换FFT
  4. 莫比乌斯反演
  5. 模拟退火算法
  6. 线性规划

• 动态规划决赛：数据结构优化DP，单调队列优化DP，斜率优化，四边形不等式，计数类DP，数位统计DP，双重动态规划，基于连通性的动态规划

• 计算几何决赛

  1. 基本运算，点积，叉积，点和直线，多边形
  2. 圆和球
  3. 二维几何：点在多边形内的判定，凸包，半平面，平面区域
  4. 三维几何
  5. 多边形的布尔计算

• 数据结构决赛：

  1. 二叉查找树/二叉排序树BST，平衡树Treap，伸展树Splay，平衡二叉树SBT
  2. 树套树：线段树套线段树，线段树套平衡树，平衡树套线段树
  3. 树链剖分，动态树LCT
  4. 分块，块状链表，莫队算法 MO’s Algorithm
  5. 可持久化数据结构

• 图论决赛：

  1. 二分图：二分图的构造，二分图的匹配，匈牙利算法，KM算法（Kuhn-Munkres算法)，Hopcroft-Karp算法，一般图的匹配
  2. 网络流：最大流问题，Ford-Fulkerson增广路径算法与Edmonds-Karp算法，Dinic算法，ISAP算法，最大流最小割定理，最小费用最大流问题
  3. 启发式搜索：A* 算法，IDA* 算法

信息学竞赛跟数理化生竞赛不同的是，做题可以用在线测评系统（Online Judge）评分:100:。除了公平、高效之外，还有一个好处是让用户看到许多其他用户的水平，这样就可以了解到其他学校、城市、省份乃至国家的选手:raising_hand:。当然OJ平台也有很多，有的主要用于学习阶段刷题，有的是学成之后去与高手切磋的，不同学习阶段用不同的平台。关于Online Judge的更多内容见《OJ简介》

《关于NOI系列赛编程语言使用限制的规定》
《CCF中学生程序设计等级评价体系》