信息学竞赛知识大纲
======
|Author|杜博识Dubos|
|---|---|
|E-mail|dubos@foxmail.com|
------
OI (Olympiads in Informatics)，国内译作`信息学竞赛`（或`信息学奥林匹克`、`程序设计竞赛`、`算法竞赛`）。本文为知识大纲，点击知识点即可进入对应讲义，但大纲是按照知识点归类排序的，与学习顺序并不完全相同，各个讲义是按照学习顺序编号的。信息学竞赛参赛过程、升学政策与各年级学习安排具体见：《[NOIP 00 信息学竞赛与升学](/NOIP%2000%20信息学竞赛与升学.md)》
## NOIP普及组
* C++入门
1. [入门：基本数据类型，常量与变量，赋值，算术表达式，整除与求余，模运算，数制转化，输入输出][NOIP 01 a]，[文件操作][NOIP 01 b]
3. [程序的控制结构，逻辑表达式，逻辑运算，关系表达式，复合语句，条件语句，循环语句，条件嵌套，循环嵌套][NOIP 02]
4. [数组：一维数组][NOIP 03 a]，[二维数组][NOIP 03 b]，[字符数组][NOIP 03 c]，[字符串string][NOIP 03 d]，字符串cstring，[高精度计算][NOIP 03 f]
5. [指针，引用][NOIP 04]
5. [函数，常用数学函数（幂函数、指数函数、对数函数、三角函数、随机函数）][NOIP 05 a]
6. [结构体，自定义数据类型][NOIP 06]
* [算法普及组][NOIP 07 a]：
1. 时间复杂度，空间复杂度
2. 位运算
3. 模拟，枚举，回溯
4. 排序：选择，插入，冒泡；堆排序，归并，快排；计数，基数，桶排序
5. 搜索，深度优先搜索DFS，广度优先搜索BFS，剪枝
6. 贪心
7. 递归
8. 分治，二分
9. STL算法
* [数据结构普及组][NOIP 08 a]
1. [线性数据结构][NOIP 08 b]：[顺序表][NOIP 08 b 顺序表]，~~数组~~（C++入门讲过了），[向量（或动态数组）][NOIP 08 b 向量]，链表，双端队列，栈，队列，优先队列，STL顺序容器和容器适配器]
2. [树：二叉树的存储与遍历，STL关联容器，集合，映射][NOIP 08 c]
3. 图：邻接矩阵，邻接表，图的遍历，用DFS求连通块，用BFS求最短路，Euler回路，Hamiltonian回路
* 数学普及组：
1. 数论：素数与合数，最大公约数，辗转相除法（Euclidean算法），最小公倍数，互质数，整数的质因数分解，筛法
2. 快速幂运算：反复平方法（Russian Peasant算法）
3. 排列组合与集合：加法原理，乘法原理，圆排列，可重集排列，鸽笼原理，容斥原理，二项式定理与杨辉三角形
* 动态规划普及组：数字三角形，记忆化搜索，最长上升子序列LIS，最长公共子序列LCS，背包
## NOIP提高组
* 数学提高组：
1. 数论：拓展欧几里得算法，中国剩余定理，剩余类，费马小定理，欧拉定理，母函数
2. 概率，数学期望
3. 矩阵，线性方程组
4. 解析几何
5. 函数的连续性、单调性和极值，数列与级数
* 动态规划提高组：有向无环图DAG上的动态规划，树形动态规划，环形动态规划，后效性处理，状态压缩，倍增优化
* 数据结构提高组：
1. 二叉堆， 并查集，线段树，主席树，二叉索引树/树状数组BIT，区间最值问题RMQ，ST算法，哈夫曼Huffman树
2. 字典树Trie，哈希表Hash与字符串，KMP算法，AC自动机，后缀数组，后缀树
* 图论提高组：
1. 最小生成树MST，Kruskal算法，Prim算法，最近公共祖先LCA，最小有向生成树/最小树形图
3. 单源最短路SSSP，Dijkstra算法，Bellman-Ford算法及其SPFA优化，Floyd-Warshall算法，负环/负圈，差分约束
3. 连通性：强连通分量SCC，Trajan算法，Kosaraju算法，2-SAT问题
4. 拓扑排序
## 省选与NOI
* 数学决赛：
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. 树套树：线段树套线段树，线段树套平衡树，平衡树套线段树
2. 树链剖分，动态树LCT
3. 分块，块状链表，[莫队算法][莫] [MO’s Algorithm][MO]
4. 可持久化数据结构
* 图论决赛：
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简介》](/NOIP%2000%20OJ简介.md)
###### 相关文件：
> [《关于NOI系列赛编程语言使用限制的规定》](http://www.noi.cn/about/rules/362-noi)
> [《CCF中学生程序设计等级评价体系》](/CCF中学生程序设计等级评价体系.pdf)
[NOIP 01 a]:/NOIP%20Junior/NOIP%2001%20a%20C%2B%2B入门.cpp
[NOIP 01 b]:/NOIP%20Junior/NOIP%2001%20b%20文件.md
[NOIP 02]:/NOIP%20Junior/NOIP%2002%20程序的控制结构.cpp
[NOIP 03 a]:/NOIP%20Junior/NOIP%2003%20a%20一维数组.cpp
[NOIP 03 b]:/NOIP%20Junior/NOIP%2003%20b%20二维数组.cpp
[NOIP 03 c]:/NOIP%20Junior/NOIP%2003%20c%20字符数组.cpp
[NOIP 03 d]:/NOIP%20Junior/NOIP%2003%20d%20string字符串.cpp
[NOIP 03 f]:/NOIP%20Junior/NOIP%2003%20f%20高精度计算.cpp
[NOIP 04]:/NOIP%20Junior/NOIP%2004%20指针与引用.cpp
[NOIP 05 a]:/NOIP%20Junior/NOIP%2005%20a%20函数.cpp
[NOIP 06]:/NOIP%20Junior/NOIP%2006%20结构体.md
[NOIP 07 a]:/NOIP%20Junior/NOIP%2007%20a%20算法普及组.md
[NOIP 08 a]:/NOIP%20Junior/NOIP%2008%20a%20普及组数据结构.md
[NOIP 08 b]:/NOIP%20Junior/NOIP%2008%20b%20线性数据结构.md
[NOIP 08 b 顺序表]:/NOIP%20Junior/NOIP%2008%20b%20线性数据结构.md#顺序表sequence-list
[NOIP 08 b 向量]:/NOIP%20Junior/NOIP%2008%20b%20线性数据结构.md#向量或称动态数组vector
[NOIP 08 c]:/NOIP%20Junior/NOIP%2008%20c%20树.md
[MO]:https://blog.anudeep2011.com/mos-algorithm/
[莫]:https://www.zhihu.com/question/27316467
信息学竞赛，国内官方网站为：.zip
版权申诉
170 浏览量
2023-12-01
15:56:48
上传
评论
收藏 2.77MB ZIP 举报
信息学竞赛，国内官方网站为：.zip （35个子文件） 
Graduation Design 
CCF中学生程序设计等级评价体系.pdf 1.19MB NOIP Junior 
NOIP 08 c 树.md 857B NOIP 01 a C++入门.cpp 16KB NOIP 04 指针与引用.cpp 14KB NOIP 03 f 高精度计算 除法.md 299B NOIP 01 b 文件.md 5KB NOIP 03 c 字符数组.cpp 8KB NOIP 08 b 线性数据结构.md 24KB NOIP 03 a 一维数组.cpp 14KB NOIP 05 a 函数.cpp 14KB NOIP 07 a 算法普及组.md 4KB NOIP 03 d string字符串.cpp 20KB NOIP 03 f 高精度计算.cpp 14KB README.md 84B NOIP 03 b 二维数组.cpp 9KB NOIP 06 结构体.md 1KB NOIP 08 a 数据结构普及组.md 12KB NOIP 02 程序的控制结构.cpp 14KB NOIP 00 信息学竞赛与升学.md 19KB NOIP 00 OJ简介.md 9KB diagrams 
NOI 04 A Self_Adjusting Search Tree by Jorge Stolfi.jpg 212KB
NOIP 08 b 顺序表2.gif 1KB
NOIP 07 STL Container Types.png 70KB NOIP 08 b 1956 Dartmouth Conference.jpg 118KB NOIP 08 b Deletion from a List.JPG 34KB 表情包试验.gif 79KB NOIP 03 f 高精度计算 除法.png 673KB NOIP 07 STL Components.JPG 35KB NOIP 08 b 双向链表.jpg 390KB NOIP 08 b 顺序表3.gif 897B NOIP 08 b Simon Newell.jpg 35KB NOIP 08 b List of elements.JPG 45KB NOIP 08 b 顺序表1.jpg 62KB NOIP 08 a KnuthAtOpenContentAlliance.jpg 44KB README.md 7KB资源评论
