• 基础算法 - 常见算法模板题（最简洁写法）【上】

    目录

    快速排序

    第k个数

    归并排序

    逆序对的数量

    二分查找

    数的范围

    浮点数二分 

    高精度

    高精度加法

    高精度减法

    高精度乘法（高精度x低精度）

    高精度除法

    前缀和与差分

    前缀和

    子矩阵的和

    差分

    差分矩阵


    快速排序

    思路：

    1. 确认分界点：x=q[(l+r)/2]
    2. 调整范围，使得在x左边的数小于x，右边的数大于x
    3. 递归处理左右两端
    1. #include 
    2.  
    3. using namespace std;
    4.  
    5. const int N = 1000010;
    6.  
    7. int q[N];
    8.  
    9. void quick_sort(int q[],int l,int r)
    10. {
    11.     if(l>=r) return ;
    12.     
    13.     int i=l-1,j=r+1,x=q[l+r>>1];
    14.     while(i
    15.     {
    16.         do i++; while(q[i]//碰到大于x的停止
    17.         do j--; while(q[j]>x);  //碰到小于x的停止
    18.         if(iswap(q[i],q[j]);
    19.         
    20.     }   //最终使得在x左边的数小于x，右边的数大于x
    21.     
    22.     quick_sort(q,l,j);  //对左区间进行处理
    23.     quick_sort(q,j+1,r);
    24. }
    25.  
    26. int main()
    27. {
    28.     int n;
    29.     scanf("%d", &n);
    30.  
    31.     for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    32.  
    33.     quick_sort(q, 0, n - 1);
    34.  
    35.     for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
    36.  
    37.     return 0;
    38. }

    第k个数

    1. #include
    2. using namespace std;
    3. int n,a[1000001],k;
    4.  
    5. void qsort(int a[],int l,int r)
    6. {
    7.     if(l>=r) return ;
    8. 	int i=l-1,j=r+1,x=a[l+r>>1];
    9. 	while(i
    10. 	{
    11. 	    do i++; while(a[i]
    12. 	    do j--; while(a[j]>x);
    13. 	    if(iswap(a[i],a[j]);
    14. 	}
    15. 	qsort(a,l,j);
    16. 	qsort(a,j+1,r);
    17. }
    18. int main()
    19. {
    20.     cin>>n>>k;
    21.     for(int i=0;i>a[i];
    22.     qsort(a,0,n-1);
    23.     cout<-1]<<" ";
    24. }

    归并排序

     思路：

    1. 递归均分如图区间
    2. 对每层区间数值按照从小到大顺序存入tmp（可能是奇数无法均分，需要将剩余直接着存入）
    3.  将该层tmp中排好序的数值放入原来的q中
    4. 回溯到上一层，重复2,3操作，直到最顶层的left>=right，排序完成
    1. #include
    2. using namespace std;
    3. const int N = 1000010;
    4. int n;
    5. int q[N], tmp[N];
    6.  
    7. void merge_sort(int q[], int l, int r)
    8. {
    9. 	if (l >= r) return;
    10. 	int mid = l + r >> 1;
    11. 	merge_sort(q, l, mid), merge_sort(q, mid + 1, r);//递归均分区间
    12. 	
    13. 	int k = 0, i = l, j = mid + 1;
    14. 	while (i <= mid && j <= r)
    15. 		if (q[i] <= q[j]) tmp[k++] = q[i++];//按照从小到大顺序存入tmp
    16. 		else tmp[k++] = q[j++];
    17. 		
    18. 	while (i <= mid) tmp[k++] = q[i++];     //将剩余的接着存入
    19. 	while (j <= r) tmp[k++] = q[j++];
    20.  
    21. 	for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];//把排好的数放回q
    22. }
    23. int main()
    24. {
    25. 	scanf("%d", &n);
    26. 	for (int i = 0; i < n; i++) scanf("%d", &q[i]);
    27.  
    28. 	merge_sort(q, 0, n - 1);
    29.  
    30. 	for (int i = 0; i < n; i++) printf("%d ", q[i]);
    31. 	
    32. 	return 0;
    33. }

    逆序对的数量

    - 归并排序合并过程中计算逆序对数量
    - 若 a[i] > a[j]，则a[i] 和它后面的元素都大于 a[j]，a[i] 构成逆序对数量：res += mid - i + 1; 

    1. #include 
    2.  
    3. using namespace std;
    4.  
    5. typedef long long LL;
    6.  
    7. const int N = 1e5 + 10;
    8.  
    9. int a[N], tmp[N];
    10.  
    11. LL merge_sort(int q[],int l,int r)
    12. {
    13.     if(l>=r) return 0;
    14.     int mid =l+r >>1;
    15.     LL res=merge_sort(q,l,mid)+merge_sort(q,mid+1,r);
    16.     
    17.     int k=0,i=l,j=mid+1;
    18.     while(i<=mid && j<=r)
    19.     {
    20.         if(q[i]<=q[j]) tmp[k++]=q[i++];
    21.         else
    22.         {
    23.             res+=mid-i+1;
    24.             tmp[k++]=q[j++];
    25.         }
    26.     }
    27.     while(i<=mid) tmp[k++]=q[i++];
    28.     while(j<=r) tmp[k++]=q[j++];
    29.     
    30.     for(i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];
    31.     return res;
    32. }
    33.  
    34. int main()
    35. {
    36.     int n;
    37.     scanf("%d", &n);
    38.     for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    39.  
    40.     cout << merge_sort(a, 0, n - 1) << endl;
    41.  
    42.     return 0;
    43. }
    44.

    二分查找

    二分模板

    1. //区间[l，r]被划分成[l,mid]和[mid + 1，r]时使用:
    2. int bsearch_1(int 1, int r)
    3. {
    4. 	while (l < r) 
    5. 	{
    6. 		int mid = l + r >> 1;
    7. 		if (check(mid)) r = mid; 	//判断mid是否满足性质
    8. 		else l = mid + 1;
    9. 	}
    10. 	return l;
    11. }
    12.  
    13. //区间[l,r]被划分成[l，mid - 1]和[mid, r]时使用:
    14. int bsearch_2(int l, int r)
    15. {
    16. 	while (l < r) 
    17. 	{
    18. 		int mid = l + r + 1 >> 1;
    19. 		if (check(mid)) l = mid; 
    20. 		else r = mid - 1;
    21. 	}
    22. 	return l;
    23. }

    记忆口诀：有减必有加

    数的范围

     思路：

    1. 利用二分，保证每次缩小范围时所求值都在范围中
    2. 一个需要找到>=x的第一个数，另一个需要找到<=x的最后一个数
    1. ​
    2. #include 
    3. #include 
    4. using namespace std;
    5. const int N = 1e5 + 10;
    6. int q[N];
    7.  
    8. int SL(int l, int r, int x) {
    9.   while (l < r) {
    10.     int mid = l + r >> 1;
    11.     if (q[mid] >= x) r = mid;
    12.     else l = mid + 1 ;
    13.   }
    14.   return l;
    15. }
    16.  
    17. int SR (int l, int r, int x) {
    18.   while (l < r) {
    19.     int mid = l + r + 1 >> 1;
    20.     if(q[mid] <= x) l = mid;
    21.     else r = mid - 1;
    22.   }
    23.   return r;
    24. }
    25.  
    26. int main() { int n,m;
    27.     scanf ("%d%d",&n,&m);
    28.     for(int i=0;iscanf ("%d",&q[i]);
    29.     while ( m-- ) {
    30.         int x;
    31.         scanf ("%d",&x);
    32.         int l = SL(0, n - 1, x);//查找左边界 并返回下标l
    33.         if (q[l]!=x) cout <<"-1 -1"<//如果找不到  返回-1 -1
    34.         else {
    35.             cout << l << ' '; //如果找到了  输出左下标
    36.             cout << SR(0, n - 1, x) << endl; //输出右下标
    37.         }
    38.     }
    39.     return 0;
    40. }
    41.  
    42.  
    43. ​

    浮点数二分 

    思路：

    因为完全不必考虑 m=(l+r)/2;导致精度丢失的问题，所以可以直接缩范围

    （借用大佬笔记） 

    1. #include
    2. using namespace std;
    3. int main()
    4. {
    5.     double l=-100000,r=100000;    //数据结果必在其之间，不用思考
    6.     double n,m;
    7.     cin>>n;
    8.     while(r-l>1e-8)    //精确到为1e-6，所以至少要多精确两位
    9.     {
    10.         m=(l+r)/2;
    11.         if(m*m*m>=n) r=m;    //立方根n在mid的左边，缩右边界
    12.         else l=m;
    13.     }
    14.     printf("%.6f",m);
    15.    return 0;
    16. }

    高精度

    高精度加法

    思路：

    1. #include 
    2. using namespace std;
    3.  
    4. const int N = 100010;
    5. int A[N], B[N], C[N];
    6.  
    7. int Add(int a[], int b[], int c[], int cnt) {
    8.  
    9.     int t = 0;//t表示进位
    10.  
    11.     for (int i=1; i<=cnt; i++) {
    12.         t += a[i] + b[i];//进位加上a和b第i位上的数
    13.         c[i] = t % 10;//c的值就是进位的个位数
    14.         t /= 10;//把t的个位数去掉只剩下十位数，即只剩下这个位置的进位
    15.     }
    16.     if (t) c[++cnt] = 1;//如果t==1，表示还有一个进位，要补上
    17.  
    18.     return cnt;
    19. }
    20.  
    21. int main() {
    22.  
    23.     string a, b;
    24.     cin >> a >> b;  
    25.  
    26.  
    27.     //A和B倒着放进int数组，因为有进位，倒着放容易处理
    28.     int cnt1 = 0;
    29.     for (int i=a.size()-1; i>=0; i--)
    30.         A[++cnt1] = a[i] - '0';
    31.  
    32.     int cnt2 = 0;
    33.     for (int i=b.size()-1; i>=0; i--)
    34.         B[++cnt2] = b[i] - '0';
    35.  
    36.     int tot = Add(A, B, C, max(cnt1, cnt2));
    37.  
    38.     //因为A和B是倒着放的，所以C也要倒着输出
    39.     for (int i=tot; i>=1; i--)
    40.         cout << C[i];
    41. }
    42.

    高精度减法

     模拟手算减法

    1. #include
    2. #include
    3. #include
    4. #include
    5. using namespace std;
    6.  string a,b;
    7. bool cmp(vector<int>&A,vector<int>&B)
    8. {
    9.     if(A.size()!=B.size()) return A.size()>B.size();
    10.     
    11.     for(int i=A.size()-1;i>=0;i--)
    12.         if(A[i]!=B[i]) return A[i]>B[i];
    13.     
    14.         
    15.     return true;    //A==B
    16. }
    17.  
    18.  
    19. vector<int> sub(vector<int>&A,vector<int>&B)
    20. {
    21.     vector<int> C;
    22.     for(int i=0,t=0;isize();i++)
    23.     {
    24.         t=A[i]-t;   //借位
    25.         if(isize()) t-=B[i]; //两数相减
    26.         C.push_back((t+10)%10); //如果t>0,入t;如果t<0,入(t+10)%10
    27.         if(t<0) t=1;
    28.         else t=0;
    29.     }
    30.     
    31.     while(C.size()>1 && C.back()==0) C.pop_back();
    32.     return C;
    33. }
    34.  
    35.  
    36. int main()
    37. {
    38.     vector<int> A,B;
    39.    
    40.     cin>>a>>b;
    41.     for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
    42.     for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
    43.     
    44.     vector<int> C;
    45.     
    46.     if(cmp(A,B)) C=sub(A,B);
    47.     else C=sub(B,A),cout<<"-";
    48.     
    49.     for(int i=C.size()-1;i>=0;i--) cout<
    50.     cout<
    51.     
    52.     return 0;
    53. }

    高精度乘法（高精度x低精度）

    1. #include
    2. #include
    3. using namespace std;
    4.  
    5. vector<int> mul(vector<int>& A,int b)
    6. {
    7.     vector<int> C;
    8.     int t=0;
    9.     for(int i=0;isize();i++)
    10.     {
    11.         t+=A[i]*b;
    12.         C.push_back(t%10);
    13.         t/=10;
    14.     }
    15.     
    16.     while(t)
    17.     {
    18.         C.push_back(t%10);
    19.         t/=10;
    20.     }
    21.     while(C.size()>1&&C.back()==0) C.pop_back();
    22.     return C;
    23. }
    24.  
    25. int main()
    26. {
    27.     string a;
    28.     int b;
    29.     cin>>a>>b;
    30.     
    31.     vector<int> A;
    32.     for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
    33.    
    34.     vector<int> C=mul(A,b);
    35.     
    36.     for(int i=C.size()-1;i>=0;i--) cout<
    37.     return 0;
    38. }

    高精度除法

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5.  
    6.  
    7. vector<int> div(vector<int>&A,int b,int&r)
    8. {
    9.     vector<int> C;
    10.     for(int i=A.size()-1;i>=0;i--)
    11.     {
    12.         r=r*10+A[i];
    13.         C.push_back(r/b);
    14.         r%=b;
    15.     }
    16.     reverse(C.begin(),C.end());
    17.     while(C.size()>1&& C.back()==0) C.pop_back();
    18.     return C;
    19. }
    20.  
    21. int main()
    22. {
    23.     string a;
    24.     vector<int> A;
    25.     int B;
    26.     cin>>a>>B;
    27.     for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
    28.     
    29.     int r=0;
    30.     auto C=div(A,B,r);
    31.     
    32.     for(int i=C.size()-1;i>=0;i--) cout<
    33.     cout<
    34.     return 0;
    35. }

    前缀和与差分

    前缀和

    思路：

    给出ai的值时算出前n项和的值

    只需要 s[r]-s[l-1] 即可求出 l 到 r 之间的值

     技巧：

    ios::sync_with_stdio(false);

    作用:提高cin和cout的速度

     副作用：不能使用scanf和printf

    1. #include
    2. using namespace std;
    3. const int N=1e6+10;
    4.  
    5. int n,m;
    6. int a[N],s[N];
    7.  
    8. int main()
    9. {
    10.     ios::sync_with_stdio(false);
    11.     
    12.     cin>>n>>m;
    13.     for(int i=1;i<=n;i++)
    14.     {
    15.         cin>>a[i];
    16.         s[i]=s[i-1]+a[i];
    17.     }
    18.     while(m--)
    19.     {
    20.         int l,r;
    21.         cin>>l>>r;
    22.         cout<-1]<
    23.     }
    24.     return 0;
    25. }

    子矩阵的和

     思路：

    S[i,j]即为所有数的的和为：S[i,j]=S[i,j−1]+S[i−1,j]−S[i−1,j−1]+a[i,j]

     

     (x1,y1),(x2,y2)这一子矩阵中的所有数之和为：S[x2,y2]−S[x1−1,y2]−S[x2,y1−1]+S[x1−1,y1−1]

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5.  
    6. using namespace std;
    7.  
    8. const int N = 1010;
    9.  
    10. int n, m, q;
    11. int a[N][N], s[N][N];
    12.  
    13. int main()
    14. {
    15.     cin>>n>>m>>q;
    16.     for(int i=1;i<=n;i++)
    17.         for(int j=1;j<=m;j++)
    18.         {
    19.             cin>>a[i][j];
    20.             s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
    21.         }
    22.         
    23.     while(q--)
    24.     {
    25.         int x1,x2,y1,y2;
    26.         cin>>x1>>y1>>x2>>y2;
    27.         cout<-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<
    28.     }
    29.     return 0;
    30. }

    差分

     思路：

    首先给定一个原数组a：a[1], a[2], a[3],,,,,, a[n];

    然后我们构造一个数组b ： b[1] ,b[2] , b[3],,,,,, b[i];

    使得 a[i] = b[1] + b[2 ]+ b[3] +,,,,,, + b[i]

    a数组是b数组的前缀和数组，比如对b数组的b[i]的修改，会影响到a数组中从a[i]及往后的每一个数。

    首先让差分b数组中的 b[l] + c ,a数组变成 a[l] + c ,a[l+1] + c,,,,,, a[n] + c;

    然后我们打个补丁，b[r+1] - c, a数组变成 a[r+1] - c,a[r+2] - c,,,,,,,a[n] - c;

    核心操作：对差分数组b做 b[l] + = c, b[r+1] - = c（时间复杂度为O(1) ）

     

     a[i]为b[i]前缀和的实现

    令a[i]=a[i-1]+b[i]; ---> b[i]=a[i]-a[i-1];

    即：

    a[0 ]= 0;

    b[1] = a[1] - a[0];

    b[2] = a[2] - a[1];

    b[3] =a [3] - a[2];

    ........

    b[n] = a[n] - a[n-1];

    1. #include
    2. using namespace std;
    3. const int N = 1e5 + 10;
    4. int a[N], b[N];
    5. int main()
    6. {
    7.     int n, m;
    8.     scanf("%d%d", &n, &m);
    9.     for (int i = 1; i <= n; i++)
    10.     {
    11.         scanf("%d", &a[i]);
    12.         b[i] = a[i] - a[i - 1];      //由前缀和公式，构建差分数组
    13.     }
    14.     int l, r, c;
    15.     while (m--)
    16.     {
    17.         scanf("%d%d%d", &l, &r, &c);
    18.         b[l] += c;     //将序列中[l, r]之间的每个数都加上c
    19.         b[r + 1] -= c;
    20.     }
    21.     for (int i = 1; i <= n; i++)
    22.     {
    23.         a[i] = b[i] + a[i - 1];    //更新a[i],前缀和运算
    24.         printf("%d ", a[i]);
    25.     }
    26.     return 0;
    27. }

    差分矩阵

     思路：

    a[][]数组是b[][]数组的前缀和数组（b[i][j]改变影响a[i][j]之后的所以值），那么b[][]是a[][]的差分数组，我们去构造差分数组： b[i][j]，使得a数组中a[i][j]是b数组左上角(1,1)到右下角(i,j)所包围矩形元素的和

    先看核心操作：在范围(x1,y1)到(x2,y2)的方形数组中加c

    b[x1][y1] + = c;

    b[x1,][y2+1] - = c;

    b[x2+1][y1] - = c;

    b[x2+1][y2+1] + = c;

    在这里插入图片描述

     （假设有b差分数组）

    完成上述操作需要构造差分数组b:

    1.   void insert(int x1,int y1,int x2,int y2,int c)
    2.   {     //对b数组执行插入操作，等价于对a数组中的(x1,y1)到(x2,y2)之间的元素都加上了c
    3.       b[x1][y1]+=c;
    4.       b[x2+1][y1]-=c;
    5.       b[x1][y2+1]-=c;
    6.       b[x2+1][y2+1]+=c;
    7.   }
    8.  
    9.   for(int i=1;i<=n;i++)
    10.   {
    11.       for(int j=1;j<=m;j++)
    12.       {
    13.           insert(i,j,i,j,a[i][j]);    //构建差分数组
    14.       }
    15.   }

    差分这样构建的原因：首先假设a,b都为空数组，也就是全部为0的情况，那么我们也可以说，b数组是a数组的差分数组！因为a[i][j] = b[1][1]+…b[i][j],因为都是0，所有情况满足！在这时a数组其实不为空，我们把a数组中的值看作（0+a[i][j]）那么a数组的值变了，变成了a[i][j],这时如果b数组要想成为a数组的差分数组，值也要变为a[i][j],所以我们把b[i][j]变为a[i][j]，这样就能满足b数组是a数组的差分数组。也就相当于想b数组中插入a[i][j].

    1. #include
    2. #include
    3. using namespace std;
    4. const int N = 1e3 + 10;
    5. int a[N][N], b[N][N];
    6. void insert(int x1, int y1, int x2, int y2, int c)
    7. {
    8.     b[x1][y1] += c;
    9.     b[x2 + 1][y1] -= c;
    10.     b[x1][y2 + 1] -= c;
    11.     b[x2 + 1][y2 + 1] += c;
    12. }
    13. int main()
    14. {
    15.     int n, m, q;
    16.     cin >> n >> m >> q;
    17.     for (int i = 1; i <= n; i++)
    18.         for (int j = 1; j <= m; j++)
    19.             cin >> a[i][j];
    20.     for (int i = 1; i <= n; i++)
    21.     {
    22.         for (int j = 1; j <= m; j++)
    23.         {
    24.             insert(i, j, i, j, a[i][j]);      //构建差分数组
    25.         }
    26.     }
    27.     while (q--)
    28.     {
    29.         int x1, y1, x2, y2, c;
    30.         cin >> x1 >> y1 >> x2 >> y2 >> c;
    31.         insert(x1, y1, x2, y2, c);
    32.     }
    33.     for (int i = 1; i <= n; i++)
    34.     {
    35.         for (int j = 1; j <= m; j++)
    36.         {
    37.             b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];  //二维前缀和
    38.         }
    39.     }
    40.     for (int i = 1; i <= n; i++)
    41.     {
    42.         for (int j = 1; j <= m; j++)
    43.         {
    44.             printf("%d ", b[i][j]);
    45.         }
    46.         printf("\n");
    47.     }
    48.     return 0;
    49. }

  • 相关阅读:
    Docker部署Nginx-常用命令
    Spring Cloud学习（九）【Elasticsearch 分布式搜索引擎01】
    java进程内存分析工具-生成core dump文件，并读取分析：jmap, jhat
    尚硅谷Vue系列教程学习笔记（9）
    systemverilog 过程控制语句
    Multitask Vision-Language Prompt Tuning
    Elasticsearch：不用高深的数学知识来理解 LLMs 是如何工作的
    java计算机毕业设计小说阅读网站源码+系统+数据库+lw文档
    Vue3中的Ref与Reactive：深入理解响应式编程
    one-hot和Embedding
  • 原文地址：https://blog.csdn.net/qq_61386381/article/details/126438172