oi知识表+NOIP提高组算法及算法思想总结
算法及算法思想总结
│ By lib
│
├暴力
├模拟
├递归及递推:数位统计类
├构造
▼├排序算法
│ ├冒泡排序
│ ├选择排序
│ ├计数排序
│ ├基数排序
│ ├插入排序
│ ├归并排序
│ ├快速排序
│ ├堆排序
│ └二叉排序树
│
▼├分治
│ ├快速幂
│ ├单调区间求解（二分答案再验证）
│ ├二分后，先各自计算，然后再根据某种策略合并答案
│ ├逆序对统计
│
▼├贪心
│ ├不相交区间、区间选点问题、区间覆盖问题
│ ├流水作业调度问题、带期限和罚款的单位时间任务调度问题
│ ├其它最优化问题
│
▼├搜索
│ ▼├剪枝
│ │ ├最优化剪枝（可先贪心一个次优解）
│ │ ├可行性
│ │
│ ▼├深度优先搜索（dfs）：网格数据
│ │ ▼├实现方式
│ │ │ ├递归实现（栈<=10000-20000层）
│ │ │ └非递归实现（手动栈）
│ │ │
│ │ ├贪心：预处理路径
│ │ ├回溯法
│ │
│ ▼├广度优先搜索（bfs）：线性数据
│ │ ├队列（先进先出）
│ │ └双向广度优先搜索（从源汇点同时搜）
│ │
│ ├FloodFill(种子填充法)
│ ├搜索顺序
│ ├搜索与其他算法结合
│ ├二分检索
│
▼├规划
│ ▼├动态规划（DP）
│ │ ▼├优化
│ │ │ ├数据结构
│ │ │ ├单调队列
│ │ │
│ │ ├背包（背包九讲）
│ │ ├区间型动态规划
│ │ ├子序列型动态规划
│ │ ├环形动态规划
│ │ ├树形动态规划
│ │ ├字符串型动态规划
│ │ └记忆化搜索
│ │
│
▼├图论
│ ▼├基本概念
│ │ ├简单路径：一条路径上的结点除起点x1和终点xk可以相同外，其它结点均不相同（x1=xk的简单路径称为回路/环）
│ │ ├阶（图结点个数），度=入度+出度（奇点和偶点）
│ │ ├带权图称为网
│ │ ├子图：假设有两个图G＝（V，E）和G’＝（V’,E’），如果V’∈ V且E’∈ E，则称G’为G的子图。
│ │ ├连通分量：极大连通子图
│ │ ├混合图（有向+无向）：“（）”无向边；“<>”有向边
│ │ ├邻接边，邻接点
│ │ ├简单图（无环），完全图（点与点之间均有边）
│ │ ├迹（无重复边），通路/轨(无重复点)，圈（起点和终点重合的轨）
│ │ ├DAG（有向无环图）
│ │
│ ├拓扑序（关键路径）：AOV网
│ ▼├最短路(三角不等式)
│ │ ▼├算法
│ │ │ ▼├单源最短路（SSSP）
│ │ │ │ ├Dijkstra（无法处理负环）（堆优化） O(n^2) {O(E lg V)}
│ │ │ │ ▼└Spfa（堆优化） O(kE)
│ │ │ │ ├Bellman-Ford的变形
│ │ │ │ └松弛操作
│ │ │ │
│ │ │ ▼└所有顶点对间最短路（APSP）
│ │ │ ├Floyd:在最外层循环做了k-1次之后，dist[i][j]则代表了i到j的路径中，所有结点编号都小于k的最短路径。
│ │ │
│ │ ├次短路∈前K短路
│ │
│ ▼├（最小）生成树（MST）
│ │ ▼├无向图最小生成树
│ │ │ ├Prim（堆优化） O(V^2+E) {O((V+E) lg V)}
│ │ │ └Kruskal（并查集优化） O(E lg E+V*E) {O(E lg E+Eα(V))}
│ │
│ │
│ ▼├网络流
│ │ ▼├算法
│ │ │ ▼├增广路算法
│ │ │ │ ▼├Ford-Fulkerson方法
│ │ │ │ │ ├Edmonds-Karp算法（bfs） O(V*E^2)
│ │ │ │ │ └dfs(效率低下）
│ │ │ │ │
│ │ │ │ ▼└最短增广路算法(分层图） O(V^2*E)
│ │ │ │ ├最短路径增值(MPLA)
│ │ │ │ ├Sap（Gap优化） 推荐
│ │ │ │ └Dinic
│ │ │ │
│ │ │ ▼├预流推进算法：
│ │ │ │ ├push-relabel算法 O(V^2*E)
│ │ │ │ ├relabel-to-front算法 O(V^3)
│ │ │ │ └Hlpp（最高标号预流推进算法）（效率高但代码长） O(V^2*sqrt(E))
│ │ │ │
│ │ │ └压入与重标记算法
│ │
│ ▼├路径
│ │ ├哈密顿回路：点
│ │ └欧拉回路：边（欧拉图：含欧拉回路）
│ │
│ │
│ ├dfs序，bfs序的使用
│
▼├离散结构
│ ▼├串、树
│ │ ├LCA与RMQ相互转化
│ │
│ ▼├矩阵
│ │ ├部分和（前缀和）
│ │ ├离散化
│ │
│
│
▼├数据结构
│ ├顺序表：数组
│ ▼├链表
│ │ ▼├单链表
│ │ ├双链表
│ │ ├循环链表
│ │
│ ├串（见离散结构）
│ ▼├集合
│ │ ▼├哈希表（散列表）
│ │ │ ▼├哈希函数
│ │ │ │ ├直接定址法
│ │ │ │ ├数字分析法
│ │ │ │ ├平方取中法
│ │ │ │ └折叠法
│ │ │ │
│ │ │ ├分段Hash
│ │ │ ▼└处理冲突
│ │ │ ├拉链法
│ │ │ ├多哈希法
│ │ │ ├开放地址法
│ │ │ └建域法
│ │ │
│ │ └并查集（路径压缩）
│ │
│ ▼├堆
│ │ ▼├二叉堆
│ │ │ └最大-最小堆
│ │ │
│ │
│ ├栈：手写栈
│ ▼├队列
│ │ ├链队列
│ │ ├循环队列
│ │ ▼└优先队列（带权值的队列）
│ │
│ ▼├树
│ │ ▼├线段树
│ │ │ └Lazy标记
│ │ │
│ │ ├树状数组（在线支持修改的前缀和）
│ │
│ ▼└图的表示
│ ├邻接矩阵
│ ├邻接表
│ └链式前向星
│
▼├数学
│ ├高精度（*高精除高精不要求*）
│ ├排列组合:Stirling数
│ ├二项式定理
│ ├康托展开:一个全排列到一个整数的双射，经常用来做可以用全排列表示状态的搜索的哈希函数
│ ▼├组合计数
│ │ ▼├递推关系与生成函数（母函数）
│ │ │ ├普通型母函数
│ │ │ └指数型母函数：Fibonacci数列，Catalan数列
│ │ │
│ │ ├抽屉原理
│ │ ├容斥原理
│ │
│ ├素数及素数判定
│ ├乘法逆元（可用欧拉定理，扩展欧几里德定理求解）：若ax≡1(mod f)，则称a关于模f的乘法逆元为x。
│ ▼├最大公约数
│ │ ├欧几里德算法（辗转相除法）：gcd(a,b)=gcd(b,a mod b)
│ │ └扩展欧几里德定理：存在唯一的整数 x，y 使得gcd（a，b）=ax+by
│ │
│
做题流程：1、建模（脱马甲）；2、破冰（有序、单调、逆向，发散）（状态与状态间联系）；3、设计数据结构保存相关信息，并在数据结构的基础上设计算法解决问题（要证明）；4、编写代码、调试程序。
每题任务：1、你尝试了几个解题方向和思路？2、正解怎么做的？3、怎样从题目到正解？4、你自己目标分多少？有没有达到？
理科生做题，多问自己为什么要这么做，下次遇到类似的问题怎么办？