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、你自己目标分多少？有没有达到？
理科生做题，多问自己为什么要这么做，下次遇到类似的问题怎么办？