长沙 网站优化,网站开发者不给源代码怎么办,网易企业邮箱彻底删除的邮件还能恢复吗,免备案空间网站阶段总结
通过今天晚上的这场div2我深刻的意识到#xff0c;光是会找窍门是远远不够的#xff0c;你得会基础的建图#xff0c;dp#xff0c;高级数据结构#xff0c;你这样才可以不断的提升自己#xff0c;不可以一直在一个阶段停留下去#xff0c;构造题可以刷下去光是会找窍门是远远不够的你得会基础的建图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.husing namespace std;
using i64 long long;
using u32 unsigned;
using u64 unsigned long long;
using pii pairi64, i64;void solve() {int n;cin n;vectorint a(n);for (int i 0; i n; i ) {cin a[i];}functionvoid(vectorint a, int l, int r) quick_sort [](vectorint 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.husing namespace std;
using i64 long long;
using u32 unsigned;
using u64 unsigned long long;
using pii pairi64, i64;void solve() {int n, k;cin n k;vectorint a(n);for (int i 0; i n; i ) {cin a[i];}functionint(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.husing namespace std;
using i64 long long;
using u32 unsigned;
using u64 unsigned long long;
using pii pairi64, i64;void solve() {int n;cin n;vectorint a(n), t(n);for (int i 0; i n; i ) {cin a[i];}functionvoid(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.husing namespace std;
using i64 long long;
using u32 unsigned;
using u64 unsigned long long;
using pii pairi64, i64;void solve() {int n;cin n;vectorint a(n), t(n);for (int i 0; i n; i ) {cin a[i];}functioni64(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.加法
vectorint add(vectorint a, vectorint b) {vectorint 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(vectorint a, vectorint 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;
}vectorint sub(vectorint a, vectorint b) {vectorint 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.乘法
乘法的模板我分为两个一个高精度乘低精度一个高精度乘高精度前一个更常用要比后一个要熟练掌握
vectorint mul(vectorint a, int b) {vectorint 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;
}vectorint mul(vectorint a, vectorint b) {vectorint 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.除法
由于本人不熟悉除法我根本没有用过所以这里我也是复制粘贴来的。原理也不难可以求得商和余数一样类比列竖式。
vectorint div(vectorint A, int b, int r) {vectorint 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项和这是O1的复杂度
vectorint s(n 1);
//....
//经过赋值后
for (int i 1; i n; i ) {s[i] s[i - 1];
}
//不想改变原数组的话也可以这样
//vectorint b(n 1);
//for (int i 0; i n; i ) {
// b[i] b[i - 1] s[i];
//}5.2二维前缀和
和上面同理s[i][j]就表示长为j高为i的矩阵的和
vectorvectorint s(n 10, vectorint (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一维差分
vectorint s(n 1);
for (int i n; i 1; i --) {s[i] - s[i - 1];
}6.2二维差分 vectorvectorint s(n 10, vectorint (m 10));
//...
//初始化完成后
functionvoid(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把这些下标映射成12345…n然后把值加上去这就是离散化。
这种感觉得多做题才会有感觉
10.区间合并
这个其实就相当于是一个操作了能记住就行记不住也能现推
先把所有的区间都存到一个vector里然后传入其中里面的ed和seg.first的判断会因题做点小改变。
st和ed的初始值记住是极小值就行因题有可能也会变
void merge(vectorpii segs) {vectorpii 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;
}
