算法标签

数据结构

• 数组 Array
• 栈 Stack
• 队列 Queue
• 优先队列（Priority Queue, heap）
• 链表 LinkedList(single/double)
• Tree/ Binary Tree
• Binary Search Tree
• HashTable
• Disjoint Set
• Trie
• BloomFliter
• LRU Cache

算法分类

• 线性结构

  • 莫队 (Mo’s Algorithm)
  • 前缀和
  • 基本数组
  • 向量
  • 链接表（linked list）
  • 栈(stack)
  • 队列
  • 块状链表,块状数组,分块
  • st表, 稀疏表
  • 差分

• 树形结构

  • 线段树
    • 二维线段树
    • 矩形树
    • zkw线段树
    • 主席树
  • 点分治
  • 平衡树
    • AVL
    • Treap
    • SBT
    • Splay
    • 静态排序树
    • 替罪羊树
  • 二叉堆（binary heap）
    • 左偏树
    • 斜堆
    • 二项堆
  • 树状数组
  • cdp分治
  • 树上距离
    • 节点到根的距离
    • 最近公共祖先,LCA
    • 节点间距离
    • 树的直径
  • 动态树
    • 树链部分,树剖
    • Link-Cut Tree,LCT
  • 树的应用
    • 并查集 (Disjoint set)
    • 树的遍历
    • 哈夫曼树
    • RMQ
    • 树套树
    • 可持久化
    • 虚树
  • 整体二分
  • 环套树
  • K-D Tree

• 字符串

  • 后缀自动机,SAM
  • 字典树, Trie树
  • AC自动机
  • KMP
  • 后缀数组,SA
  • 后缀树
  • 有限状态自动机
  • 哈夫曼, Huffman
  • 简单密码学
  • 回文自动机PAM
  • Manacher算法

• 排序

  • 冒泡排序
  • 选择排序
  • 桶排
  • 插入排序
  • 归并
  • 快速排序,快排
  • 堆排序
  • 希尔排序
  • 外部排序

• 查找

  • 二分答案
  • 顺序查找
  • 二分查找

• 二分图

  • 最大匹配
    • 匈牙利算法
    • 一般图的最大匹配
    • Konig定理
  • 带权二分图匹配
  • 稳定婚姻系统

• 搜索

  • 广度优先搜索, BFS
  • 深度优先搜索, DFS
  • 剪枝
  • 记忆化搜索
  • 启发式搜索
    • 启发式迭代加深, IDA*
    • Dancing Links
    • 爬山法
    • 模拟退火
    • 遗传
    • A*算法
  • 迭代加深
  • 随机调整

• 网络流

  • 最大流
    • Dinic
    • Sap
    • 有上下界的最大流
  • 最小割
    • 闭合图
    • 最小点权覆盖集
    • 最大点权覆盖集
    • 分数规划
    • 最大密度子图
  • 费用流
    • 最短路增广费用流
    • zkw费用流
    • 最小费用可行流

• 基础算法

  • 模拟
  • 贪心(Greedy)
  • 递推
  • 递归（backtrace）
  • 枚举, 暴力
  • 分治（Divide and conquer）

• 动态规划(Dynamic Programming)

  • 动态规划初步
  • 背包
  • 环形动规,环形dp
  • 数位动规,数位dp
  • 多维状态
  • 区间动归,区间dp
  • 字母树
  • 动态规划优化
    • 单调队列
    • 降低维度,降维
    • 优先队列(Priority Queue)
    • 矩阵加速,矩阵优化
    • 斜率优化
    • 状态压缩,状压
    • 凸完全单调性,凸单调
    • 四边形不等式
  • 树形动归
  • 插头dp

• 其它技巧

  • 暴力数据结构
  • 高精
  • 博弈论
    • Nim游戏
    • 博弈树
    • Shannon开关游戏
  • 倍增
  • 离散化
  • 哈希,Hash
    • ELFhash
    • SDBM
    • BKDR
  • 随机贪心, 随机化
  • 快速傅立叶变换,DFT,FFT
  • 位运算,按位
  • 骗分
  • NP问题
  • 构造
  • 快速数论变换NTT
  • 快速沃尔什变换FWT

• 数论,数学

  • 整数研究
    • 素数判断, 质数, 筛法
    • 最大公约数, gcd
    • 扩展欧几里得, 扩欧
    • 不定方程
    • 进制
    • 同余,中国剩余定理
    • 莫比乌斯反演
    • 逆元
  • 集合论
  • 群论
    • 置换
    • Polya原理
  • 组合数学
    • 排列组合
    • 二项式定理
    • 康托展开
    • 袋与球问题
    • 鸽笼
    • 熔斥
    • 斐波那契,Fibonacci
    • 卡特兰,Catalan
    • Stirling
    • 生成函数
    • 卢卡斯,Lucas
  • 线性规划
  • 概率论,统计
    • 众数
    • 简单概率
    • 条件概率
    • Bayes
    • 期望
  • 线性代数
    • 矩阵运算
    • 矩阵乘法
    • 线性递推,递推式
    • 高斯消元
    • 异或方程组
    • 线基性
  • 微积分初步
    • 极限
    • 导数
    • 积分
    • 定积分
    • 立体解析几何
    • 级数
  • 图论

    • 图遍历

    • 拓扑排序

      • AOV
      • AOE

    • 最短路

      • Floyd
      • Dijkstra
      • Bellman-Ford
      • SPFA
      • 差分约束
      • K短路

    • 生成树

      • Prim
      • Kruskal
      • 生成树的另类算法
      • 次小生成树
      • 特殊生成树

    • 圈和块

      • 最小环
      • 负权环
      • 连通块
      • 2-SAT
      • 欧拉公式
      • 四色定理
      • 欧拉环路

    • 强连通分量,缩点

      • Tarjan
      • 割点

    • 仙人掌

  • 计算几何
    • 凸包
    • 叉积
    • 线段相交
    • 点积
    • 半平面相交,半平面交
    • 最近点对
    • 凸多边形的交
    • 离散化扫描
    • 旋转卡壳