ACM基础知识及算法
| ACM 算法 | 难度 | ||||
| 数据结构 | 栈 | 栈 | 1 | ||
| 单调栈 | |||||
| 队列 | 一般队列 | 1 | |||
| 优先队列/单调队列 | 1 | ||||
| 循环队列 | 2 | ||||
| 双端队列 | 2 | ||||
| 链表 | 一般链表 | 1 | |||
| 循环链表 | 2 | ||||
| 双向链表 | 2 | ||||
| 块状链表 | 2 | ||||
| 十字链表 | 3 | ||||
| 邻接表/邻接矩阵 | 邻接表 | 1 | |||
| 邻接多重表 | 2 | ||||
| Hash表(哈希表) | Hash表 | ||||
| 字符串Hash | |||||
| 二叉树 | 一般二叉树 | 1 | |||
| 遍历二叉树 | 先序遍历二叉树 | 2 | |||
| 中序遍历二叉树 | 2 | ||||
| 后序遍历二叉树 | 2 | ||||
| Huffman树(赫夫曼树)(最优二叉树) | 1 | ||||
| Huffman编码(赫夫曼编码) | 1 | ||||
| 二叉查找树/二叉排序树/二叉搜索树 | Treap | 3 | |||
| 伸展树 | 3 | ||||
| 线索二叉树 | 4 | ||||
| 平衡二叉树 | 4 | ||||
| 堆 | 大/小根堆（优先队列） | 2 | |||
| 可并堆 | 3 | ||||
| 左偏堆 | 3 | ||||
| 线段树 | 一维线段树 | 2 | |||
| 延迟标记 | 3 | ||||
| 二维线段树 | 3 | ||||
| 扫描线 | 2 | ||||
| 线段树套平衡树 | 5 | ||||
| 主席树/可持久化线段树 | 6 | ||||
| 树状数组 | 一维树状数组 | 2 | |||
| N维树状数组 | 3 | ||||
| 逆序对问题 | 2 | ||||
| 字符串 | KMP算法 | 2 | |||
| 最小表示法 | 2 | ||||
| 字典树/Trie树 | 静态建树 | 2 | |||
| 动态建树 | 2 | ||||
| 可持久化Trie树 | 3 | ||||
| 后缀数组 | 5 | ||||
| 后缀树 | |||||
| 后缀自动机 | |||||
| Aho-Corasick自动机 | 6 | ||||
| 并查集 | 并查集 | 1 | |||
| 路径压缩 | 1 | ||||
| 边带权并查集 | 1 | ||||
| 分块 | 2 | ||||
| RMQ问题 | 朴素 | 1 | |||
| 线段树 | 2 | ||||
| ST表 | 3 | ||||
| RMQ标准算法 | 4 | ||||
| 离散化 | 2 | ||||
| 红黑树 | 5 | ||||
| 跳跃表 | 3 | ||||
| 图论 | 搜索 | 深度优先遍历/DFS | 深度优先遍历/DFS | 2 | |
| DFS序 | 1 | ||||
| 迭代加深DFS(ID-DFS) | 3 | ||||
| 双向DFS | 2 | ||||
| 广度优先遍历/BFS | 广度优先遍历/BFS | 2 | |||
| 双端队列BFS | 2 | ||||
| 优先队列BFS | 2 | ||||
| 多起点BFS | 2 | ||||
| 双重BFS | 2 | ||||
| 双向BFS | 2 | ||||
| 剪枝 | 3 | ||||
| 拓扑排序 | 2 | ||||
| 状态压缩 | 1 | ||||
| A*算法 | |||||
| IDA*算法 | |||||
| 记忆化搜索 | 3 | ||||
| 强连通分量 | 强连通分量 | Tarjan算法 | 3 | ||
| Korasaju算法 | 3 | ||||
| 双连通分量 | |||||
| 强连通分支及其缩点 | |||||
| 图的割边和割点 | |||||
| 2-SAT问题 | |||||
| 欧拉路问题 | 欧拉路径 | 2 | |||
| 欧拉回路 | 2 | ||||
| 哈密顿回路 | |||||
| 最小生成树 | Prim算法 | 2 | |||
| Kruskal算法(稀疏图) | 2 | ||||
| Sollin算法 | 3 | ||||
| 次小生成树 | 3 | ||||
| 最小有向生成树 | |||||
| 第k小生成树 | 3 | ||||
| 最优比例生成树 | |||||
| 最小树形图 | |||||
| 最小瓶颈生成树 | 最小瓶颈生成树 | ||||
| 每对结点间最小瓶颈路 | |||||
| 最小瓶颈路 | |||||
| 最小度限制生成树 | |||||
| 增量最小生成树 | |||||
| 平面点的欧几里德最小生成树 | |||||
| 平面点的曼哈顿最小生成树 | |||||
| 最小平衡生成树 | |||||
| 最短路径 | 单源最短路径 | 有向无环图的最短路径 | 拓扑排序 | 2 | |
| 非负权值加权图的最短路径 | Dijkstra算法 | 2 | |||
| Dijkstra算法(二叉堆优化) | 2 | ||||
| 含负权值加权图的最短路径 | Bellman-Ford算法 | 2 | |||
| SPFA算法 | 2 | ||||
| 全源最短最短路径 | Floyd算法 | 1 | |||
| Johnson算法 | 2 | ||||
| 次短路径 | |||||
| 第k短路径 | |||||
| 差分约束系统 | 3 | ||||
| 平面点对的最短路径(优化) | |||||
| 双标准限制最短路径 | |||||
| 环 | 环判定 | 2 | |||
| 负环判定 | Bellman-Ford算法 | 2 | |||
| SPFA算法 | 2 | ||||
| 网络流 | 最大流问题 | 增广路算法 | 增广路定理 | 1 | |
| Ford-Fulkerson算法 | 3 | ||||
| Ford-Fulkerson迭加算法 | 3 | ||||
| Edmond-Karp算法 | 3 | ||||
| Dinic算法 | 3 | ||||
| ISAP算法/最短增广路算法 | 3 | ||||
| 预流推进算法 | |||||
| 多源多汇问题 | |||||
| 无源无汇有容量下界网络的可行流 | |||||
| 有容量下界网络的s-t最大/最小流 | |||||
| 节点有限制的网络流 | |||||
| 最小割最大流定理 | |||||
| 最小费用最大流问题 | 容量不固定的s-t最小费用流 | ||||
| 含负费用的最小费用最大流 | |||||
| 费用与流量平方成正比的最小流 | |||||
| 二分图匹配 | 二分图判定 | 2 | |||
| 二分图最大匹配 | 匈牙利算法 | 2 | |||
| Konig定理 | 1 | ||||
| 二分图最小点覆盖 | 匈牙利算法 | 2 | |||
| 二分图最小边覆盖 | |||||
| 二分图最佳完美匹配 | Kuhn-Munkres算法 | ||||
| 二分图完全匹配 | Kuhn-Munkres算法 | ||||
| 二分图多重匹配 | |||||
| 二分图带权最大匹配 | Kuhn-Munkres算法 | ||||
| 二分图最大独立集 | |||||
| 最大闭合子图 | |||||
| 最大密度子图 | |||||
| 公平分配问题 | |||||
| 区间k覆盖问题 | |||||
| 有向无环图(DAG)的最小路径覆盖 | DAG的最小不相交路径覆盖 | 2 | |||
| DAG的最小可相交路径覆盖 | |||||
| 树的直径 | 树形DP | 3 | |||
| BFS | 2 | ||||
| 基环树 | |||||
| 最近公共祖先 | 向上标记法 | ||||
| 树上倍增 | 3 | ||||
| Tarjan 算法 | 2 | ||||
| LCA 转 RMQ | 3 | ||||
| 弦图 | |||||
| 稳定婚姻问题 | |||||
| 动态规划 | 四边形不等式理论 | ||||
| 不完全状态记录 | 青蛙过河问题 | ||||
| 区间DP | |||||
| 背包问题 | 0-1背包 | 2 | |||
| 完全背包 | 2 | ||||
| 分组背包 | |||||
| 多重背包 | |||||
| 判定性背包问题 | |||||
| 带附属关系的背包问题 | |||||
| + -1背包问题 | |||||
| 双背包求最优值 | |||||
| 构造三角形问题 | |||||
| 带上下界限制的背包问题(012背包) | |||||
| 线性的动态规划问题 | 积木游戏问题 | ||||
| 决斗（判定性问题） | |||||
| 圆的最大多边形问题 | |||||
| 统计单词个数问题 | |||||
| 棋盘分割 | |||||
| 日程安排问题 | |||||
| 最***近问题(求出两数之比最接近某数/两数之和等于某数等等) | |||||
| 方块消除游戏(某区间可以连续消去求最大效益) | |||||
| 资源分配问题 | |||||
| 数字三角形问题 | |||||
| 漂亮的打印 | |||||
| 邮局问题与构造答案 | |||||
| 最高积木问题 | |||||
| 两段连续和最大 | |||||
| 2次幂和问题 | |||||
| N个数的最大M段子段和 | |||||
| 交叉最大数问题 | |||||
| 判定性问题的DP(如判定整除、判定可达性等) | 模K问题的DP | ||||
| 特殊的模K问题，求最大(最小)模K的数 | |||||
| 变换数问题 | |||||
| 单调性优化的动态规划 | 1-SUM问题 | ||||
| 2-SUM问题 | |||||
| 序列划分问题(单调队列优化) | |||||
| 剖分问题(多边形剖分/石子合并/圆的剖分/乘积最大) | 凸多边形的三角剖分问题 | ||||
| 乘积最大问题 | |||||
| 多边形游戏(多边形边上是操作符,顶点有权值) | |||||
| 石子合并(N^3/N^2/NLogN各种优化) | |||||
| 贪心的动态规划 | 最优装载问题 | ||||
| 部分背包问题 | |||||
| 乘船问题 | |||||
| 贪心策略 | |||||
| 双机调度问题Johnson算法 | |||||
| 区间DP | |||||
| 数位DP | |||||
| 状态DP | 牛仔射击问题(博弈类) | ||||
| 哈密顿路径的状态dp | |||||
| 两支点天平平衡问题 | |||||
| 一个有向图的最接近二部图 | |||||
| 树型DP | 完美服务器问题(每个节点有3种状态) | ||||
| 小胖守皇宫问题 | |||||
| 网络收费问题 | |||||
| 树中漫游问题 | |||||
| 树上的博弈 | |||||
| 树的最大独立集问题 | |||||
| 树的最大平衡值问题 | |||||
| 构造树的最小环 | |||||
| 数学 | 数论 | 积性函数 | 1 | ||
| 佩尔方程 | 3 | ||||
| 同余 | 同余定理 | 1 | |||
| 费马小定理 | 1 | ||||
| 欧拉定理 | 1 | ||||
| 欧拉定里推论 | 1 | ||||
| 扩展欧几里得算法 | 1 | ||||
| 中国剩余定理 | 1 | ||||
| 乘法逆元 | 1 | ||||
| 素数 | 欧几里得定理 | 1 | |||
| 朴素法 | 1 | ||||
| 筛选法 | Eratosthenes筛选法 | 2 | |||
| 线性筛 | 2 | ||||
| 米勒测试法 | 3 | ||||
| 约数/因数/因子 | 算术基本定理 | 1 | |||
| 算术基本定理的推论 | 1 | ||||
| 因数分解 | 试除法 | 1 | |||
| 倍数法 | 1 | ||||
| 质因数分解 | 试除法 | 1 | |||
| 最大公约数/最大公因数 | 欧几里得算法/辗转相除法 | 1 | |||
| 更相减损术 | 1 | ||||
| 最小公倍数 | 1 | ||||
| 欧拉函数 | Eratosthenes筛选法 | 2 | |||
| 线性筛 | 2 | ||||
| 连分数逼近 | |||||
| 循环群生成元 | |||||
| 进制位 | 1 | ||||
| 矩阵 | 矩阵乘法 | 1 | |||
| 矩阵快速幂 | 1 | ||||
| 矩阵转置 | 1 | ||||
| 组合数学 | 排列组合 | 排列数 | 1 | ||
| 组合数 | 组合数求法 | 1 | |||
| 组合数性质 | 1 | ||||
| 杨辉三角 | 1 | ||||
| 二项式定理 | 1 | ||||
| 加法原理 | 1 | ||||
| 乘法原理 | 1 | ||||
| 容斥原理 | 1 | ||||
| 递推关系和生成函数 | |||||
| Lucas定理 | |||||
| Polya计数法 | Polya计数公式 | ||||
| Burnside定理 | |||||
| N皇后构造解 | 2 | ||||
| 幻方的构造 | |||||
| Catalan数列 | |||||
| Stirling数列 | |||||
| 斐波拉契数 | 1 | ||||
| 调和数 | |||||
| 连分数 | |||||
| MoBius | MoBius函数 | ||||
| MoBius反演 | 5 | ||||
| 偏序关系理论 | |||||
| 计算几何 | 基本公式 | 叉乘 | 1 | ||
| 点乘 | 1 | ||||
| 常见形状的面积、周长、体积公式 | 1 | ||||
| 坐标离散化 | 2 | ||||
| 线段 | 判断两线段（一直线、一线段）是否相交 | 1 | |||
| 求两线段的交点 | 1 | ||||
| 多边形 | 判定凸多边形,顶点按顺时针或逆时针给出,(不)允许相邻边共线 | ||||
| 判点在凸多边形内或多边形边上,顶点按顺时针或逆时针给出 | |||||
| 判点在凸多边形内,顶点按顺时针或逆时针给出,在多边形边上返回0 | |||||
| 判点在任意多边形内,顶点按顺时针或逆时针给出 | |||||
| 判线段在任意多边形内,顶点按顺时针或逆时针给出,与边界相交返回1 | |||||
| 多边形重心 | |||||
| 多边形切割(半平面交) | |||||
| 扫描线算法 | |||||
| 多边形的内核 | |||||
| 三角形 | 内心 | 1 | |||
| 外心 | 1 | ||||
| 重心 | 1 | ||||
| 垂心 | 1 | ||||
| 费马点 | |||||
| 圆 | 判直线和圆相交,包括相切 | 1 | |||
| 判线段和圆相交,包括端点和相切 | |||||
| 判圆和圆相交,包括相切 | |||||
| 计算圆上到点p最近点,如p与圆心重合,返回p本身 | |||||
| 计算直线与圆的交点,保证直线与圆有交点 | |||||
| 计算线段与圆的交点可用这个函数后判点是否在线段上 | |||||
| 计算圆与圆的交点,保证圆与圆有交点,圆心不重合 | |||||
| 计算两圆的内外公切线 | |||||
| 计算线段到圆的切点 | |||||
| 点集最小圆覆盖 | |||||
| 球 | |||||
| 可视图的建立 | |||||
| 对踵点 | |||||
| 经典问题 | 平面凸包 | ||||
| 三维凸包 | |||||
| Delaunay剖分/Voronoi图 | |||||
| 计算方法 | 二分法 | 二分法求解单调函数相关知识 | 1 | ||
| 用矩阵加速的计算 | 1 | ||||
| 迭代法 | |||||
| 三分法 | 一般三分法 | ||||
| 三分法求解单峰(单谷)的极值 | |||||
| 快速幂 | 数学快速幂 | 1 | |||
| 矩阵快速幂 | 2 | ||||
| 解线性方程组 | LUP分解 | ||||
| 高斯消元 | |||||
| 解模线性方程组 | |||||
| 定积分计算 | |||||
| 多项式求根 | |||||
| 周期性方程 | |||||
| 线性规划 | |||||
| 快速傅立叶变换 | |||||
| 随机算法 | 1 | ||||
| 0/1分数规划 | |||||
| 迭代逼近 | |||||
| 矩阵法 | |||||
| 概率论 | 全概率公式 | 1 | |||
| 数学期望 | 1 | ||||
| 博弈论 | SG函数 | 3 | |||
| 极大极小过程 | 3 | ||||
| Nim问题 | 2 | ||||
阿里巴巴公司福利 613人发布
，可以适当对关键信息加粗一点，比如关键技术、性能指标之类的。