从零开始的OI学习之路

· · 个人记录

简介

从语言到省选的知识点，每个知识点附有前置知识，可能还会有学习笔记

前置知识为必要顺序，有序列表为推荐顺序。

oi-wiki.org

语言（普及、提高）

普及

  1. 顺序结构

  2. 分支结构

  3. 循环结构

  4. 数组

  5. 字符串 （前置知识：数组）

  6. 函数

  7. 递归

  8. 结构体

  9. STL (string,vector,deque,set(multiset),map(multimap),priority_queue)

  10. 文件操作

提高

  1. STL (pair,queue,stack,list,bitset,tuple)

  2. 重载运算符

  3. 命名空间

  4. 类

  5. 引用

  6. 宏

  7. 头文件

  8. 指针

  9. 杂项（pb_ds,lambda表达式）

算法（普及、提高、省选）

普及

  1. 复杂度分析

  2. 模拟

  3. 搜索（详情见搜索部分）

  4. 高精度

  5. 排序（快速排序，归并排序，计数排序）

  6. 贪心、哈夫曼树（前置知识：排序）

  7. 二分（三分）

  8. 图论（详情见图论部分）

  9. DP（详情见动态规划部分）

  10. 前缀和、差分

  11. 离散化

  12. 双指针

  13. 倍增

提高

  1. 分治（前置知识：递归）

  2. 字符串（详情见字符串部分）

  3. 数学（详情见数学部分）

  4. 随机化（模拟退火）

  5. 构造

省选

  1. 计算几何（详情见计算几何部分）

  2. 杂项（二进制分组）

数据结构（普及、提高、省选）

普及

  1. 线性表（数组、栈、队列、双端队列）

  2. 链表（单向链表、双向链表、循环链表）

  3. 哈希表

  4. 堆

  5. 并查集 并查集学习笔记

  6. 单调栈、单调队列

  7. ST表（前置知识：倍增）

  8. 二叉搜索树

  9. trie（0-1trie）

提高

  1. 树状数组（权值树状数组） 树状数组学习笔记

  2. 线段树（动态开点线段树，权值线段树、扫描线） 线段树学习笔记

  3. 分块（数论分块、块状链表、根号分治） 分块学习笔记 根号分治学习笔记

  4. 平衡树（treap、FHQtreap、splay）

省选

  1. 可并堆（左偏树）

  2. 可持久化数据结构（可持久化线段树、可持久化并查集、可持久化trie、可持久化分块、可持久化可并堆）

  3. 高级线段树（主席树、李超线段树、吉老师线段树、zkw线段树）

  4. 高级平衡树（WBLT、SBT、AVL树、B树、B+树、替罪羊树、Leafy Tree、笛卡尔树、红黑树、左偏红黑树、跳表）

  5. 树套树

  6. KD-Tree （前置知识：替罪羊树）

  7. 动态树（LCT，前置知识：Splay）

  8. 离线算法（CDQ 分治、整体二分、莫队）

  9. 杂项（珂朵莉树、sqrt tree等）

搜索部分（普及、提高）

普及

  1. 朴素 dfs 搜索（回溯法）

  2. 朴素 bfs 搜索

  3. 搜索剪枝（记忆化搜索、最优性剪枝、可行性剪枝）

提高

  1. 双向搜索（双向dfs，双向bfs）

  2. A*

  3. 迭代加深搜索

  4. IDA* （前置知识：迭代加深搜索，A*）

动态规划部分（普及、提高、省选）

普及

  1. 基础DP、记忆化搜索（数字三角形、LIS、LCS）

  2. 背包（0-1背包、完全背包、多重背包、背包变种）

提高

  1. 区间DP

  2. 树形DP

  3. DAG上DP

  4. 状压 DP

  5. 数位 DP

  6. 计数 DP

  7. 概率 DP

  8. DP优化（单调队列/单调栈优化DP、转移优化DP、矩阵快速幂优化DP）

省选

  1. DP优化（斜率优化DP、四边形不等式优化DP、状态设计优化DP、wqs带权二分、分治优化DP）

  2. 动态 DP

  3. 插头 DP

字符串部分（普及、提高、省选）

普及

  1. KMP

  2. 字符串哈希

  3. trie（详情见数据结构部分）

提高

  1. 前缀函数

  2. manacher、回文树

  3. AC自动机

  4. 失配树

  5. 后缀自动机、后缀数组、后缀树

省选

  1. 子序列自动机

  2. Lyndon 分解

  3. 扩展KMP

  4. Boyer-Moore 算法

  5. Main-Lorentz 算法

数学部分（普及、提高、省选）

普及

  1. 进制

  2. 位运算

  3. 快速幂

  4. 埃氏筛

  5. 欧几里德算法、裴蜀定理

提高

  1. 线性筛

  2. 扩展欧几里德算法

  3. 欧拉定理、费马小定理、逆元

  4. 组合数学

  5. 拉格朗日插值

  6. 矩阵

  7. 康托展开

  8. 高斯消元

  9. 线性基

  10. 原根

  11. 离散对数（bsgs）

  12. 中国剩余定理

  13. 卢卡斯定理

  14. 扩展欧拉定理

  15. 基础博弈论

省选

  1. 扩展中国剩余定理

  2. 扩展卢卡斯定理

  3. 扩展bsgs

  4. FFT、NTT

  5. 多项式全家桶

  6. 剩余、二次剩余

  7. 莫比乌斯反演（二项式反演、欧拉反演、单位根反演、斯特林反演）

  8. 杜教筛（Powerful Number 筛、Min_25 筛、洲阁筛）

  9. 高级博弈论（SG函数）

  10. Miller_Rabin

图论部分（普及、提高、省选）

普及

  1. 邻接矩阵、邻接表、链式前向星

  2. 图上dfs、bfs（详情见搜索部分）

  3. 树的直径、树的重心、基环树、DAG

  4. 拓扑排序

  5. 洪水填充

提高

  1. 单源最短路（dijkstra、spfa）

  2. 多源最短路（floyd、johnson）

  3. 二分图最大匹配

  4. 最小生成树（kruskal、prim）

  5. 欧拉图、欧拉回路

  6. 倍增lca

  7. 差分约束

  8. tarjan（边双连通分量、点双连通分量、强连通分量）

省选

  1. 最大流、最小割

  2. 最小费用最大流

  3. 二分图最大权匹配

  4. kruskal重构树

  5. 树链剖分

  6. 同余最短路

  7. 一般图最大匹配

  8. 树上启发式合并

  9. 虚树

  10. 点分治、边分治

  11. 点分树、边分树

  12. 矩阵树

  13. 斯坦纳树

  14. 2-SAT

  15. Prufer 序列

  16. 一般图最大权匹配

计算几何部分（提高、省选）

提高

  1. 向量

  2. 多边形、点积、叉积

  3. 极角排序

  4. 二维凸包

  5. 旋转卡壳

省选

  1. 平面最近点对

  2. 半平面交

  3. 三角剖分

  4. 三维凸包