Author | 杜博识Dubos |
---|---|
dubos@foxmail.com |
OI (Olympiads in Informatics),国内译作信息学竞赛
(或信息学奥林匹克
、程序设计竞赛
、算法竞赛
)。本文为知识大纲,点击知识点即可进入对应讲义,但大纲是按照知识点归类排序的,与学习顺序并不完全相同,各个讲义是按照学习顺序编号的。信息学竞赛参赛过程、升学政策与各年级学习安排具体见:《NOIP 00 信息学竞赛与升学》
-
C++入门
-
- 时间复杂度,空间复杂度
- 位运算
- 模拟,枚举,回溯
- 排序:选择,插入,冒泡;堆排序,归并,快排;计数,基数,桶排序
- 搜索,深度优先搜索DFS,广度优先搜索BFS,剪枝
- 贪心
- 递归
- 分治,二分
- STL算法
-
- 线性数据结构:顺序表,
数组(C++入门讲过了),向量(或动态数组),链表,双端队列,栈,队列,优先队列,STL顺序容器和容器适配器] - 树:二叉树的存储与遍历,STL关联容器,集合,映射
- 图:邻接矩阵,邻接表,图的遍历,用DFS求连通块,用BFS求最短路,Euler回路,Hamiltonian回路
- 线性数据结构:顺序表,
-
数学普及组:
- 数论:素数与合数,最大公约数,辗转相除法(Euclidean算法),最小公倍数,互质数,整数的质因数分解,筛法
- 快速幂运算:反复平方法(Russian Peasant算法)
- 排列组合与集合:加法原理,乘法原理,圆排列,可重集排列,鸽笼原理,容斥原理,二项式定理与杨辉三角形
-
动态规划普及组:数字三角形,记忆化搜索,最长上升子序列LIS,最长公共子序列LCS,背包
-
数学提高组:
- 数论:拓展欧几里得算法,**剩余定理,剩余类,费马小定理,欧拉定理,母函数
- 概率,数学期望
- 矩阵,线性方程组
- 解析几何
- 函数的连续性、单调性和极值,数列与级数
-
动态规划提高组:有向无环图DAG上的动态规划,树形动态规划,环形动态规划,后效性处理,状态压缩,倍增优化
-
数据结构提高组:
- 二叉堆, 并查集,线段树,主席树,二叉索引树/树状数组BIT,区间最值问题RMQ,ST算法,哈夫曼Huffman树
- 字典树Trie,哈希表Hash与字符串,KMP算法,AC自动机,后缀数组,后缀树
-
图论提高组:
- 最小生成树MST,Kruskal算法,Prim算法,最近公共祖先LCA,最小有向生成树/最小树形图
- 单源最短路SSSP,Dijkstra算法,Bellman-Ford算法及其SPFA优化,Floyd-Warshall算法,负环/负圈,差分约束
- 连通性:强连通分量SCC,Trajan算法,Kosaraju算法,2-SAT问题
- 拓扑排序
-
数学决赛:
- 博弈论SG函数,Nim
- 群,置换群,Burnside定理,Polya原理
- 快速傅里叶变换FFT
- 莫比乌斯反演
- 模拟退火算法
- 线性规划
-
动态规划决赛:数据结构优化DP,单调队列优化DP,斜率优化,四边形不等式,计数类DP,数位统计DP,双重动态规划,基于连通性的动态规划
-
计算几何决赛
- 基本运算,点积,叉积,点和直线,多边形
- 圆和球
- 二维几何:点在多边形内的判定,凸包,半平面,平面区域
- 三维几何
- 多边形的布尔计算
-
数据结构决赛:
- 二叉查找树/二叉排序树BST,平衡树Treap,伸展树Splay,平衡二叉树SBT
- 树套树:线段树套线段树,线段树套平衡树,平衡树套线段树
- 树链剖分,动态树LCT
- 分块,块状链表,莫队算法 MO’s Algorithm
- 可持久化数据结构
-
图论决赛:
- 二分图:二分图的构造,二分图的匹配,匈牙利算法,KM算法(Kuhn-Munkres算法),Hopcroft-Karp算法,一般图的匹配
- 网络流:最大流问题,Ford-Fulkerson增广路径算法与Edmonds-Karp算法,Dinic算法,ISAP算法,最大流最小割定理,最小费用最大流问题
- 启发式搜索:A* 算法,IDA* 算法
信息学竞赛跟数理化生竞赛不同的是,做题可以用在线测评系统(Online Judge)评分:100:。除了公平、高效之外,还有一个好处是让用户看到许多其他用户的水平,这样就可以了解到其他学校、城市、省份乃至国家的选手:raising_hand:。当然OJ平台也有很多,有的主要用于学习阶段刷题,有的是学成之后去与高手切磋的,不同学习阶段用不同的平台。关于Online Judge的更多内容见《OJ简介》