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 |