acwing算法基础课学习笔记（第一章：基础算法）

小鱼儿 2023-09-28 18:18 30阅读 0赞

#### 第一章：基础算法 ####

*  前言
 *  一、快速排序
 *   *  1. 快速排序算法模板
     *  2. 快速排序模板题（1）：快速排序
     *  3.快速排序算法模板题（2）：第k个数
 *  二、归并排序
 *   *  1. 归并排序算法模板
     *  2. 归并排序模板题（1）：归并排序
     *  3. 归并排序模板题（2）：逆序对的数量
 *  三、二分
 *   *  1. 整数二分算法模板
     *  2. 整数二分算法模板题：数的范围
     *  3. 浮点数二分算法模板
     *  4. 浮点数二分算法模板题： 数的三次方根
 *  四、高精度
 *   *  1. 高精度加法模板
     *  2. 高精度减法模板
     *  3. 高精度乘低精度模板
     *  4. 高精度除以低精度算法
 *  五、前缀和与差分
 *   *  1. 一维前缀和模板
     *  2. 二维前缀和模板
     *  3. 一维差分模板
     *  4. 二维差分模板
 *  六、双指针
 *   *  1. 双指针算法模板
     *  2. 双指针算法模板题（1）：最长连续不重复子序列
     *  3. 双指针算法模板题（2）：数组元素的目标和
     *  4. 双指针算法模板题（3）：判断子序列
 *  七、位运算
 *   *  1. 位运算算法模板
     *  2. 位运算模板题：二进制中1的个数
 *  八、离散化
 *   *  1. 离散化算法模板
     *  2. 离散化算法模板题：区间和
 *  九、区间合并
 *   *  1. 区间合并模板
     *  2. 区间合并模板题：区间合并

## 前言 ##

所有的模板题都可以在acwing题库中搜到。

## 一、快速排序 ##

\*\* 思路：基于分治思想\*\*

1.  确定分界点（随机取任意一个数为分界点，一般取中点）；
2.  调整区间，把小于`x`的数移到左边，把大于`x`的数移到右边，把区间分为`[l, j]`、`[j + 1, r]`；
3.  递归左右。

### 1. 快速排序算法模板 ###

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

### 2. 快速排序模板题（1）：快速排序 ###

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int N = 100010;
    
    int q[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()
    {
        int n;
        cin >> n;
    
        for(int i = 0; i < n; i ++) cin >> q[i];
    
        quick_sort(q, 0, n - 1);
    
        for(int i = 0; i < n; i ++ ) printf("%d ", q[i]);
    
        return 0;
    }

### 3.快速排序算法模板题（2）：第k个数 ###

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int N = 100010;
    
    int q[N];
    
    int quick_sort(int q[], int l, int r, int k)
    {
        if(l >= r) return q[l];
    
        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]);
        }
    
        if(j - l + 1 >= k) return quick_sort(q, l, j , k);
        else return quick_sort(q, j + 1, r, k - (j - l + 1));
    }
    
    int main()
    {
        int n, k;
        cin >> n >> k;
    
        for(int i = 0; i < n; i ++ ) cin >> q[i];
    
        cout << quick_sort(q, 0, n - 1, k) << endl;
    
        return 0;
    }

## 二、归并排序 ##

**思路：**

1.  取数组的中间数作为分界点；
2.  将分界点左右两边分别排好序；
3.  将左右两边进行合并。

### 1. 归并排序算法模板 ###

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

### 2. 归并排序模板题（1）：归并排序 ###

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int N = 100010;
    
    int q[N], tmp[N];
    
    void memset_sort(int q[], int l, int r)
    {
        if(l >= r) return;
    
        int mid = l + r >> 1;
        memset_sort(q, l, mid), memset_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(int i = l, j = 0; i <= r; i ++ , j ++ ) q[i] = tmp[j];
    }
    
    int main()
    {
        int n;
        cin >> n;
    
        for(int i = 0; i < n; i ++ ) cin >> q[i];
    
        memset_sort(q, 0, n - 1);
    
        for(int i = 0; i < n; i ++ ) printf("%d ", q[i]);
    
        return 0;
    }

### 3. 归并排序模板题（2）：逆序对的数量 ###

#include <bits/stdc++.h>
    
    using namespace std;
    
    typedef long long LL;
    
    const int N = 100010;
    
    int q[N], tmp[N];
    
    LL memset_sort(int q[], int l, int r)
    {
        if(l >= r) return 0;
    
        int mid = l + r >> 1;
        LL res = memset_sort(q, l, mid) + memset_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
            {
                res += mid - i + 1;
                tmp[k ++ ] = q[j ++];
            }
        while(i <= mid) tmp[k ++ ] = q[i ++];
        while(j <= r) tmp[k ++ ]= q[j ++];
    
        for(int i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
    
        return res;
    }
    
    int main()
    {
        int n;
        cin >> n;
    
        for(int i = 0; i < n; i ++) cin >> q[i];
    
        cout << memset_sort(q, 0, n - 1) << endl;
    
        return 0;
    }

## 三、二分 ##

**思路：**  
本质：可以划分为满足某种性质与不满足某种性质的两个区间，用二分法可以找到两区间边界的左右两个点。

### 1. 整数二分算法模板 ###

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

### 2. 整数二分算法模板题：数的范围 ###

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int N = 100010;
    
    int n, m;
    int q[N];
    
    int main()
    {
        cin >> n >> m;
        for(int i = 0; i < n; i ++ ) cin >> q[i];
    
        while(m -- )
        {
            int x;
            cin >> x;
    
            int l = 0, r = n - 1;
            while(l < r)
            {
                int mid = l + r >> 1;
                if(q[mid] >= x) r = mid;
                else l = mid + 1;
            }
    
            if(q[l] != x) cout << "-1 -1" << endl;
            else
            {
                cout << l << ' ';
    
                int l = 0, r = n - 1;
                while(l < r)
                {
                    int mid = l + r + 1 >> 1;
                    if(q[mid] <= x) l = mid;
                    else r = mid - 1;
                }
                cout << l << endl;
            }
        }
        return 0;
    }

### 3. 浮点数二分算法模板 ###

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

### 4. 浮点数二分算法模板题： 数的三次方根 ###

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
        double x;
        cin >> x;
    
        double l = -100, r = 100;
        while(r - l > 1e-8)
        {
            double mid = (l + r) / 2;
            if(mid * mid * mid >= x) r = mid;
            else l = mid;
        }
        printf("%.6lf\n", l);
        return 0;
    }

## 四、高精度 ##

### 1. 高精度加法模板 ###

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

### 2. 高精度减法模板 ###

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

### 3. 高精度乘低精度模板 ###

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

### 4. 高精度除以低精度算法 ###

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

## 五、前缀和与差分 ##

### 1. 一维前缀和模板 ###

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

**一维前缀和模板题：前缀和**

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int N = 100010;
    
    int n, m;
    int a[N], s[N];
    
    int main()
    {
        cin >> n >> m;
        for(int i = 1; i <= n; i ++ ) cin >> a[i];
    
        for(int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];
    
        while(m -- )
        {
            int l, r;
            cin >> l >> r;
            printf("%d\n", s[r] - s[l - 1]);
        }
        return 0;
    }

### 2. 二维前缀和模板 ###

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 <bits/stdc++.h>
    
    using namespace std;
    
    const int N = 1010;
    
    int n, m, q;
    int s[N][N];
    
    int main()
    {
        cin >> n >> m >> q;
    
        for(int i = 1; i <= n; i ++ )
            for(int j  = 1; j <= m; j ++ )
                cin >> s[i][j];
    
        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];
    
        while(q -- )
        {
           int x1, y1, x2, y2;
           cin >> 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;
    }

### 3. 一维差分模板 ###

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

**一维差分模板题：差分**

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int N = 100010;
    
    int n, m;
    int a[N], b[N];
    
    void insert(int l, int r, int c)
    {
        b[l] += c;
        b[r + 1] -= c;
    }
    
    int main()
    {
        cin >> n >> m;
        for(int i = 1; i <= n; i ++ ) cin >> 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 ++ ) printf("%d ", b[i]);
    
        return 0;
    }

### 4. 二维差分模板 ###

给以(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 <bits/stdc++.h>
    
    using namespace std;
    
    const int N = 1010;
    
    int n, m, q;
    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()
    {
        cin >> n >> m >> q;
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= m; j ++ )
                cin >> 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 ++ ) printf("%d ", b[i][j]);
            puts("");
        }
        return 0;
    }

## 六、双指针 ##

**常见问题分类：**

1.  对于一个序列，用两个指针维护一段区间
2.  对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

### 1. 双指针算法模板 ###

for (int i = 0, j = 0; i < n; i ++ )
    {
        while (j < i && check(i, j)) j ++ ;
    
        // 具体问题的逻辑
    }

### 2. 双指针算法模板题（1）：最长连续不重复子序列 ###

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int N = 100010;
    
    int n;
    int q[N], s[N];
    
    int main()
    {
        cin >> n;
        for(int i = 0; i < n; i ++ ) cin >> q[i];
    
        int res = 0;
        for(int i = 0, j = 0; i < n; i ++ )
        {
            s[q[i]] ++;
            while(j < i && s[q[i]] > 1) s[q[j ++ ]] --;
            res = max(res, i - j + 1);
        }
        cout << res << endl;
        return 0;
    }

### 3. 双指针算法模板题（2）：数组元素的目标和 ###

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int N = 1e5 + 10;
    
    int n, m, x;
    int a[N], b[N];
    
    int main()
    {
        cin >> n >> m >> x;
        for(int i = 0; i < n; i ++ ) cin >> a[i];
        for(int i = 0; i < m; i ++ ) cin >> b[i];
    
        for(int i = 0, j = m - 1; i < n; i ++ )
        {
            while(j >= 0 && a[i] + b[j] > x) j --;
            if(j >= 0 && a[i] + b[j] == x) cout << i << ' ' << j << endl;
        }
        return 0;
    }

### 4. 双指针算法模板题（3）：判断子序列 ###

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int N = 1e5 + 10;
    
    int n, m;
    int a[N], b[N];
    
    int main()
    {
        cin >> n >> m;
        for(int i = 0; i < n; i ++ ) cin >> a[i];
        for(int i = 0; i < m; i ++ ) cin >> b[i];
    
        int i = 0, j = 0;
        while(i < n && j < m)
        {
            if(a[i] == b[j]) i ++;
            j ++;
        }
        if(i == n) puts("Yes");
        else puts("No");
    
        return 0;
    }

## 七、位运算 ##

### 1. 位运算算法模板 ###

求n的第k位数字: n >> k & 1
    返回n的最后一位1：lowbit(n) = n & -n，如101000得1000

### 2. 位运算模板题：二进制中1的个数 ###

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
        int n;
        cin >> n;
    
        while(n -- )
        {
            int x, s = 0;
            cin >> x;
    
            for(int i = x; i; i -= i & -i) s ++;
            printf("%d ", s);
        }
        return 0;
    }

## 八、离散化 ##

\*\*场景：\*\*目标数据稀疏的分散在大数组空间中，大部分元素为0。  
**思路：**

1.  首先取操作涉及的下标，即将要存数字的下标与求和范围两端的下标，存入小数组q中;
2.  对数组q排序;
3.  重新创建一个大小与q相同的数组s，从数组q中找到对应大数组要存入数据的位置映射，在s相同位置存入数据（q中找映射可以用二分法）;
4.  找大数组求和范围两端点在q中的映射位置，在数组s对应映射位置求和即可，可用前缀和.

### 1. 离散化算法模板 ###

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
    }

### 2. 离散化算法模板题：区间和 ###

#include <iostream>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    const int N = 300010;
    
    int n, m;
    int a[N], s[N];
    
    vector<int> alls;
    vector<PII> add, query;
    
    int find(int 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;
    }
    
    int main()
    {
       cin >> n >> m;
       for (int i = 0; i < n; i ++ )
       {
           int x, c;
           cin >> x >> c;
           add.push_back({x, c});
    
           alls.push_back(x);
       }
    
       for (int i = 0; i < m; i ++ )
       {
           int l, r;
           cin >> l >> r;
           query.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());
    
       // 处理插入
       for (auto item : add)
       {
           int x = find(item.first);
           a[x] += item.second;
       }
    
       // 预处理前缀和
       for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i];
    
       // 处理询问
       for (auto item : query)
       {
           int l = find(item.first), r = find(item.second);
           cout << s[r] - s[l - 1] << endl;
       }
    
       return 0;
    }

## 九、区间合并 ##

\*\*场景：\*\*离散的区间，合并相交的区间  
**思路：**

1.  按区间的左端点排序；
2.  从左到右扫描，维护一个当前区间（随着遍历，若相交则区间变长）
3.  每次遍历的区间和当前区间有三种情况分类讨论：  
    （1）右端点小于当前区间右端点，当前区间不变；  
    （2）右端点大于当前区间右端点，当前区间变长；  
    （3）左端点大于当前区间右端点，将该区间置为当前区间；

### 1. 区间合并模板 ###

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

### 2. 区间合并模板题：区间合并 ###

#include <iostream>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    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;
    }
    
    int main()
    {
        int n;
        scanf("%d", &n);
    
        vector<PII> segs;
        for (int i = 0; i < n; i ++ )
        {
            int l, r;
            scanf("%d%d", &l, &r);
            segs.push_back({l, r});
        }
    
        merge(segs);
    
        cout << segs.size() << endl;
    
        return 0;
    }

**内容持续更新中,关注博主不迷路。**