算法地图
点一个框看它解决什么、什么时候想到它;选一条路线,一步一步看先学什么。蓝字可以直接点开对应的笔记。
English
算法
静态图
面试刷题路线
数论主线
组合计数主线
线性代数主线
赛场上怎么想到
看原尺寸
算法地图:面试要写的、快速过的、赛场主攻的
绿框 = 面试常考,要能写对写快;灰框 = 快速过,知道它解决什么、什么时候想到它;蓝框 = 主攻的主线,按箭头从上往下学;黄框 = 主攻的支线,主线学到箭头那一格时挂上去。
蓝字 = 站内的笔记:A1、B1……是这条线每轮的讲义;NT = Number Theory,C = Combinatorics,M = Matrix 是以前的英文笔记。跨列的先修关系写在点开后的说明里。
面试常考:要能写对、写快(HFT / 互联网面试和比赛签到题)
快速过:知道它解决什么、复杂度多少、什么时候想到它
赛场主攻:数学。要能推式子,赛场上说得出思路
数论
组合计数
线性代数(矩阵)
复杂度 · STL
看数据范围定复杂度
容器的复杂度要背熟
A1 第 1 节
二分
有序里找边界
答案单调就二分答案
A1 第 2 节
双指针 · 滑窗
两端都只往右走
总共 O(n)
A1 第 3 节
前缀和 · 差分
区间和 O(1)
区间加 O(1)
A1 第 4 节
栈 · 单调栈
下一个更大的数
单调队列:滑窗最值
A2(上)第 2 节
堆 · 哈希表
Top-K;动态取最值
查有没有、数几次
A2(上)第 3 节
排序 · 贪心
排序后取局部最优
交换论证说明对
位运算
lowbit;枚举子集
异或的性质
搜索 · 回溯
BFS:最少步数
DFS:枚举 + 剪枝
树
遍历 · 直径 · LCA
递归返回值的设计
图 · 最短路
Dijkstra · 拓扑排序
有负权:Bellman-Ford
并查集
动态加边问连通
Kruskal 最小生成树
DP:线性 · 背包
先定状态的含义
再写转移和边界
DP:区间 · 树 · 状压
按长度、子树、集合
状压:n 到 20 左右
字符串
KMP · 哈希 · Trie
01-Trie:最大异或
设计题
LRU · 订单簿 · 限流
考数据结构选型
树状数组 · 线段树
区间查、区间改
都是 O(log n)
平衡树 · pb_ds
动态第 k 小、排名
比赛优先用库
树上进阶
树剖 · 换根 · 点分治
路径改查、全根统计
连通性
Tarjan · 缩点
2-SAT:二选一约束
网络流 · 二分图
最大流 · 匹配 · 费用流
难在建图
字符串进阶
AC 自动机 · SAM
Manacher:回文
计算几何
叉积 · 凸包
半平面交 · 精度
博弈
Nim · SG 函数
先打表找规律
分治
CDQ · 整体二分
离线降一维
离线技巧
莫队 · 扫描线
询问能重排就离线
李超树 · 笛卡尔树
斜率优化 DP
区间最值变成树
对拍 · 随机化
暴力对拍查错
随机哈希防卡
快速幂 · gcd · exgcd
所有模运算的起点
NT #1 GCD · CRT
逆元 · CRT · 欧拉定理
模意义除法;合并同余
NT #1 GCD · CRT
筛法
线性筛顺带筛积性函数
NT #3 sieve → Möbius
积性函数 · 狄利克雷卷积
φ、μ、d、σ 之间的关系
NT #2 multiplicative
莫比乌斯反演 · 数论分块
∑ gcd 类式子的标准路线
NT #2-ex Möbius
NT #1.1 floor blocks
杜教筛 · min_25
n 到 1e10 的前缀和
NT #4 Min_25 · Du
原根 · BSGS
离散对数;NTT 的模数
C #2.2 roots · NTT
Miller-Rabin · rho
1e18 级的判素和分解
NT #4 Miller-Rabin · rho
二次剩余 · Lucas
模 p 开方;大组合数取模
NT #4 Miller-Rabin · rho
常用结论
勒让德公式;约数个数上界
NT #0 common formulae
排列组合 · 组合数取模
预处理阶乘和逆阶乘
C #1.1 binomials
C #0 formulae
容斥 · 错排 · 不定方程
“至少”和“恰好”互相换
C #1.2 inclusion-exclusion
二项式反演 · min-max 反演
恰好 k 个 ↔ 至少 k 个
生成函数
OGF 管组合;EGF 管排列
C #3.1 OGF
FFT · NTT
O(n log n) 的卷积
C #2.1 FFT
C #2.2 roots · NTT
多项式全家桶
求逆 · ln · exp · 分治 NTT
C #3.2 power series
球盒 · 斯特林 · 卡特兰
经典分配模型
Polya · Burnside
旋转、翻转下的不同方案
概率 · 期望 DP
期望的线性性;倒推
FWT · 子集卷积 · SOS
按位与 / 或 / 异或的卷积
矩阵乘法 · 快速幂
O(k³ log n) 算线性递推
M #1 fast power · Kitamasa
DP 半环
(min, +) 矩阵:恰好走 k 步
M #1 fast power · Kitamasa
高斯消元
实数 · 模 p · 异或方程组
M #2 Gaussian elimination
行列式
消成上三角;任意模数辗转相除
矩阵树定理 · LGV
生成树计数;不相交路径
BM · 特征多项式
从前几项求递推;Kitamasa
M #1 fast power · Kitamasa
矩阵题型
线段树的节点存矩阵
M #4 problems
线性基
最大异或;第 k 小异或
M #3 linear basis
L2 第 1 节
图跟着学习进度更新:讲过的框补上对应的文章。