ACM-Template

由于本地的模板较少较杂，之后会不断更新到github上方便自己查看以经典例题引入

目录

---

1. 基础算法

1.0 sort排序

1.1 二分

1.2 离散化

1.3 归并排序

1.4 前缀和和差分

1.4.1 一维前缀和

1.4.2 二维前缀和

1.4.3 一维差分

1.4.4 二维差分

---

2. 数据结构

2.1 并查集

2.1.1 一般并查集

2.1.2 带权并查集

2.1.3 扩展域并查集(种类并查集)

2.2 单点栈

2.3 单调队列

2.4 树状数组

2.5 线段树

2.5.1 基础线段树

2.5.2 权值线段树

2.6 二叉搜索树(BST)

2.7 Splay伸展树

2.8 分块

2.9 莫队算法

---

3. 搜索

3.1 深度优先搜索(dfs)

3.2 广度优先搜索(bfs)

3.3 双向广搜(dbfs)

---

4. 图论

4.1 树的基础

4.2 图的基础

4.3 最小生成树

4.3.1 Kruskal算法

4.3.2 prim算法

4.4 最短路

4.4.1 单源最短路问题

4.4.1.1 Dijkstra算法

4.4.1.2 bellman-ford算法

4.4.1.3 spfa算法

4.4.2 多源最短路问题(Floyd算法)

4.5 拓扑排序

---

5. 数学知识(数论)

5.1 康托展开和逆康托展开

5.2 快速幂和快速乘

5.3 最大公约数(欧几里得算法)和最小公倍数

5.4 素数筛

5.5 扩展欧几里得算法

5.6 同余和逆元

5.7 欧拉函数

---

6. 动态规划

6.1 线性dp

6.1.1 LIS(最长上升子序列)问题

6.1.2 LCS(最长公共子序列)问题

6.1.3 数字三角形问题

6.1.4 括号匹配问题

6.2 区间dp

6.2.1 枚举区间断点合并两区间

6.2.1 字符串折叠问题枚举折点

6.2.3 只能从左边界或右边界添加元素

6.3 状态压缩dp

6.4 树形dp

6.5 背包问题

6.5.1 0-1背包问题

6.5.2 完全背包问题

6.5.3 多重背包问题

6.5.4 分组背包问题

6.5.5 混合背包问题

6.5.6 二维费用的背包问题

6.5.7 背包问题的方案问题

6.5.8 有依赖的背包问题

6.5.9 泛化物品(详见背包九讲)

---

7. 贪心

---

8. 字符串

8.1 字符串哈希

8.2 KMP

8.3 Manacher算法(马拉车算法)

8.4 字典树(Trie树)

---

9. 计算几何

---

附录1. STL

附录1.1 pair

附录1.2 stack(栈)

附录1.3 queue(队列)

附录1.3.1 一般队列queue

附录1.3.2 双端队列deque

附录1.3.3 优先队列priority_queue

附录1.4 vector(向量)

附录1.5 map(映射)

附录1.6 set(集合)

附录1.7 string(字符串)

附录1.8 algorithm文件头相关

---

附录2. 讲义课件

标题	内容1	内容2	内容3	内容4	题目链接	时间
大一上
第1讲	sort排序	二分	\	\	点我	$2021/12/15$
第2讲	康托展开和逆康托展开	前缀和	差分	EOF的使用	点我	$2021/12/22$
第3讲	快速幂	快速乘	贪心	\	点我	$2021/12/30$
大一寒假
第4讲	STL-pair	STL-栈	STL-队列	STL-vector	点我	$2022/1/25$
第5讲	最大公约数和最小公倍数	素数筛	\	\	点我	$2022/2/23$
大一下
第6讲	深度优先搜索(dfs)	广度优先搜索	\	\	点我	$2022/3/8$
第7讲	树的基础	并查集	\	\	点我	$2022/3/22$
第8讲	图的基础	最小生成树(prim)	最小生成树(Kruskal)	\	点我	$2022/4/5$
第9讲	最短路(上)	Dijkstra算法	spfa算法	\	点我	$2022/4/19$
第10讲	最短路(下)	spfa判负环	Floyd算法	拓扑排序	点我	$2022/4/26$
第11讲	动态规划入门	\	\	\	点我	$2022/5/3$
第12讲(含续)	背包问题	\	\	\	点我	$2022/5/17$
第13讲	扩展欧几里得算法	同余和逆元	欧拉函数	\	点我	$2022/5/31$
大一暑假
暑假第1讲	单调栈和单调队列	双向广搜(dbfs)	扩展域并查集(种类并查集)	带权并查集	点我	$2022/7/4$
暑假第2讲	字符串hash	KMP算法	Manacher算法(马拉车算法)	字典树(Trie树)	点我	$2022/7/7$
暑假第3讲	C++STL	链式前向星	哈夫曼树(优先队列)	强连通分量	点我	$2022/7/11$
暑假第4讲	LCA(最近公共祖先)	Hungary算法(匈牙利算法)	\	\	点我	$2022/7/14$
暑假第5讲	基础线段树	树状数组	离散化	\	点我	$2022/7/18$
暑假第6讲	权值线段树	线段树维护复杂区间	扩展:逆序对	\	点我	$2022/7/21$
暑假第7讲	二叉搜索树(BST)	Splay伸展树	\	\	点我	$2022/7/25$
暑假第8讲	离线思想	分块	莫队算法	\	点我	$2022/7/28$
暑假第9讲	线性dp	区间dp	\	\	点我	$2022/8/1$
暑假第10讲	状态压缩dp	树形dp	\	\	点我	$2022/8/4$