信息学奥赛知识点大纲
题单介绍
本题单参考[此处题单](https://www.luogu.com.cn/training/9391#information)
1. [**oi-wiki知识点网页**](https://oi-wiki.org/)
2. [**洛谷《深入浅出程序设计》竞赛的课件**](https://www.luogu.com.cn/training/61297)
# 目录
## [Part 1 入门阶段]
### 入门级
- [顺序结构](https://www.luogu.com.cn/training/62606)
- [分支结构](https://www.luogu.com.cn/training/70089)
- [循环结构](https://www.luogu.com.cn/training/70090)
- 数组
- 字符与字符串
- 结构体和函数
- 递归
- 指针（不常用）
- 文本操作（NOI系列赛事必备）
### 提高级
- STL模板
### NOI级
- STL模板
## [Part 2 基础算法]
### 入门级
- 模拟与枚举
- 高精度
- 排序算法
- 贪心
- 二分法
- 倍增法
- 递归法
- 分治
- 前缀和 & 差分
- 快速幂
- 双指针
### 提高级
- 排序 2
- 深度优先搜索
- 广度优先搜索
- 记忆化搜索
- 搜索的剪枝
### NOI级
- 复杂分治
- 平衡规划
- 构造
## [Part 3 数据结构]
### 入门级
- 链表(list)
- 栈(stack)
- 队列(queue)
### 提高级
- 栈和队列
- 优先队列
- 二叉堆
- ST表
- 树状数组
- 线段树
- 二叉平衡树
### NOI级
- 分块
- 跳跃表
- prufer序列
- 树链剖分
- 主席树
- 二维线段树
- 树套树
- K-D Tree
- 最小树形图
- 动态树（LCT）
- 可并堆
- 可持久化数据结构
## [Part 4 树与图]
### 入门级
- 树
- 图的遍历
### 提高级
- 树 强化
- 基环树
- 图的遍历 强化
- 最短路
- 并查集
- 生成树
- 拓扑排序
- 强连通分量
- 缩点与割边
- 最近公共祖先LCA
### NOI级
- 二分图
- 网络流
- 最大流
- 最小割
- 费用流
- 上下界网络流
### 其他
- 2-SAT
- 点分治
- 虚树
- 矩阵树定理
## [Part 5 动态规划]
### 入门级
- 递推
- 线性动态规划
- 背包动态规划
- 区间动态规划
### 提高级
- 树形动态规划
- 状态压缩动态规划
- 倍增优化动态规划
- 数据结构优化动态规划
- 单调队列优化动态规划
### NOI级
- 斜率优化动态规划
- 决策单调性优化动态规划
- 数位统计类动态规划
- 轮廓线动态规划
## [Part 5 数学]
### 入门级
- 位运算
- 进制转换与初中数学
- 初等数论
- 整除相关
- 素数与最大公约数
- 组合数学
### 提高级
- 高中数学
- 初等数论
- 同余基础
- 欧拉函数
- 中国剩余定理
- 组合数学
- 排列组合
- 容斥原理
- 卡特兰数
- 线性代数
- 矩阵
- 高斯消元
- 概率与期望
### NOI级
- 初等数论
- 原根和指数
- 完全数
- 高次剩余
- 置换群
- 母函数（生成函数）
- 莫比乌斯反演
- Burnside引理和Polya原理
- 斯特林数
- 高等数学
- 多项式函数微积分
- 泰勒级数
- 快速傅里叶变换FFT
- 卷积
- 线性代数
- 矩阵逆运算
- 行列式
- 线性基
- 概率乘法公式，全概率公式，贝叶斯公式
- 博弈论
- 线性规划
- 信息论基础
## [Part 6 字符串]
### 提高级
- 字符串哈希
- KMP
- Trie树
### NOI级
- Manacher算法
- AC自动机
- 扩展kmp
- 后缀数组
- 后缀树
- 后缀自动机
- 回文自动机
- DFA和NFA算法
## [Part 7 计算几何](https://www.luogu.com.cn/training/9387)
### NOI级
- 计算几何基础
- 凸包
- 旋转卡壳
- 半平面交
## [Part 8 其他](https://www.luogu.com.cn/training/9388)
- 模拟退火
- 0/1 分数规划
- 离线算法
- CDQ 分治
- 整体二分
- 莫队
## 综合
待续