🎬视频 | 📖文章


关于刷题

NP 问题

链表

队列

哈希表

堆/优先队列

双端队列 (Deque)

可并堆

左偏堆

二叉查找树

Treap

伸展树

并查集

集合计数问题

二分图的识别

平衡二叉树

二叉排序树

线段树

一维线段树

二维线段树

树状数组

一维树状数组

N 维树状数组

字典树

后缀数组,后缀树

块状链表

哈夫曼树

桶,跳跃表

Trie 树(静态建树、动态建树)

AC 自动机

LCA 和 RMQ 问题

KMP 算法

图论 基本图算法图

广度优先遍历

深度优先遍历

拓扑排序

割边割点

强连通分量

Tarjan 算法

双连通分量

强连通分支及其缩点

图的割边和割点

最小割模型、网络流规约

2SAT 问题

欧拉回路

哈密顿回路

最小生成树

Prim 算法

Kruskal 算法(稀疏图)

Sollin 算法

次小生成树

第 k 小生成树

最优比例生成树

最小树形图

最小度限制生成树

平面点的欧几里德最小生成树

平面点的曼哈顿最小生成树

最小平衡生成树

最短路径

有向无环图的最短路径>拓扑排序

非负权值加权图的最短路径>Dijkstra 算法(可使用二叉堆优化)

含负权值加权图的最短路径>Bellmanford 算法

含负权值加权图的最短路径>Spfa 算法

(稠密带负权图中 SPFA 的效率并不如 BellmanFord 高)

全源最短路弗洛伊德算法 Floyd

全源最短路 Johnson 算法

次短路径

第 k 短路径

差分约束系统

平面点对的最短路径(优化)

双标准限制最短路径

最大流

增广路>FordFulkerson 算法

预推流

Dinic 算法

有上下界限制的最大流

节点有限制的网络流

无向图最小割>StoerWagner 算法

有向图和无向图的边不交路径

FordFulkerson 迭加算法

含负费用的最小费用最大流

匹配

Hungary 算法

最小点覆盖

最小路径覆盖

最大独立集问题

二分图最优完备匹配 KuhnMunkras 算法

不带权二分匹配:匈牙利算法

带权二分匹配:KM 算法

一般图的最大基数匹配

一般图的赋权匹配问题

拓扑排序

弦图

稳定婚姻问题

搜索 广搜的状态优化

利用 M 进制数存储状态

转化为串用 hash 表判重

按位压缩存储状态

双向广搜

A *算法

深搜的优化

位运算

剪枝

函数参数尽可能少

层数不易过大

双向搜索或者是轮换搜索

IDA *算法

记忆化搜索

动态规划 四边形不等式理论

不完全状态记录

青蛙过河问题

利用区间 dp

背包类问题

01 背包,经典问题

无限背包,经典问题

判定性背包问题

带附属关系的背包问题

+1 背包问题

双背包求最优值

构造三角形问题

带上下界限制的背包问题 (012 背包)

线性的动态规划问题

积木游戏问题

决斗(判定性问题)

圆的最大多边形问题

统计单词个数问题

棋盘分割

日程安排问题

最小逼近问题(求出两数之比最接近某数/两数之和等于某数等等)

方块消除游戏(某区间可以连续消去求最大效益)

资源分配问题

数字三角形问题

漂亮的打印

邮局问题与构造答案

最高积木问题

两段连续和最大

2 次幂和问题

N 个数的最大 M 段子段和

交叉最大数问题

判定性问题的 dp(如判定整除、判定可达性等)

模 K 问题的 dp

特殊的模 K 问题,求最大(最小)模 K 的数

变换数问题

单调性优化的动态规划

1SUM 问题

2SUM 问题

序列划分问题(单调队列优化)

剖分问题(多边形剖分/石子合并/圆的剖分/乘积最大)

凸多边形的三角剖分问题

乘积最大问题

多边形游戏(多边形边上是操作符,顶点有权值)

石子合并 (N^3/N^2/NLogN 各种优化)

贪心的动态规划

最优装载问题

部分背包问题

乘船问题

贪心策略

双机调度问题 Johnson 算法

状态 dp

牛仔射击问题(博弈类)

哈密顿路径的状态 dp

两支点天平平衡问题

一个有向图的最接近二部图

树型 dp

完美服务器问题(每个节点有 3 种状态)

小胖守皇宫问题

网络收费问题

树中漫游问题

树上的博弈

树的最大独立集问题

树的最大平衡值问题

构造树的最小环

数学 数论 中国剩余定理

欧拉函数

欧几里得定理

欧几里德辗转相除法求 GCD(最大公约数)

扩展欧几里得

大数分解与素数判定

佩尔方程

同余定理(大数求余)

素数测试

一千万以内:筛选法

一千万以外:米勒测试法

连分数逼近

因式分解

循环群生成元

素数与整除问题

进制位

同余模运算

组合数学

排列组合

容斥原理

递推关系和生成函数

Polya 计数法

Polya 计数公式

Burnside 定理

N 皇后构造解

幻方的构造

满足一定条件的 hamilton 圈的构造

Catalan 数

Stirling 数

斐波拉契数

调和数

连分数

MoBius 反演

偏序关系理论

加法原理和乘法原理

计算几何

基本公式

叉乘

点乘

常见形状的面积、周长、体积公式

坐标离散化

线段

判断两线段(一直线、一线段)是否相交

求两线段的交点

多边形

判定凸多边形,顶点按顺时针或逆时针给出,(不)允许相邻边共线

判点在凸多边形内或多边形边上,顶点按顺时针或逆时针给出

判点在凸多边形内,顶点按顺时针或逆时针给出,在多边形边上返回 0

判点在任意多边形内,顶点按顺时针或逆时针给出

判线段在任意多边形内,顶点按顺时针或逆时针给出,与边界相交返回 1

多边形重心

多边形切割(半平面交)

扫描线算法

多边形的内核

三角形

内心

外心

重心

垂心

费马点

判直线和圆相交,包括相切

判线段和圆相交,包括端点和相切

判圆和圆相交,包括相切

计算圆上到点 p 最近点,如 p 与圆心重合,返回 p 本身

计算直线与圆的交点,保证直线与圆有交点

计算线段与圆的交点可用这个函数后判点是否在线段上

计算圆与圆的交点,保证圆与圆有交点,圆心不重合

计算两圆的内外公切线

计算线段到圆的切点

点集最小圆覆盖

可视图的建立

对踵点

经典问题

平面凸包

三维凸包

Delaunay 剖分/Voronoi 图

计算方法

二分法

二分法求解单调函数相关知识

用矩阵加速的计算

迭代法

三分法

解线性方程组

LUP 分解

高斯消元

解模线性方程组

定积分计算

多项式求根

周期性方程

线性规划

快速傅立叶变换

随机算法

0/1 分数规划

三分法求解单峰(单谷)的极值

迭代逼近

矩阵法

博弈论

极大极小过程

Nim 问题