已经全部熟练掌握，还得经常的复习

目录

• 排序
• 二分
• 高精度
• 前缀和
• 差分
• 位运算
• 双指针
• 离散化
• 区间合并

排序

模板题 AcWing 785. 快速排序

786. 第k个数

快速排序
快排的核心思想是分治，选一个当作哨兵让小于等于它的数都在左边，大于等于它的数都在右边
时间复杂度是n(logn)

步骤大致分为以下三步：

• 确定分界点
• 调整区间
• 递归处理左右两段

y神模板:

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); }

总的模板:

#include<cstdio> #include<algorithm> using namespace std; const int N=1e6+10;int n; int a[N];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); } int main(void) {scanf("%d",&n);for(int i=0;i<n;i++) scanf("%d",&a[i]);quick_sort(a,0,n-1);for(int i=0;i<n;i++) printf("%d ",a[i]);return 0; }

归并排序
模板题 AcWing 787. 归并排序

788. 逆序对的数量

快排的核心思想也是分治，不过是以中间位置作为分界点，这和快排是不同的，快排是选择数组中的一个数作为分界点。
时间复杂度是n(logn)

步骤大致分为三步:

• 确定分界点
• 递归排序
• 归并(合二为一)

y神模板:

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]; }

总的模板:

#include<cstdio> using namespace std; const int N=100010; int a[N]; int tmp[N]; 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;int i=l;//左区间的头 int 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(void) {int n; scanf("%d",&n);for(int i=0;i<n;i++) scanf("%d",&a[i]);merge_sort(a,0,n-1);for(int i=0;i<n;i++) printf("%d ",a[i]);puts("");return 0; }

二分

整数二分

模板题 AcWing 789. 数的范围

整数二分的话，就两种情况，我们可以根据check()来判断，是r=mid 还是 l=mid
通过此方法来判断是否加1.

y神模板:

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; }

浮点数二分

模板题 AcWing 790. 数的三次方根

浮点数二分模板，就不需要判断用不用加1的问题了，因为它是连续的。

y神模板:

bool check(double x) {/* ... */} // 检查x是否满足某种性质double bsearch_3(double l, double r) {const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求while (r - l > eps){double mid = (l + r) / 2;if (check(mid)) r = mid;else l = mid;}return l; }

高精度

高精度 加减乘除

高精度加法

y神模板:

// C = A + B, A >= 0, B >= 0 vector<int> add(vector<int> &A, vector<int> &B) {if (A.size() < B.size()) return add(B, A);vector<int> C;int t = 0;for (int i = 0; i < A.size(); i ++ ){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; } vector<int> add(vector<int> &A,vector<int> &B) {vector<int> C;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];C.push_back(t%10);t/=10;}if(t) C.push_back(1);return C; }

高精度减法

y神模板:

// C = A - B, 满足A >= B, A >= 0, B >= 0 vector<int> sub(vector<int> &A, vector<int> &B) {vector<int> C;for (int i = 0, t = 0; i < A.size(); i ++ ){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; }

完整的实例:

#include<iostream> #include<cstdio> #include<string> #include<vector> using namespace std; bool cmp(vector<int> &A,vector<int> &B) {if(A.size()>B.size()) return true;if(A.size()<B.size()) return false;for(int i=A.size()-1;i>=0;i--){if(A[i]>B[i]) return true;if(A[i]<B[i]) return false;}return true; } vector<int> sub(vector<int> &A,vector<int> &B) {vector<int> C;int t=0;for(int i=0;i<A.size();i++){t=A[i]-t;if(i<B.size()) t=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; } int main(void) {string a,b; cin>>a>>b;vector<int>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');if(cmp(A,B)){auto C=sub(A,B);for(int i=C.size()-1;i>=0;i--) cout<<C[i];}else{auto C=sub(B,A);cout<<"-";for(int i=C.size()-1;i>=0;i--) cout<<C[i];} }

高精度乘法

y神模板:

// C = A * b, A >= 0, b >= 0 vector<int> mul(vector<int> &A, int b) {vector<int> 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;}while (C.size() > 1 && C.back() == 0) C.pop_back();return C; }

高精度除法

注意除法跟其它不同，其它我们都是从低位向高位计算。
除法是从高位向地位计算。

y神模板:

// A / b = C ... r, A >= 0, b > 0 vector<int> div(vector<int> &A, int b, int &r) {vector<int> 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());while (C.size() > 1 && C.back() == 0) C.pop_back();return C; }

前缀和

一维前缀和

AcWing 795. 前缀和

y神模板:

S[i] = a[1] + a[2] + ... a[i] a[l] + ... + a[r] = S[r] - S[l - 1]

完整的代码:

#include<cstdio> #include<iostream> using namespace std; const int N=1e5+10; int a[N]; int s[N]; int main(void) {int n,m; cin>>n>>m;for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];while(m--){int l,r; cin>>l>>r;cout<<s[r]-s[l-1]<<endl;}return 0; }

二维前缀和

AcWing 796. 子矩阵的和

y神模板:

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]

完整的代码:

#include<cstdio> #include<iostream> using namespace std; const int N=1010; int n,m,q; int a[N][N],s[N][N]; int main(void) {scanf("%d%d%d",&n,&m,&q);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];}}while(q--){int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);printf("%d\n",s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);}return 0; }

差分

差分是前缀和的一个逆的运算。
我们要构造一个数组 b1,b2,b3,…。使得
b1=a1-a0; b2=a2-a1; b3=a3-a2;
这样 a1=b1=a1; a2=b1+b2=a2 a3=b3+b2+b1=a3;

如果我们想要加只需要在开头加一个c 在结尾的最后一个的下一个减c。
因为是前缀和故一个加上一个数，其它的都会加

一维差分

模板题 AcWing 797. 差分

y神模板:

给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

完整代码:

#include<iostream> #include<cstdio> using namespace std; const int N=101000; int a[N],b[N]; void insert(int l,int r,int c) {b[l]+=c;b[r+1]-=c; } int main(void) {int n,m;cin>>n>>m;for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++) insert(i,i,a[i]);//初始化差分数组while(m--){int l,r,c; cin>>l>>r>>c;insert(l,r,c);}for(int i=1;i<=n;i++) b[i]+=b[i-1];//求前缀和for(int i=1;i<=n;i++) cout<<b[i]<<" ";return 0; }

二维差分

模板题 AcWing 796. 子矩阵的和

y神模板:

给以(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

完整代码:

#include<iostream> #include<cstdio> using namespace std; const int N=1010; int a[N][N],b[N][N]; 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(void) {int n,m,q;cin>>n>>m>>q;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){insert(i,j,i,j,a[i][j]);//初始化}}while(q--){int x1,y1,x2,y2,c;cin>>x1>>y1>>x2>>y2>>c;insert(x1,y1,x2,y2,c);}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];//前缀和}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<b[i][j]<<" ";}cout<<endl;}return 0; }

位运算

AcWing 801. 二进制中1的个数

y神模板:

求n的第k位数字: n >> k & 1 //是从0开始的 返回n的最后一位1：lowbit(n) = n & -n

双指针

AcWIng 799. 最长连续不重复子序列
AcWing 800. 数组元素的目标和
2816. 判断子序列

y神模板:

for (int i = 0, j = 0; i < n; i ++ ) {while (j < i && check(i, j)) j ++ ;// 具体问题的逻辑 } 常见问题分类：(1) 对于一个序列，用两个指针维护一段区间(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

离散化

802. 区间和 【离散化】超详细解析

y神模板:

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 }

区间合并

AcWing 803. 区间合并

y神模板:

// 将所有存在交集的区间合并 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; }

总结

以上是生活随笔为你收集整理的第一章 基础算法 【完结】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。