knowledge_point

一、基础算法

1. 模拟

2. 递归与搜索

  • 深度优先搜索
  • 广度优先搜索
  • 启发式搜索
  • 迭代加深搜索
  • Min-Max搜索
  • Alpha-beta剪枝
  • 记忆化搜索
  • Meet_In_the_middle

3. 排序算法

  • 插入排序
  • 归并排序
  • 快速排序
  • 桶排序
  • 用数据结构排序

4. 贪心算法(fyh hxm wxg)

  • Huffman编码及Huffman树
  • K叉Huffman树
  • 区间覆盖问题及拓展
  • 思维性贪心
  • 拟阵

5. 差分思想


二、图论

1. 图的存储

  • 邻接表(链式前向星)
  • 邻接矩阵

2. 图的路径问题(fyh hxm)

[kuangbin]最短路练习

  • Floyd算法
  • BellMan-Ford算法及其优化
  • Dijkstra算法
  • K短路问题
  • 差分约束系统

3. 图的连通性(fyh hxm)

[kuangbin带你飞]专题九 连通图

[kuangbin]图的割点、桥与双连通分支

  • Prim算法

[kuangbin带你飞]专题八 生成树

  • Tarjan算法
    • 割点和桥
  • 强连通分量和双联通分量

4. 回路问题(fyh hxm)

  • Euler回路
  • Hamiltonian回路

5. 平面图与对偶图(fyh)

6. 无向图的三角形枚举

7. Graph Realization Problem

  • Graph Realization Problem
  • Digraph Realization Problem

8. 图的匹配(wxg hxm)

[kuangbin带你飞]专题十 匹配问题

  • 二分图最大匹配及拓展(Hungarian算法)
  • 二分图最优匹配及拓展(KM算法)

[kuangbin]专题39 KM匹配

  • 一般图最大匹配及拓展(带花树算法)

9. 树的问题(fyh hxm wxg)

  • 倍增算法
  • Tarjan算法(离线)
  • RMQ算法

[kuangbin]专题34 RMQ练习

  • 轻重链剖分
  • 长链剖分
  • 树上差分
  • 虚树
  • Dfs序与欧拉序
  • 仙人掌
  • 圆方树

10. 网络流(wxg hxm)

[kuangbin带你飞]专题十一 网络流

  • 最大流与最小割(dinic算法)
  • 费用流及拓展
  • 有上向界的网络流
  • 网络流各种模型
  • 费用流及拓展
  • 有上向界的网络流
  • 网络流各种模型

三、动态规划

1. 背包问题

  • 01背包问题
  • 完全背包问题
  • 多重背包
  • 树上背包问题

2. 状压DP (fyh)

3. 区间DP (fyh)

[kuangbin]永不放弃!怒整DP!(区间)

4. 数位DP (fyh)

[kuangbin]专题十五 数位DP

[kuangbin]永不放弃!怒整DP!(数位)

5. Tree DP

6. 概率期望DP(hxm)

7. 递推DP

8. 动态规划优化(fyh wxg)

[kuangbin带你飞]专题二十 斜率DP

  • 决策单调性优化
  • 数据结构优化
  • 线段树优化DP
  • 单调队列优化DP
  • 四边形不等式优化DP

四、字符串

1. 哈希(hxm)

2. Trie树

  • 01字典树

3. KMP算法与AC自动机(hxm wxg)

[kuangbin带你飞]专题十七 AC自动机

  • 拓展KMP算法
  • 最小表示法

4. 后缀树、后缀数据与后缀自动机(hxm wxg)

[kuangbin带你飞]专题十八 后缀数组

[kuangbin]专题27 后缀自动机

5. Manacher算法、回文树算法与回文自动机(hxm wxg)

[kuangbin]专题十六 KMP & 扩展KMP & Manacher


五、数据结构

[kuangbin带你飞]专题二十四 二分 尺取 单调栈队列

1. 栈

  • 单调栈 

2. 队列

  • 单调队列

3. 堆和优先队列

4. 树状数组

5. 线段树

6. 左偏树

7. 平衡树

[kuangbin]专题28 动态树LCT

9. 链表

  • 块状链表

10. 分块与莫队(hxm)

[kuangbin] 莫队算法

  • 树上分块

11. 可持久化数据结构

  • 主席树

[kuangbin]主席树

[kuangbin]专题33 划分树专场

  • 带修主席树
  • 可持久化数组
  • 可持久化并查集
  • 可持久化Trie
  • 可持久化Treap

12. 树套树


六、数学

[kuangbin]数学训练一

[kuangbin]数学训练二

[kuangbin]数学训练三

[kuangbin]数学训练四 数论

[kuangbin]数学训练五 数论(续)

[kuangbin带你飞]专题十四 基础数论

1. 整除与剩余(fyh hxm)

  • Euclid算法
    • 扩展Euclid算法
    • 类Euclid算法
  • 中国剩余定理及拓展
  • Lucas定理及拓展
  • 原根
  • 二次剩余
  • 离散对数
  • N次剩余
  • 佩尔方程(hxm)

2. 素数与函数(fyh)

3. 线性代数(fyh hxm)

4. 多项式算法(hxm wxg)

5. 数值计算

  • 数值积分
  • 高阶代数方程求根

6. 概率与期望(hxm)

[kuangbin]数学训练六 概率/期望

[kuangbin带你飞]专题二十一 概率&期望

7. 组合数学与容斥原理

8. 其他数学内容

  • 快速幂
  • Catalan 数
  • Fermat定理
  • 第一类与第二类Stirling 数(hxm)

9. 生成函数(hxm wxg)

[kuangbin]专题40 母函数

  • 指数型生成函数
  • 普通型生成函数

10. 置换群论


七、分治算法(wxg)

1. 二分算法

  • 整体二分

2. 三分算法

3. 第K大数

4. 偏序问题(CDQ分治)

5. 点分治(fyh)

[kuangbin]专题38 树分治


八、计算几何(fyh,hxm)

[kuangbin带你飞]专题十三 基础计算几何

[KuangBin]计算几何进阶

1. 线段相交问题

2. 凸多边形面积

3. 最小圆覆盖

4. 扫描线

5. 凸包问题

[kuangbin]计算几何之凸包问题

6. 最近点对问题

7. 圆的交与并

8. 半平面交

[kuangbin]计算几何之半平面交

9. Simpson积分

10. KD-Tree

11. V图


九、博弈论问题

[kuangbin]专题35 博弈论(Ⅰ)

[kuangbin]专题36 博弈论(Ⅱ)

1. 基于动态规划的博弈论问题

  • Sg函数

2. Nim博弈问题

  • Sg函数
  • 反Nim博弈

3. Wythoff博弈问题

4. Surreal Number博弈


十、其他算法

1. 朱-刘算法

2. 无向图最小割

3. 高精度

4. 模拟退火

5. 随机化算法

6. 倍增算法

7. bitset压位