1.基础算法 —— 代码模板链接 常用代码模板1——基础算法
排序
二分
高精度
前缀和与差分
双指//代码效果参考：http://www.jhylw.com.cn/442920807.html
针算法位运算
离散化
区间合并
2.数据结构 —— 代码模板链接 常用代码模板2——数据结构
链表与邻接表：树与图的存储
栈与队列：单调队列、单调栈
kmp
Trie
并查集
堆
Hash表
C++ STL使用技巧
3.搜索与图论 —— 代码模板链接 常用代码模板3——搜索与图论
DFS与BFS
树与图的遍历：拓扑排序
最短路
最小生成树
二分图：染色法、匈牙利算法
4.数学知识 —— 代码模板链接 常用代码模板4——数学知识
质数
约数
欧拉函数
快速幂
扩展欧几里得算法
中国剩余定理
高斯消元
组合计数
容斥原理
简单博弈论
5.动态规划
背包问题
线性DP
区间DP
计数类DP
数位统计DP
状态压缩DP
树形DP
记忆化搜索
1.常用代码模板1——基础算法
快速排序算//代码效果参考：http://www.jhylw.com.cn/364637537.html
法模板 —— 模板题 AcWing 785. 快速排序void quick_sort(int q【】, int l, int r)
{undefined
if (l >= r) return;
int i = l - 1, j = r + 1, x = q【l + r ] 1】;
while (i [span style="color: rgba(0, 0, 0, 1)"> j)
{undefined
do i ++ ; while (q【i】 [span style="color: rgba(0, 0, 0, 1)"> x);
do j -- ; while (q【j】 > x);
if (i [span style="color: rgba(0, 0, 0, 1)"> j) swap(q【i】, q【j】);
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
归并排序算法模板 —— 模板题 AcWing 787. 归并排序
void merge_sort(int q【】, int l, int r)
{undefined
if (l >= r) return;
int mid = l + r ] 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q【i】 < q【j】) tmp【k ++ 】 = q【i ++ 】;
else tmp【k ++ 】 = q【j ++ 】;
while (i <= mid) tmp【k ++ 】 = q【i ++ 】;
while (j <= r) tmp【k ++ 】 = q【j ++ 】;
for (i = l, j = 0; i <= r; i ++, j ++ ) q【i】 = tmp【j】;
}
整数二分算法模板 —— 模板题 AcWing 789. 数的范围
bool check(int x) {/ ... /} // 检查x是否满足某种性质
// 区间【l, r】被划分成【l, mid】和【mid + 1, r】时使用：
int bsearch_1(int l, int r)
{undefined
while (l [span style="color: rgba(0, 0, 0, 1)"> r)
{undefined
int mid = l + r ] 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间【l, r】被划分成【l, mid - 1】和【mid, r】时使用：
int bsearch_2(int l, int r)
{undefined
while (l [span style="color: rgba(0, 0, 0, 1)"> r)
{undefined
int mid = l + r + 1 ] 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
浮点数二分算法模板 —— 模板题 AcWing 790. 数的三次方根
bool check(double x) {/ ... /} // 检查x是否满足某种性质
double bsearch_3(double l, double r)
{undefined
const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求
while (r - l > eps)
{undefined
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
高精度加法 —— 模板题 AcWing 791. 高精度加法
// C = A + B, A >= 0, B >= 0
vector[span style="color: rgba(0, 0, 255, 1)">intintint
{undefined
if (A.size() < B.size()) return add(B, A);
vector[span style="color: rgba(0, 0, 255, 1)">int
int t = 0;
for (int i = 0; i < A.size(); i ++ )
{undefined
t += A【i】;
if (i < B.size()) t += B【i】;
C.push_back(t % 10);
t /= 10;
}
if (t) C.push_back(t);
return C;
}
高精度减法 —— 模板题 AcWing 792. 高精度减法
// C = A - B, 满足A >= B, A >= 0, B >= 0
vector[span style="color: rgba(0, 0, 255, 1)">intintint
{undefined
vector[span style="color: rgba(0, 0, 255, 1)">int
for (int i = 0, t = 0; i < A.size(); i ++ )
{undefined
t = A【i】 - t;
if (i < B.size()) t -= B【i】;
C.push_back((t + 10) % 10);
if (t < 0) t = 1;
else t = 0;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
高精度乘低精度 —— 模板题 AcWing 793. 高精度乘法
// C = A b, A >= 0, b > 0
vector[span style="color: rgba(0, 0, 255, 1)">intint
{undefined
vector[span style="color: rgba(0, 0, 255, 1)">int
int t = 0;
for (int i = 0; i < A.size() || t; i ++ )
{undefined
if (i < A.size()) t += A【i】 b;
C.push_back(t % 10);
t /= 10;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
高精度除以低精度 —— 模板题 AcWing 794. 高精度除法
// A / b = C ... r, A >= 0, b > 0
vector[span style="color: rgba(0, 0, 255, 1)">intint
{undefined
vector[span style="color: rgba(0, 0, 255, 1)">int
r = 0;
for (int i = A.size() - 1; i >= 0; i -- )
{undefined
r = r * 10 + A【i】;
C.push_back(r / b);
r %= b;
}
reverse(C.begin(), C.end());
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
一维前缀和 —— 模板题 AcWing 795. 前缀和
S【i】 = a【1】 + a【2】 + ... a【i】
a【l】 + ... + a【r】 = S【r】 - S【l - 1】
二维前缀和 —— 模板题 AcWing 796. 子矩阵的和
S【i, j】 = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S【x2, y2】 - S【x1 - 1, y2】 - S【x2, y1 - 1】 + S【x1 - 1, y1 - 1】
一维差分 —— 模板题 AcWing 797. 差分
给区间【l, r】中的每个数加上c：B【l】 += c, B【r + 1】 -= c
二维差分 —— 模板题 AcWing 798. 差分矩阵
给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S【x1, y1】 += c, S【x2 + 1, y1】 -= c, S【x1, y2 + 1】 -= c, S【x2 + 1, y2 + 1】 += c
位运算 —— 模板题 AcWing 801. 二进制中1的个数
求n的第k位数字: n ] k & 1
返回n的最后一位1：lowbit(n) = n & -n
双指针算法 —— 模板题 AcWIng 799. 最长连续不重复子序列, AcWing 800. 数组元素的目标和
for (int i = 0, j = 0; i < n; i ++ )
{undefined
while (j < i && check(i, j)) j ++ ;
// 具体问题的逻辑
}
常见问题分类：
(1) 对于一个序列，用两个指针维护一段区间
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作
离散化 —— 模板题 AcWing 802. 区间和
vector[span style="color: rgba(0, 0, 255, 1)">int
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素
二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{undefined
int l = 0, r = alls.size() - 1;
while (l [span style="color: rgba(0, 0, 0, 1)"> r)
{undefined
int mid = l + r ] 1;
if (alls【mid】 >= x) r = mid;
else l = mid + 1;
}
return r + 1; // 映射到1, 2, ...n
}
区间合并 —— 模板题 AcWing 803. 区间合并
// 将所有存在交集的区间合并
void merge(vector
&segs)
{undefined
vector
res;
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
for (auto seg : segs)
if (ed [span style="color: rgba(0, 0, 0, 1)"> seg.first)
{undefined
if (st != -2e9) res.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);
if (st != -2e9) res.push_back({st, ed});
segs = res;
}
2.常用代码模板2——数据结构
单链表 —— 模板题 AcWing 826. 单链表
// head存储链表头，e【】存储节点的值，ne【】存储节点的next指针，idx表示当前用到了哪个节点
int head, e【N】, ne【N】, idx;
// 初始化
void init()
{undefined
head = -1;
idx = 0;
}
// 在链表头插入一个数a
void insert(int a)
{undefined
e【idx】 = a, ne【idx】 = head, head = idx ++ ;
}
// 将头结点删除，需要保证头结点存在
void remove()
{undefined
head = ne【head】;
}
双链表 —— 模板题 AcWing 827. 双链表
// e【】表示节点的值，l【】表示节点的左指针，r【】表示节点的右指针，idx表示当前用到了哪个节点
int e【N】, l【N】, r【N】, idx;
// 初始化
void init()
{undefined
//0是左端点，1是右端点
r【0】 = 1, l【1】 = 0;
idx = 2;
}
// 在节点a的右边插入一个数x
void insert(int a, int x)
{undefined
e【idx】 = x;
l【idx】 = a, r【idx】 = r【a】;
l【r【a】】 = idx, r【a】 = idx ++ ;
}
// 删除节点a
void remove(int a)
{undefined
l【r【a】】 = l【a】;
r【l【a】】 = r【a】;
}
栈 —— 模板题 AcWing 828. 模拟栈
// tt表示栈顶
int stk【N】, tt = 0;
// 向栈顶插入一个数
stk【 ++ tt】 = x;
// 从栈顶弹出一个数
tt -- ;
// 栈顶的值
stk【tt】;
// 判断栈是否为空
if (tt > 0)
{undefined
}
队列 —— 模板题 AcWing 829. 模拟队列
1. 普通队列：
// hh 表示队头，tt表示队尾
int q【N】, hh = 0, tt = -1;
// 向队尾插入一个数
q【 ++ tt】 = x;
// 从队头弹出一个数
hh ++ ;
// 队头的值
q【hh】;
// 判断队列是否为空
if (hh <= tt)
{undefined
}
2. 循环队列
// hh 表示队头，tt表示队尾的后一个位置
int q【N】, hh = 0, tt = 0;
// 向队尾插入一个数
q【tt ++ 】 = x;
if (tt == N) tt = 0;
// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;
// 队头的值
q【hh】;
// 判断队列是否为空
if (hh != tt)
{undefined
}
单调栈 —— 模板题 AcWing 830. 单调栈
常见模型：找出每个数左边离它最近的比它大/小的数
