ACM算法类型大纲 思维导图全
需积分: 0 138 浏览量
2023-07-30
22:46:26
上传
评论
收藏 203KB PDF 举报
ACm
字符串
KMP -> exKMP
AC自动机 ->fail树
后缀数组
后缀自动机
后缀树
后缀平衡树
后缀仙人掌
字符串 Hash
Trie树
可持久化Trie
Trie图
manacher
回文自动机
最小表示法
计算几何
基础知识
向量
点积
叉积
基础知识
凸包
旋转卡壳
半平面交
随机增量
pick定理
梯形部分&三角形部分
扫描线
数论
基础知识
%理论
积性函数
高中部分数学知识
素数
暴力判素数
筛法求素数
埃拉托色尼筛
线性筛（欧拉筛)
Miller-Rabbin素数检测
分解质因数
欧拉函数
sqrt(n)求单个值的欧拉函数
线性筛欧拉函数
欧拉定理
快速幂 慢速幂
gcd
辗转相除法
lcm
egcd
exgcd
求逆元
求同余方程
中国剩余定理(CRT)
互质版
不互质版
矩阵
矩阵快速幂
矩阵求逆
行列式
莫比乌斯反演 莫比乌斯函数
狄利克雷卷积
容斥原理
抽屉原理(鸽巢原理)
Ramsey定理
费马小定理
逆元
exgcd求逆元
线性求逆元
费马小定理求逆元
高斯消元
线性基
排列组合
杨辉三角
Lucas定理
exLucas定理
BSGS exBSGS
数列
斐波那契数列
gcd(f[n],f[m])=f[gcd(n,m)]
卡特兰数
斯特林数
第一类斯特林数
第二类斯特林数
贝尔数
等差、等比数列
通项公式
求和公式
Polya定理
置换群
原根
快速傅里叶变换(FFT)
快速数论变换(NTT)
快速沃尔什变换(FWT)
拉格朗日
拉格朗日乘子法
拉格朗日插值
拉格朗日四平方和定理
线性规划
单纯性
辛普森积分
概率和期望
动态规划
简单dp
背包dp
01背包
完全背包
多重背包
区间dp
状压dp
普通状压->枚举子集dp
斯坦纳树
插头dp
数位dp
树形dp->基环树dp
环形dp
环+外向树上的dp
期望dp
记忆化dp
DAG上的dp
多维动态规划
dp套dp
dp的优化
斜率优化
四边形不等式优化
数据结构优化dp
单调队列优化dp
线段树优化dp
改变状态优化dp
寻址优化
其他算法和思维
二分
三分
整体二分
二分答案
lower_bound
upper_bound
倍增
贪心
枚举
暴力
分治 CDQ分治
离散化
模拟
meet in the middle
排序
快速排序(sort ) 重载运算符
归并排序 归并排序求逆序对
桶排
基数排序
计数排序
插入排序
选择排序
冒泡排序
分块
随机化
前缀和 二维前缀和
高精度 压位
递推，递归 矩阵加速递推
位运算
莫队
树上莫队
带修改的莫队
打表
打表找规律
分段打表
卡常
搜索
bfs
双向bfs
dfs
A*
IDA*
DLX
记忆化搜索
剪枝
可行性剪枝
最优性剪枝
玄学剪枝
模拟退火
遗传算法
爬山算法
随机化搜索
数据结构
队列
单调队列
优先队列(堆)
双端队列
栈单调栈
堆二叉堆
可并堆
可持久化左偏树左偏树○
斜堆
配对堆
斐波那契堆
随机堆
并查集
可持久化并查集
带权并查集
hash表
链表
双向链表
块状链表白可持久化块状链表
十字链表
st表
块状树
树状数组
多维树状数组
树状数组求逆序对
线段树
动态开点线段树
线段树的合并
权值线段树
zkw线段树
二维线段树(线段树套线段树)
可持久化线段树(主席树)
静态第k大
动态第k大
扫描线
平衡树
treap
可持久化treapfhq-treap(无旋treap)
splay
可持久化splay
替罪羊树
红黑树
AVL树
SBT
朝鲜树
Trie树可持久化Trie树
KDtree
划分树
四分树
笛卡尔树
树套树
线段树套平衡树
平衡树套线段树
其他树套树
STL
map
set multiset
stack
queue
priority_queue
bitset
vector
图论
最短路
SPFA
SPFA判负环
SLF优化
LLL优化
dijkstra
堆优化的dijkstra
线段树优化的dijkstra
Floyd
倍增Floyd
K短路
最长路
差分约束
Tarjan
强连通分量/缩点
双连通分量(点、边)
割边、割点、桥
2-sat
拓扑排序
二分图
二分图最大匹配(匈牙利)
二分图最大权匹配(KM)
网络流
最大流/最小割
Dinic
ISAP
最小费用最大流白
SPFA费用流
zkw费用流
有上下界的网络流
数据结构优化网络流
分数规划
欧拉图
树论
生成树
最小生成树
Kruskal
Prim及其堆优化
(严格)次小生成树
最大生成树
其他各种生成树
最优比率生成树
最小瓶颈生成树
生成树计数
暴力统计(划掉)
Matrix-tree定理
LCA
倍增
树剖
tarjan
虚树
基环树
树链剖分
prufer序列
括号序列
dfs序
树的遍历
前序
中序
后序
树上倍增
树的直径
树的重心
树分治
点分治
边分治
动态树分治
Link-Cut-Tree
树分块
区间图与弦图
平面图与对偶图
最小树形图(朱刘算法)
仙人掌动态仙人掌
博弈论
基础
Bash Game
Wythoff Game
Nimm Game
SG函数
A-Beta剪枝
博弈树
极大极小搜索
树形图博弈
资源评论
