算法阶段总结1

阶段总结

通过今天晚上的这场div2我深刻的意识到，光是会找窍门是远远不够的，你得会基础的建图，dp，高级数据结构，你这样才可以不断的提升自己，不可以一直在一个阶段停留下去，构造题可以刷下去，但是要开始复习之前的东西和新算法的学习了。为此这篇总结，我将以我现在的代码风格写出算法基础课的所有算法模板。

1.快速排序

// Problem: 快速排序
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/787/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Author:lvzihao521
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = pair<i64, i64>;void solve() {int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; i ++) {cin >> a[i];}function<void(vector<int> &a, int l, int r)> quick_sort = [&](vector<int> &a, int l, int r) -> void {if (l >= r) {return ;}int i = l - 1, j = r + 1, x = a[l + r >> 1];while (i < j) {do {i ++;} while (a[i] < x);do {j --;} while (a[j] > x);if (i < j) {swap(a[i], a[j]);}}quick_sort(a, l, j);quick_sort(a, j + 1, r);};quick_sort(a, 0, n - 1);for (int i = 0; i < n; i ++) {cout << a[i] << " \n"[i == n - 1];}
}int main() {int t;t = 1;while (t --) {solve();}return 0;
}

第k个数

// Problem: 第k个数
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/788/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Author:lvzihao521
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = pair<i64, i64>;void solve() {int n, k;cin >> n >> k;vector<int> a(n);for (int i = 0; i < n; i ++) {cin >> a[i];}function<int(int l, int r, int k)> quick_sort = [&](int l, int r, int k) -> int {if (l >= r) {return a[l];}int i = l - 1, j = r + 1, x = a[l + r >> 1];while (i < j) {do {i ++;} while (a[i] < x);do {j --;} while (a[j] > x);if (i < j) {swap(a[i], a[j]);}}if (j - l + 1 >= k) {return quick_sort(l, j, k);} else {return quick_sort(j + 1, r, k - (j - l + 1));}};cout << quick_sort(0, n - 1, k) << endl;
}int main() {int t;t = 1;while (t --) {solve();}return 0;
}

2.归并排序

// Problem: 归并排序
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/789/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Author:lvzihao521
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = pair<i64, i64>;void solve() {int n;cin >> n;vector<int> a(n), t(n);for (int i = 0; i < n; i ++) {cin >> a[i];}function<void(int l, int r)> merge_sort = [&](int l, int r) -> void {if (l >= r) {return ;}int mid = l + r >> 1;merge_sort(l, mid);merge_sort(mid + 1, r);int i = l, j = mid + 1, k = 0;while (i <= mid && j <= r) {if (a[i] <= a[j]) {t[k ++] = a[i ++];} else {t[k ++] = a[j ++];}}while (i <= mid) {t[k ++] = a[i ++];}while (j <= r) {t[k ++] = a[j ++];}for (i = l, k = 0; i <= r; i ++, k ++) {a[i] = t[k];}};merge_sort(0, n - 1);for (int i = 0; i < n; i ++) {cout << a[i] << " \n"[i == n - 1];}
}int main() {int t;t = 1;while (t --) {solve();}return 0;
}

逆序对个数

// Problem: 逆序对的数量
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/790/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Author:lvzihao521
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = pair<i64, i64>;void solve() {int n;cin >> n;vector<int> a(n), t(n);for (int i = 0; i < n; i ++) {cin >> a[i];}function<i64(int l, int r)> merge_sort = [&](int l, int r) -> i64 {i64 res = 0;if (l >= r) {return 0;}int mid = l + r >> 1;res += merge_sort(l, mid) + merge_sort(mid + 1, r);int i = l, j = mid + 1, k = 0;while (i <= mid && j <= r) {if (a[i] <= a[j]) {t[k ++] = a[i ++];} else {t[k ++] = a[j ++];res += mid - i + 1;}}while (i <= mid) {t[k ++] = a[i ++];}while (j <= r) {t[k ++] = a[j ++];}for (i = l, k = 0; i <= r; i ++, k ++) {a[i] = t[k];}return res;};i64 res = merge_sort(0, n - 1);cout << res << endl;
}int main() {int t;t = 1;while (t --) {solve();}return 0;
}

3.二分

二分不是特别简单的题面都是需要写一个check函数的，check函数是二分的一个难点，因题而异，所以我下面的模板是基于check函数写好以后写的

区间左端点

int l = 0, r = 1e9;
while (l < r) {int mid = l + r >> 1;if (check(mid)) r = mid;else l = mid + 1;
}

区间右端点

int l = 0, r = 1e9;
while (l < r) {int mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;
}

4.高精度

高精度顾名思义就是一些数字太大了，比如有1000位，无法直接进行运算，但是我们可以通过把这些数字放到数组里，然后一位一位的做运算，相当于在模拟咱们手动列竖式的感觉

1.加法

vector<int> add(vector<int> &a, vector<int> &b) {vector<int> res;int t = 0;for (int i = 0; i < a.size() || i < b.size(); i ++) {if (i < a.size()) {t += a[i];}if (i < b.size()) {t += b[i];}res.emplace_back(t % 10);t /= 10;}if (t) {res.emplace_back(t);}return res;
}

2.减法

减法的话，他需要多写一个比较函数，因为咱们只能实现大数减小数，如果是小数减大数的话，通过cmp函数改成大数减小数，并且手动加负号就可以，我在这里只是实现一下这两个函数，

在做完运算后，可能会出现123456 - 123000 = 000456的问题，所以最后我们要去除前导零。

bool cmp(vector<int> &a, vector<int> &b) {if (a.size() != b.size()) {return a.size() > b.size();}for (int i = a.size() - 1; i >= 0; i --) {if (a[i] != b[i]) {return a[i] > b[i];}}return true;
}vector<int> sub(vector<int> &a, vector<int> &b) {vector<int> res;int t = 0;for (int i = 0; i < a.size(); i ++) {t = a[i] - t;if (i < b.size()) {t -= b[i];}res.emplace_back((t + 10) % 10);t = t < 0 ? 1 : 0;}while (res.size() > 1 && res.back() == 0) {res.pop_back();}return res;
}

3.乘法

乘法的模板我分为两个，一个高精度乘低精度，一个高精度乘高精度，前一个更常用，要比后一个要熟练掌握

vector<int> mul(vector<int> &a, int b) {vector<int> res;int t = 0;for (int i = 0; i < a.size() || t; i ++) {if (i < a.size()) {t += a[i] * b;}res.emplace_back(t % 10);t /= 10;}while (res.size() > 1 && res.back() == 0) {res.pop_back();}return res;
}

vector<int> mul(vector<int> &a, vector<int> &b) {vector<int> res(a.size() + b.size() + 10);for (int i = 0; i < a.size(); i ++) {for (int j = 0; j < b.size(); j ++) {res[i + j] += a[i] * b[j];}}int t = 0;//完成进位的操作for (int i = 0; i < res.size(); i ++) {t += res[i];res[i] = t % 10;t /= 10;}while (res.size() > 1 && res.back() == 0) {res.pop_back();}return res;
}

4.除法

由于本人不熟悉除法（我根本没有用过），所以这里我也是复制粘贴来的。原理也不难，可以求得商和余数，一样类比列竖式。

vector<int> div(vector<int> &A, int b, int &r) {vector<int> res;r = 0;for (int i = A.size() - 1; i >= 0; i -- ){r = r * 10 + A[i];res.emplace_back(r / b);r %= b;}reverse(res.begin(), res.end());while (res.size() > 1 && res.back() == 0){res.pop_back();}return res;
}

5.前缀和

5.1一维前缀和

这就是给咱们一个数组，然后对他进行一个操作，使得下标为i就是前i项和，这是O（1）的复杂度

vector<int> s(n + 1);
//....
//经过赋值后
for (int i = 1; i <= n; i ++) {s[i] += s[i - 1];
}
//不想改变原数组的话，也可以这样
//vector<int> b(n + 1);
//for (int i = 0; i < n; i ++) {
//    b[i] = b[i - 1] + s[i];
//}

5.2二维前缀和

和上面同理s[i][j]就表示长为j，高为i的矩阵的和

vector<vector<int>> s(n + 10, vector<int> (m + 10));
//...
//经过赋值后
for (int i = 1; i <= n; i ++) {for (int j = 1; j <= m; j ++) {s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];}
}

6.差分

这可以看成是前缀和的逆运算

它可以做到对一个区间内用一次操作来加减一个数

也有题的类型是找最小操作数，也是要用差分

6.1一维差分

vector<int> s(n + 1);
for (int i = n; i >= 1; i --) {s[i] -= s[i - 1];
}

6.2二维差分

vector<vector<int>> s(n + 10, vector<int> (m + 10));
//...
//初始化完成后
function<void(int x1, int y1, int x2, int y2, int r)> insert = [&](int x1, int y1, int x2, int y2, int r) -> void {s[x1][y1] += r;s[x2 + 1][y1] -= r;s[x1][y2 + 1] -= r;s[x2 + 1][y2 + 1] += r;
}
for (int i = 1; i <= n; i ++) {for (int j = 1; j <= n; j ++) {insert(i, j, i, j, s[i][j]);}
}while (q --) {int x1, x2, y1, y2, r;cin >> x1 >> y1 >> x2 >> y2, r;insert(x1, y1, x2, y2, r);
}
//来个前缀和复原
for (int i = 1; i <= n; i ++) {for (int j = 1; j <= m; j ++) {s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];}
}

7.双指针

​ 常用做法

​ 1.两个指针从头一起走

​ 2.一个指针从头开始，一个指针从尾开始

8.位运算

8.1左移<<

在二进制表示下把数字同时向左移动，高位越界舍弃，低位补零。

8.2 右移>>

在二进制补码表示下把数字同时向右移动，高位以0补充，低位越界舍弃

8.3 与&

二进制表示下两位同时为1则为1，否则为0

8.4 或|

二进制表示下只要有一位为1则为1，否则为0

8.5 异或^

二进制表示下两个不同就为1，相同就为0

9. 离散化

这种题就是一些数字分布在一个很大的区间里，但是数字的总个数很少，开不了这么大的数组，怎么办呢，我们可以利用set和map来离散化，用set来把所有要用到的下标记录下来，然后用map把这些下标映射成1，2，3，4，5…n，然后把值加上去，这就是离散化。

这种感觉得多做题才会有感觉

10.区间合并

这个其实就相当于是一个操作了，能记住就行，记不住也能现推

先把所有的区间都存到一个vector里，然后，传入其中，里面的ed和seg.first的判断会因题做点小改变。

st和ed的初始值记住是极小值就行，因题有可能也会变

void merge(vector<pii> &segs) {vector<pii> res;int st = -2e9, ed = -2e9;sort(segs.begin(), segs.end());for (auto seg : segs) {if (ed < seg.first) {if (st != -2e9) {res.emplace_back(st, ed);}st = seg.first, ed = seg.second;} else {ed = max(ed, seg.second);}}if (st != -2e9) {res.emplace_back(st, ed);}segs = res;
}