一、ACWing笔记整理

一、基础算法1.快速排序--不稳定算法思路两个指针从最左最右出发当指向数x时向中间移动若则两指针指向数交换#include iostream using namespace std; const int N 1e6 10; int n; int q[N]; void quick_sort(int q[], int l, int r) { if (l r) return; int x q[l], i l - 1, j r 1;//x可取q[r]或者q[(lr)/2] 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, l, i-1);但是这时x不可取q[l]不然会死循环 eg1 2 quick_sort(q, j 1, r);//quick_sort(q, i, r); } int main() { scanf(%d, n); for (int i 0; i n; i ) scanf(%d, q[i]); quick_sort(q, 0, n - 1); for (int i 0; i n; i ) printf(%d , q[i]); return 0; }2.归并排序算法思路a.确定分界点mid(lr)/2 b.归并排序left right c. 合二为一[双指针分别指向两部分的第一即最小值比对两个最小值将更小的放进tmp数组同时此指针向后移动]#includeiostream using namespace std; const int N 1000010; int n; int q[N], tmp[N]; void merge_sort(int q[], int l, int r) { if (l r) return; int mid (lr)/2; 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]; } int main() { scanf(%d, n); for (int i 0; i n; i ) scanf(%d, q[i]); merge_sort(q, 0, n - 1); for (int i 0; i n; i ) printf(%d , q[i]); return 0; }3.二分查找3.1 整数二分#include iostream using namespace std; // 整数二分 /* 有单调性一定可以二分 但没有单调性可以二分 二分的本质不是单调性而是边界 第一种二分 FIRST 先找一个mid (lr1) /2 check mid true [mid,r] l mid **如果l取mid则要1 false [l,mid-1] r mid-1 如何考虑用什么模板 先写一个check函数 再考虑如何更新区间 第二种二分 Second mid (lr1) /2 check mid true [l,mid-1] r mid **如果r取mid则不用1 false [mid1,r] l mid1 */ const int N100005; int a[N]; int n,m; int main() { cinnm; for(int i0;in;i) scanf(%d,a[i]); while(m--){ int x; scanf(%d,x); int l0,rn-1; while(lr){ int mid (lr)/2; if(a[mid]x) rmid; else lmid1; } if(a[l]!x)cout-1 -1endl; else { coutl ; int l0,rn-1; while(lr){ int mid(lr1)/2; if(a[mid]x) l mid; else r mid-1; } coutlendl; } } return 0; }4.高精度vector是 C 标准库中的一种动态数组容器它可以根据需要自动调整大小支持在尾部快速添加或删除元素并且能够像普通数组一样通过下标随机访问元素。push_back(val)在末尾添加一个元素。pop_back()删除末尾元素不返回该元素。size()返回当前元素个数。4.1高精度加法#include iostream #include vector #includestring using namespace std; vectorint add(vectorint A, vectorint B) { //为了方便计算让A中保存较长的数字 B中保存较短的数字 if (A.size() B.size()) return add(B, A); //保存结果的数组 vectorint C; //进位开始时是0 int t 0; //依次计算每一位 for (int i 0; i A.size(); i ) { t A[i];//加上 A 的第 i 位上的数字 if (i B.size()) t B[i];//加上 B 的第 i 位上的数字 C.push_back(t % 10); //C 中放入结果 t / 10;//t 更新成进位 } //最后如果进位上有数放进结果数组 if (t) C.push_back(t); return C;//返回结果 } int main() { string a, b;//以字符串形式保存输入的两个整数 vectorint A, B;//保存两个整数的数组 cin a b;//接收输入 for (int i a.size() - 1; i 0; i -- ) A.push_back(a[i] - 0);//倒序存储第一个数 for (int i b.size() - 1; i 0; i -- ) B.push_back(b[i] - 0);//倒序存储第二个数 auto C add(A, B);//auto根据初始化表达式的类型自动推导变量的类型--这里会自动推导成vectorint类型 for (int i C.size() - 1; i 0; i -- ) cout C[i];//倒序输出C中的数字 cout endl; return 0; }4.2高精度减法#include iostream #include vector #includestring using namespace std; // 判断是否有 A B 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; } // C A - B vectorint sub(vectorint A, vectorint B) { vectorint C; for (int i 0, t 0; i A.size(); i) { t A[i] - t;//后边t是借位的值1/0 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();//去除前导0 return C; } int main() { string a, b; vectorint A, B; cin a b; // a 123456 for (int i a.size() - 1; i 0; i--) A.push_back(a[i] - 0); // A [6, 5, 4, 3, 2, 1] for (int i b.size() - 1; i 0; i--) B.push_back(b[i] - 0); if (cmp(A, B)) { auto C sub(A, B); for (int i C.size() - 1; i 0; i--) printf(%d, C[i]); } else { auto C sub(B, A); printf(-); for (int i C.size() - 1; i 0; i--) printf(%d, C[i]); } return 0; }4.3高精度乘法把b看成整体去做乘法#include iostream #include vector #include string using namespace std; // C A * b vectorint mul(vectorint A, int b) { vectorint C; int t 0; // 进位 for (int i 0; i A.size() || t; i ) { if (i A.size()) t A[i] * b; C.push_back(t % 10); t / 10; } return C; } int main() { string a; int b; cin a b; vectorint A; for (int i a.size() - 1; i 0; i -- ) A.push_back(a[i] - 0); auto C mul(A, b); for (int i C.size() - 1; i 0; i -- ) printf(%d, C[i]); return 0; }4.4高精度除法函数里加了r来传递余数#include iostream #include vector #include algorithm #include string using namespace std; // A / b商是C余数是r vectorint div(vectorint A, int b, int r)//这里必须用r才能把r的值传回main函数 { vectorint C; r 0; for (int i A.size() - 1; i 0; i -- ) { r r * 10 A[i]; C.push_back(r / b); r % b; } reverse(C.begin(), C.end());//用reverse要#include algorithm while (C.size() 1 C.back() 0) C.pop_back(); return C; } int main() { string a; int b; cin a b; vectorint A; for (int i a.size() - 1; i 0; i -- ) A.push_back(a[i] - 0); int r; auto C div(A, b, r); for (int i C.size() - 1; i 0; i -- ) printf(%d, C[i]); cout endl r endl; return 0; }5.前缀和与差分5.1一维前缀和#includeiostream using namespace std; const int N1e510; int n;int m; int q[N];int s[N]; int main(){ cinnm; for(int i1;in;i) scanf(%d,q[i]); s[0]0; for(int i1;in;i){ s[i]s[i-1]q[i]; } int l,r; for(int i1;im;i){ cinlr; printf(%d\n,(s[r]-s[l-1])); } return 0; }5.2二维前缀和#includeiostream using namespace std; const int N1e310; int n;int m;int qq; int q[N][N];int s[N][N]; int main(){ cinnmqq; for(int i1;in;i){ for(int j1;jm;j){ scanf(%d,q[i][j]); } } for(int i1;in;i){ s[i][0]0;s[0][i]0; } for(int i1;in;i){ for(int j1;jm;j){ s[i][j]s[i-1][j]s[i][j-1]q[i][j]-s[i-1][j-1]; } } int x1,x2,y1,y2; for(int i1;iqq;i){ ciny1y2x1x2; printf(%d\n,(s[x1][x2]s[y1-1][y2-1]-s[y1-1][x2]-s[x1][y2-1])); } return 0; }5.3一维差分#includeiostream using namespace std; const int N1e510; int n,m; int q[N];int s[N]; int main(){ cinnm; s[0]q[0]0; for(int i1;in;i){ cinq[i]; s[i]q[i]-q[i-1]; } int l,r,c; for(int i0;im;i){ cinlrc; s[l]c;s[r1]-c; } for(int i1;in;i){ q[i]s[i]q[i-1]; printf(%d ,q[i]); } return 0; }5.4二维差分当于构造矩阵b让原矩阵a是新矩阵b的前缀和#includeiostream using namespace std; const int N1e310; int n, m, qq; int a[N][N], b[N][N]; // 统一标准x代表行y代表列 // 左上角 (x1, y1) 右下角 (x2, y2) void insert(int x1, int y1, int x2, int y2, int c){ b[x1][y1] c; b[x2 1][y1] - c; b[x1][y2 1] - c; b[x2 1][y2 1] c; } int main(){ cin n m qq; // 1. 读取原矩阵并初始化差分矩阵 b for(int i 1; i n; i){ for(int j 1; j m; j){ cin a[i][j]; insert(i, j, i, j, a[i][j]); } } // 2. 处理 qq 次区间修改操作 for(int i 1; i qq; i){ int x1, y1, x2, y2, c; cin x1 y1 x2 y2 c; // 补上 c且按正常顺序读入 insert(x1, y1, x2, y2, c); } // 3. 求二维前缀和将差分矩阵 b 还原为最终答案并输出 for(int i 1; i n; i){ for(int j 1; j m; j){ b[i][j] b[i-1][j] b[i][j-1] - b[i-1][j-1]; cout b[i][j] ; } cout endl; } return 0; }6.双指针算法6.1最长连续不重复子序列#include iostream using namespace std; const int N 100010; int n; int a[N], s[N]; int main() { cin n; for (int i 0; i n; i ) cin a[i]; int res 0; for (int i 0, j 0; i n; i ) { s[a[i]] ; while (s[a[i]] 1) { s[a[j]] -- ; j ; } res max(res, i - j 1); } cout res endl; return 0; }6.2找数组元素目标和#include iostream using namespace std; const int N 100010; int m, n, k; int a[N], b[N]; int main() { cin n m k; for (int i 0; i n; i) cin a[i]; for (int i 0; i m; i) cin b[i]; int i 0; int j m - 1; while(i n j 0){ if(a[i] b[j] k){ cout i j ; return 0; } else if(a[i] b[j] k){ j - 1; } else if(a[i] b[j] k){ i 1; } } return 0; }6.3略7.位运算求n的第k位数字: n k 1返回n的最后一位1lowbit(n) n -n#includeiostream using namespace std; const int N1e510; int n; int lowbit(int x){ return (x (-x)); } int main(){ cinn; while(n--){ int x;int num0; cinx; while(x){ x-lowbit(x); num; } coutnum ; } return 0; }8.离散化#includeiostream #includevector #includealgorithm using namespace std; const int N3e510; typedef pairint,int PII; vectorPII adds,querys; vectorint alls; int q[N],s[N]; int finds(int x){ int l0;int ralls.size()-1; int mid(lr)/2; while(lr){ int mid(lr)/2; if(alls[mid]x) rmid;//有 else lmid1; } return l1;//因为s[]从1开始 而非0 } int main(){ int n,m; cinnm; for(int i0;in;i){ int x,c; cinxc; adds.push_back({x,c}); alls.push_back(x); } for(int i0;im;i){ int l,r; cinlr; querys.push_back({l,r}); alls.push_back(l);alls.push_back(r); } sort(alls.begin(),alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end());//unique返回的是末尾重复的第一个元素坐标 for(auto item:adds){ int xfinds(item.first); q[x]item.second; } for(int i1;ialls.size();i){//从i1开始不然s[-1]要越界 s[i]s[i-1]q[i]; } for(auto item:querys){ int lfinds(item.first);int rfinds(item.second); couts[r]-s[l-1]endl; } return 0; }9.区间合并#includeiostream #includevector #includealgorithm//sort using namespace std; const int N3e510; typedef pairint,int PII; int n;vectorPII segs; void merge(vectorPII segs){//必须加不然用不了.first .second以及最后res传不回主函数 vectorPII res; int l-1e9-10,r-1e9-10; for(auto item:segs){ if(ritem.first){ if(l!-1e9-10) res.push_back({l,r}); litem.first;ritem.second; } else{ rmax(r,item.second); } } if(l!-1e9-10) res.push_back({l,r}); segsres; } int main(){ cinn; while(n--){ int l,r; scanf(%d%d,l,r); segs.push_back({l,r}); } sort(segs.begin(),segs.end()); merge(segs); printf(%d,segs.size()); return 0; }