排序
- 1. 快速排序
- 2. 归并排序
二分
高精度
前缀和与差分
双指针
位运算
- 1. 得到一个数二进制表示的第k位
- 2. lowbit操作(得到一个数二进制表示的最低位的1)
离散化
区间合并

排序

1. 快速排序

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
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) {
        while (q[++i] < x);
        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() {
    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. 归并排序

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

int n;
int q[N], 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, 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 = 0, j = l; i < k; i++, j++) q[j] = tmp[i];
}

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

二分

算法简述

在一个区间 [l, r] 上有两种对立性质，通过二分法可以寻找这两种性质的边界。注意：

有单调性一定可以二分，但可以二分的不一定非得有单调性。
二分一定有解，但对应到具体题目上不一定有解

1. 整数二分

模板

int l = 0, r = n - 1;

while (l < r) {
    int mid = l + r + 1 >> 1;
    if (check1(q[mid])) l = mid; // check1(q[mid]) 表示q[mid]满足性质1
    else r = mid - 1;
}

// 或者

int l = 0, r = n - 1;

while (l < r) {
    int mid = l + r >> 1;
    if (check2(q[mid])) r = mid;
    else l = mid + 1;
}

具体要使用哪个模板要具体问题具体分析，只是要记住当 l = mid; 时， mid = l + r + 1 >> 1。
这是因为当 r = l + 1时，若 mid = l + r >> 1 = l。区间从 [l, r] 变到了 [l, r]，相当于没有变，会一直死循环下去

想象这么一个问题：

给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。如果数组中不存在该元素，则返回 -1 -1。

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int q[N];

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", &q[i]);

    while (m--) {
        int x;
        scanf("%d", &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;
}

2. 浮点二分

#include<iostream>

using namespace std;

double x;

int main() {
    scanf("%lf", &x);

    double l = -10000.0, r = 10000.0;

    while (r - l > 1e-8) {
        double mid = (l + r) / 2;

        if (mid * mid * mid >= x) r = mid;
        else l = mid;
    }

    printf("%lf", l);

    return 0;
}

高精度

算法简述

采用小端存储用数组存下大整数的每一位，模拟四则运算的过程

1. 高精度加法

#include<iostream>
#include<vector>

using namespace std;

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

int main() {
    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');

    auto C = add(A, B);

    for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);

    return 0;
}

2. 高精度减法

#include<iostream>
#include<vector>

using namespace std;

bool cmp(vector<int> A, vector<int> 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;
}

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

int main() {
    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');

    vector<int> C;

    if (cmp(A, B)) C = sub(A, B);
    else {
        cout << '-';
        C = sub(B, A);
    }

    for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);

    return 0;
}

3. 高精度乘法 (高 * 低)

4. 高精度除法 (高 / 低)

前缀和与差分

算法简述

前缀和与差分互为逆运算。其中前缀和主要应用在原数组不发生改变的情况下，频繁查询某一区间的累加和。而差分则主要应用在频繁对原数组的某一区间的所有元素进行增减。

1. 前缀和

引例

想象这么一个问题：

输入一个长度为 n 的整数序列。

接下来再输入 m 个询问，每个询问输入一对 l, r。

对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。

自然而然可以想到如下解法：

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int a[N];

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    while (m--) {
        int l, r;
        scanf("%d %d", &l, &r);
        int sum = 0;

        for (int i = l; i <= r; i++) sum += a[i];

        printf("%d\n", sum);
    }

    return 0;
}

如果询问量较小，耗时也许会比较短，但每次查询的时间复杂度都为O(n)，倘若询问量比较大，程序会进行大量的重复运算。有没有更好更快的方法呢？

答案是有的，我们可以额外创建一个前缀和数组s[N]，其中s[i]表示原数组a[N]前i个元素的和，即 s[i] = a[i] + s[i - 1]

怎么求出数组 a[N] 在区间 [l, r] 上的累加和呢？

虽然生成前缀和数组的时间复杂度仍是O(n)，但每次查询的时间复杂度降到了O(1)，效率大大增加。

源代码

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int a[N], s[N];

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) s[i] = a[i] + s[i - 1];

    while (m--) {
        int l, r;
        scanf("%d %d", &l, &r);
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}

这种思想还可以拓展到二维情形，想象这么一个问题：

输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1, y1, x2, y2, 表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

#include<iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], s[N][N];

int main() {
    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++)
            s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

    while (q--) {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);

        cout << s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] << endl;
    }

    return 0;
}

2. 差分

引例

输入一个长度为 n 的整数序列。

接下来输入 m 个操作，每个操作包含三个整数 l, r, c，表示将序列中 [l, r] 之间的每个数加上 c。

请你输出进行完所有操作后的序列。

暴力解法很容易实现，但同样存在着时间复杂度较高的问题，有没有一种办法可以在常量时间内完成对子序列 [l, r] 中的每个元素进行增减呢？

我们构造一个差分数组 b[N]，使得 b[N] 的前缀和为 a[N]，此时我们称 b[N] 为 a[N] 的差分。怎么构造 b[N] 并不重要，我们先来看看怎么通过差分数组 b[N] 在常数时间内完成对 a[N] 的修改。

明白了 b[i] += c 的含义，我们就可以很轻松的实现对子序列 [l, r] 中的每个元素进行增减的操作了

void insert(int l, int r, int c) {
    b[l] += c;
    b[r + 1] -= c;
}

如何构造差分数组 b[N] 呢？我们可以把 a[N] 看作是一个所有元素都为0的数组，通过修改区间 [i, i] 上的值来得到 a[i]。

源代码

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

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() {
    scanf("%d %d", &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;
        scanf("%d %d %d", &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;
}

这种思想也可以拓展到二维情形，想象这么一个问题：

输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1 ,y1, x2, y2, c，其中 (x1, y1)和 (x2, y2) 表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上 c。

请你将进行完所有操作后的矩阵输出。

#include<iostream>

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() {
    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]);
            insert(i, j, i, j, a[i][j]); // 生成差分数组
        }

    while (q--) {
        int x1, y1, x2, y2, c;
        scanf("%d %d %d %d %d", &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]; // 求b[N]的前缀和
            printf("%d ", b[i][j]);
        }
        cout << endl;
    }

    return 0;
}

双指针

位运算

1. 得到一个数二进制表示的第k位

#include<iostream>

using namespace std;

int main() {
    int x;
    cin >> x;

    for (int i = 31; i >= 0; i--) {
        cout << ((x >> i) & 1);
    }

    return 0;
}

2. lowbit操作(得到一个数二进制表示的最低位的1)

给定一个长度为 n 的数列，请你求出数列中每个数的二进制表示中 1 的个数。

对于一个数x，x & (-x) 操作可以得到其最低位的1

x 与 -x 最低位1高位的数字一定不同，最低位1低位的数字一定都是0 (一堆0取反再加1，正好进位到最低位的1上)，一进行与运算，当然可以得到最低位1

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

int n;
int q[N];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &q[i]);

    for (int i = 0; i < n; i++) {
        int x = q[i];
        int cnt = 0;
        while (x) {
            int tmp = x & (-x);
            x ^= tmp; // 这里换成 "-=" 也是一样的
            cnt++;
        }

        cout << cnt << ' ';
    }

    return 0;
}

离散化

算法简述

把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率

引例

假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。

输入格式
第一行包含两个整数 n 和 m。接下来 n 行，每行包含两个整数 x 和 c。再接下来 m 行，每行包含两个整数 l 和 r。

输出格式
共 m 行，每行输出一个询问中所求的区间内数字和。

数据范围
-1e9 <= x <= 1e9 1 <= n, m <= 1e5 -1e9 <= l <= r <= 1e9 -1e4 <= c <= 1e4

我们来仔细分析一下这道题：
数轴是无限长的 [-1e9, 1e9]，这使得直接创建一个前缀和数组求区间和成为不可能。但我们只进行了至多 1e5 次插入操作以及至多 1e5 次查询操作，使无限长的数轴上有最多 3e5 个位置上有值。如果能将这些有值的位置映射到从1开始的自然数上，就使创建一个前缀和数组成为可能。

IMG_1367(20211015-160127).JPG

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 3e5 + 10;

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

    // 整体右移一格，将a[0]空出来方便求前缀和
    return l + 1;
}

vector<int>::iterator unique(vector<int> &a) {
    int j = 0;
    for (int i = 0; i < a.size(); i ++ )
        if (!i || a[i] != a[i - 1])
            a[j ++ ] = a[i];

    return a.begin() + j;
}

int main() {
    scanf("%d %d", &n, &m);

    for (int i = 0; i < n; i++) {
        int x, c;
        scanf("%d %d", &x, &c);

        add.push_back({x, c});

        alls.push_back(x);
    }

    for (int i = 0; i < m; i++) {
        int l, r;
        scanf("%d %d", &l, &r);

        query.push_back({l, r});

        alls.push_back(l);
        alls.push_back(r);
    }

    // 将alls排序并去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls), 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;
}

区间合并

算法简述

给定一些区间，合并有交集的区间

引例

给定 n 个区间 [li,ri]，要求合并所有有交集的区间。注意如果在端点处相交，也算有交集。输出合并完成后的区间个数。例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。

输入格式
第一行包含整数 n。接下来 n 行，每行包含两个整数 l 和 r。

输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。

数据范围
1 ≤ n ≤ 100000,
-1e9 ≤ li ≤ ri ≤ 1e9

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 10;

int n;

vector<PII> segs;

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 (ed != -2e9) res.push_back({st, ed});

    segs = res;
}

int main() {
    scanf("%d", &n);
    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;
}

算法学习笔记

基础算法

排序

1. 快速排序

2. 归并排序

二分

算法简述

1. 整数二分

模板

2. 浮点二分

高精度

算法简述

1. 高精度加法

2. 高精度减法

3. 高精度乘法 (高 * 低)

4. 高精度除法 (高 / 低)

前缀和与差分

算法简述

1. 前缀和

引例

源代码

2. 差分

引例

源代码

双指针

位运算

1. 得到一个数二进制表示的第k位

2. lowbit操作(得到一个数二进制表示的最低位的1)

离散化

算法简述

引例

输入格式

输出格式

数据范围

区间合并

算法简述

引例

输入格式

输出格式

数据范围