已經(jīng)全部熟練掌握，還得經(jīng)常的復習

目錄

• 排序
• 二分
• 高精度
• 前綴和
• 差分
• 位運算
• 雙指針
• 離散化
• 區(qū)間合并

排序

模板題 AcWing 785. 快速排序

786. 第k個數(shù)

快速排序
快排的核心思想是分治，選一個當作哨兵讓小于等于它的數(shù)都在左邊，大于等于它的數(shù)都在右邊
時間復雜度是n(logn)

步驟大致分為以下三步：

• 確定分界點
• 調(diào)整區(qū)間
• 遞歸處理左右兩段

y神模板:

void quick_sort(int q[], int l, int r) {if (l >= r) return;//元素個數(shù)是一個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. 逆序?qū)Φ臄?shù)量

快排的核心思想也是分治，不過是以中間位置作為分界點，這和快排是不同的，快排是選擇數(shù)組中的一個數(shù)作為分界點。
時間復雜度是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;//說明已經(jīng)分成一個一個的了int mid=l+r>>1;merge_sort(q,l,mid),merge_sort(q,mid+1,r);int k=0;int i=l;//左區(qū)間的頭 int j=mid+1; //右區(qū)間的頭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; }

二分

整數(shù)二分

模板題 AcWing 789. 數(shù)的范圍

整數(shù)二分的話，就兩種情況，我們可以根據(jù)check()來判斷，是r=mid 還是 l=mid
通過此方法來判斷是否加1.

y神模板:

bool check(int x) {/* ... */} // 檢查x是否滿足某種性質(zhì)// 區(qū)間[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是否滿足性質(zhì)else l = mid + 1;}return l; } // 區(qū)間[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; }

浮點數(shù)二分

模板題 AcWing 790. 數(shù)的三次方根

浮點數(shù)二分模板，就不需要判斷用不用加1的問題了，因為它是連續(xù)的。

y神模板:

bool check(double x) {/* ... */} // 檢查x是否滿足某種性質(zhì)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; }

差分

差分是前綴和的一個逆的運算。
我們要構(gòu)造一個數(shù)組 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 在結(jié)尾的最后一個的下一個減c。
因為是前綴和故一個加上一個數(shù)，其它的都會加

一維差分

模板題 AcWing 797. 差分

y神模板:

給區(qū)間[l, r]中的每個數(shù)加上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]);//初始化差分數(shù)組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的個數(shù)

y神模板:

求n的第k位數(shù)字: n >> k & 1 //是從0開始的 返回n的最后一位1：lowbit(n) = n & -n

雙指針

AcWIng 799. 最長連續(xù)不重復子序列
AcWing 800. 數(shù)組元素的目標和
2816. 判斷子序列

y神模板:

for (int i = 0, j = 0; i < n; i ++ ) {while (j < i && check(i, j)) j ++ ;// 具體問題的邏輯 } 常見問題分類：(1) 對于一個序列，用兩個指針維護一段區(qū)間(2) 對于兩個序列，維護某種次序，比如歸并排序中合并兩個有序序列的操作

離散化

802. 區(qū)間和 【離散化】超詳細解析

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 }

區(qū)間合并

AcWing 803. 區(qū)間合并

y神模板:

// 將所有存在交集的區(qū)間合并 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});//最后一個區(qū)間segs = res; }

總結(jié)

以上是生活随笔為你收集整理的第一章 基础算法 【完结】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。