SUMMARY.md

目录

• 第一章·基础算法

  • 准备知识
  • 模拟
  • 暴力美学
  • 贪心
  • 构造
  • 二分法
    • 整体二分
  • 三分法
  • 高精度
    • 基本运算
    • 进阶
  • 排序
    • 线性划分
    • 逆序对

• 第二章·搜索

  • DFS
  • BFS
  • 记忆化搜索
  • 双向广搜
  • 启发式搜索
  • A*
  • IDA*
  • 迭代深搜
  • 回溯法
  • Dancing Links

• 第三章·动态规划

  • 一般动规与递推
  • 记忆化搜索
  • 背包DP
  • 区间DP
  • DAG上的dp
  • 树形DP
  • 状压DP
    • 斯坦纳树
  • 数位DP
  • 插头DP
  • 环形DP
  • 环 + 外向树上的动态规划
  • 优化及其它
    • 斜率优化
    • 四边形不等式
    • 二进制优化
    • 决策单调性
    • 滚动数组
    • 前缀和
    • 其他优化
  • 其它动规方法

• 第四章·树

  • 存储方式：存图or存父亲
  • 遍历：BFS和DFS
  • 无根树转有根树
  • 求直径和中心求直径和中心
  • 二叉树的遍历方法
  • 二叉查找树的基本操作
  • 虚树
  • 生成树
  • 矩阵树定理
  • MST
    • Kruskal
    • Prim
    • 堆优化Prim
  • 点分治
  • 树的重心
  • 树的直径
    • 树上倍增求LCA
    • Tarjan
    • 链剖法
  • 树同构
  • DFS序
  • 树链剖分
  • Prufer编码
  • 最近公共祖先(LCA)
  • 仙人掌

• 第五章·图论

  • 存储方式：邻接矩阵、前向星、链式前向星
  • 遍历：BFS和DFS
  • 拓扑排序
  • 动态树分治
  • 2-SAT
  • 欧拉图
  • 图的连通
    • 强连通分量
    • 双连通分量
    • 割点割边
  • 差分约束
  • 二分图判定
  • 二分图染色
  • 二分图匹配
  • 最短路 Floyd, SPFA, Dijkstra 堆或线段树优化Dijkstra 有向图最小环 无向图最小环 输出方案 k短路 偏离算法
  • 差分约束
  • 欧拉图
  • 网络流
    • 拆点
    • 最大流
    • 最小割
    • 费用流
      • zkw费用流
    • 上下界网络流
      • 二分

• 第六章·数学

  • 进制相关
  • 斐蜀定理
  • 找一个数的所有约数
  • 费马小定理（欧拉定理）
  • 判定素数
  • 素数测试
  • 快速幂
  • 中国剩余定理
  • 分段打表
  • 欧几里得算法、扩展欧几里得算法
  • 矩阵乘法
  • 行列式
  • 拟阵
  • 位运算
  • 乘法逆元
  • 拉格朗日乘数法
  • 阶 原根
  • BSGS
  • 筛法
  • 博弈论
  • 取模运算
  • 欧拉函数
  • 多项式黑科技
  • 卡特兰数
  • 排列组合
  • 康托展开
  • 概率与期望
  • 置换群
  • 高斯消元
  • xor模线性方程组
  • 容斥原理
  • 抽屉原理
  • 调和级数
  • 数值与积分
  • 莫比乌斯反演
  • 快速傅里叶变换
  • 快速数论变换
  • 线性规划
  • 数学其它

• 第七章·字符串

  • 一堆字符串函数
  • 哈希大法
  • 字典树(Trie)
  • 回文自动机
  • 回文树
  • 后缀数组(SA)
  • AC自动机
  • 后缀自动机(SAM)
  • 后缀树
  • Manacher
  • 最小表示法
  • 密码学

• 第八章·数据结构

  • STL
  • pb_ds
  • 基础数据结构
    • 堆
    • 链表
    • 分块
    • 哈希表
    • 单调栈
    • 单调队列
    • 并查集
    • 表达式求值
  • 中级数据结构
    • ST表
    • 块状链表
    • 块状数组
    • 树状数组
    • 线段树
    • zkw线段树
    • 可并堆
      • 配对堆
      • 左偏树
    • 平衡树
      • Treap
      • SBT
      • Splay
      • 替罪羊树
  • 高级数据结构
    • 树套树
      • 线段树套线段树
      • 线段树套平衡树
      • 平衡树套线段树
    • AVL树
    • 划分树
    • Euler Tour Tree
    • 仙人掌树
    • 替罪羊树(朝鲜树)
    • 主席树
    • K-Dtree
    • 可持久化数据结构
      • 可持久化线段树
      • 可持久化块状数组
      • 可持久化平衡树
      • 可持久化字典树
    • 动态树
      • Link Cut Tree
      • 树分块

• 第九章·计算几何

  • 二维计算几何基础
  • 三维计算几何基础
  • pick定理
  • 三角剖分
  • 梯形剖分
  • 凸包
  • 扫描线
  • 旋转卡壳
  • 半平面交
  • 其他黑科技

• 第十章·其他

  • 非传统题（提答大法）
  • cdq分治
  • 莫队算法
  • 树上莫队
  • 爬山算法
  • 分数规划
  • 模拟退火
  • 朱刘算法
  • 随机增量法
  • 弦图与区间图
  • 杂项
  • 随机化
  • 倍增算法
  • 离线处理
  • 各种距离

• 第十一章·算法之外的世界

• 第十二章·新征程