算法地图

点一个框看它解决什么、什么时候想到它;选一条路线,一步一步看先学什么。蓝字可以直接点开对应的笔记。

算法地图:面试要写的、快速过的、赛场主攻的 绿框 = 面试常考,要能写对写快;灰框 = 快速过,知道它解决什么、什么时候想到它;蓝框 = 主攻的主线,按箭头从上往下学;黄框 = 主攻的支线,主线学到箭头那一格时挂上去。 蓝字 = 站内的笔记: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 节 图跟着学习进度更新:讲过的框补上对应的文章。