文章前言,一个普通的ACM算法竞赛选手。
以前只知道写题，却没有自己弄一个算法流程，思考许久，决定整理一下算法，先从入门算法入手，如有不足，望指出。
持续更新......,直到完善，现在已经破万了，最后字数粗略估计将会达到6万字。写完有时间的话会写进阶版的。
我将介绍
//一部分人初识算法却不知道要什么情况用,或者说学这个算法不清楚是为了解决什么问题,这里将会一一解答,这篇博客旨在为新手打开兴趣并打下扎实算法基础.
//(你学完了这个博客加上写了给的练习,虽然不会立马变得很xx,但是你看待问题的思维已经发生了改变,希望你以后通过大量练习,熟练运用给出的算法体系 )
//最后,此篇博客为开放给大众的,不涉及任何营销(不要攻击博主).
//里面的每一道例题博主都亲自ac过的,放心食用.
（一）基础算法
1.快速排序
void quick_sort(int q[], int l, int r)//快速排序模板 { if (l >= r) return; int i = l - 1, j = r + 1, x = q[l + r >> 1]; while (i < j) { do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j), quick_sort(q, j + 1, r); }
2.归并排序
void merge_sort(int q[], int l, int r)//归并模板 { 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]; }
3.二分
bool check(int x) {/* ... */} // 检查x是否满足某种性质 // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用： int bsearch_1(int l, int r) { while (l < r) { 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) { while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; } return l; }
4.高精度
5.前缀和与差分
一维前缀和 S[i] = a[1] + a[2] + ... a[i] a[l] + ... + a[r] = S[r] - S[l - 1] 二维前缀和 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] 一维差分 给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c 二维差分 给以(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
6.双指针算法
for (int i = 0, j = 0; i < n; i ++ ) { while (j < i && check(i, j)) j ++ ; // 具体问题的逻辑 } 常见问题分类： (1) 对于一个序列，用两个指针维护一段区间 (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作
7.位运算
1. 求n的第k位数字: n >> k & 1 2. 返回n的最后一位1：lowbit(n) = n & -n
8.离散化
vector<int> alls; // 存储所有待离散化的值 sort(alls.begin(), alls.end()); // 将所有值排序 alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素 // 二分求出x对应的离散化的值 int find(int x) // 找到第一个大于等于x的位置 { int l = 0, r = alls.size() - 1; while (l < r) { int mid = l + r >> 1; if (alls[mid] >= x) r = mid; else l = mid + 1; } return r + 1; // 映射到1, 2, ...n }
9.区间合并
// 将所有存在交集的区间合并 void merge(vector<PII> &segs) { vector<PII> res; sort(segs.begin(), segs.end()); int st = -2e9, ed = -2e9; for (auto seg : segs) if (ed < seg.first) { 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; }
（二） 数据结构
1.单链表
// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点 int head, e[N], ne[N], idx; // 初始化 void init() { head = -1; idx = 0; } // 在链表头插入一个数a void insert(int a) { e[idx] = a, ne[idx] = head, head = idx ++ ; } // 将头结点删除，需要保证头结点存在 void remove() { head = ne[head]; }
2.双链表
// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点 int e[N], l[N], r[N], idx; // 初始化 void init() { //0是左端点，1是右端点 r[0] = 1, l[1] = 0; idx = 2; } // 在节点a的右边插入一个数x void insert(int a, int x) { e[idx] = x; l[idx] = a, r[idx] = r[a]; l[r[a]] = idx, r[a] = idx ++ ; } // 删除节点a void remove(int a) { l[r[a]] = l[a]; r[l[a]] = r[a]; }
3.栈
// tt表示栈顶 int stk[N], tt = 0; // 向栈顶插入一个数 stk[ ++ tt] = x; // 从栈顶弹出一个数 tt -- ; // 栈顶的值 stk[tt]; // 判断栈是否为空 if (tt > 0) { }
4.队列
1.普通队列 // hh 表示队头，tt表示队尾 int q[N], hh = 0, tt = -1; // 向队尾插入一个数 q[ ++ tt] = x; // 从队头弹出一个数 hh ++ ; // 队头的值 q[hh]; // 判断队列是否为空 if (hh <= tt) { } 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) { }
5.单调栈和队列
1.单调栈 常见模型：找出每个数左边离它最近的比它大/小的数 int tt = 0; for (int i = 1; i <= n; i ++ ) { while (tt && check(stk[tt], i)) tt -- ; stk[ ++ tt] = i; } 2.单调队列 常见模型：找出滑动窗口中的最大值/最小值 int hh = 0, tt = -1; for (int i = 0; i < n; i ++ ) { while (hh <= tt && check_out(q[hh])) hh ++ ; // 判断队头是否滑出窗口 while (hh <= tt && check(q[tt], i)) tt -- ; q[ ++ tt] = i; }
6.KMP
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度 求模式串的Next数组： for (int i = 2, j = 0; i <= m; i ++ ) { while (j && p[i] != p[j + 1]) j = ne[j]; if (p[i] == p[j + 1]) j ++ ; ne[i] = j; } // 匹配 for (int i = 1, j = 0; i <= n; i ++ ) { while (j && s[i] != p[j + 1]) j = ne[j]; if (s[i] == p[j + 1]) j ++ ; if (j == m) { j = ne[j]; // 匹配成功后的逻辑 } }
7.trie树
int son[N][26], cnt[N], idx; // 0号点既是根节点，又是空节点 // son[][]存储树中每个节点的子节点 // cnt[]存储以每个节点结尾的单词数量 // 插入一个字符串 void insert(char *str) { int p = 0; for (int i = 0; str[i]; i ++ ) { int u = str[i] - 'a'; if (!son[p][u]) son[p][u] = ++ idx; p = son[p][u]; } cnt[p] ++ ; } // 查询字符串出现的次数 int query(char *str) { int p = 0; for (int i = 0; str[i]; i ++ ) { int u = str[i] - 'a'; if (!son[p][u]) return 0; p = son[p][u]; } return cnt[p]; }
8.并查集
(1)朴素并查集： int p[N]; //存储每个点的祖宗节点 // 返回x的祖宗节点 int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } // 初始化，假定节点编号是1~n for (int i = 1; i <= n; i ++ ) p[i] = i; // 合并a和b所在的两个集合： p[find(a)] = find(b); (2)维护size的并查集： int p[N], size[N]; //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量 // 返回x的祖宗节点 int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } // 初始化，假定节点编号是1~n for (int i = 1; i <= n; i ++ ) { p[i] = i; size[i] = 1; } // 合并a和b所在的两个集合： size[find(b)] += size[find(a)]; p[find(a)] = find(b); (3)维护到祖宗节点距离的并查集： int p[N], d[N]; //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离 // 返回x的祖宗节点 int find(int x) { if (p[x] != x) { int u = find(p[x]); d[x] += d[p[x]]; p[x] = u; } return p[x]; } // 初始化，假定节点编号是1~n for (int i = 1; i <= n; i ++ ) { p[i] = i; d[i] = 0; } // 合并a和b所在的两个集合： p[find(a)] = find(b); d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量
9.堆
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1 // ph[k]存储第k个插入的点在堆中的位置 // hp[k]存储堆中下标是k的点是第几个插入的 int h[N], ph[N], hp[N], size; // 交换两个点，及其映射关系 void heap_swap(int a, int b) { swap(ph[hp[a]],ph[hp[b]]); swap(hp[a], hp[b]); swap(h[a], h[b]); } void down(int u) { int t = u; if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2; if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1; if (u != t) { heap_swap(u, t); down(t); } } void up(int u) { while (u / 2 && h[u] < h[u / 2]) { heap_swap(u, u / 2); u >>= 1; } } // O(n)建堆 for (int i = n / 2; i; i -- ) down(i);
10.哈希表
（一）一般哈希 (1) 拉链法 int h[N], e[N], ne[N], idx; // 向哈希表中插入一个数 void insert(int x) { int k = (x % N + N) % N; e[idx] = x; ne[idx] = h[k]; h[k] = idx ++ ; } // 在哈希表中查询某个数是否存在 bool find(int x) { int k = (x % N + N) % N; for (int i = h[k]; i != -1; i = ne[i]) if (e[i] == x) return true; return false; } (2) 开放寻址法 int h[N]; // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置 int find(int x) { int t = (x % N + N) % N; while (h[t] != null && h[t] != x) { t ++ ; if (t == N) t = 0; } return t; } （二）字符串哈希 核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低 小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果 typedef unsigned long long ULL; ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64 // 初始化 p[0] = 1; for (int i = 1; i <= n; i ++ ) { h[i] = h[i - 1] * P + str[i]; p[i] = p[i - 1] * P; } // 计算子串 str[l ~ r] 的哈希值 ULL get(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; }
