AcWing基础算法的收获复盘

排序算法

AcWing 的排序算法包括了快速排序和归并排序，核心思路都是双指针+递归。

快速排序

原理

  • 两个指针分别从左右端点出发，与列表中某一随机的数比较大小，直到某一边不满足了便交换两指针指向的元素，再将操作对象改为另一指针。
  • 目的：使该数左边全是小于等于它的数，右边全是大于等于它的数。
  • 递归这一操作，当每一个数都满足这一特性时，排序也就完成了。
  • return 的条件是左边界大于等于右边界

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int q[N], n;

void quick_sort(int q[], int l, int r) {
    if(l >= r) return;
    int x = q[(l + r) / 2], i = l - 1, j = 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() {
    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;
}

归并排序

原理

  • 先随机取一个数（一般是中间值）作为分界拆分数组，并递归，这样整个数组就被不断的对半分，直到最小单元。
  • 两个指针分别指向分成的两个部分，从两个部分各自的第一个元素开始，比较两数大小，并将小的数存放到新的数组中。
  • 难点：如何处理这个临时的数组。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>

using namespace std;

const int N = 1e6 + 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(int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}

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

解释

  • 如果两个指针都没有超过各自的边界，进行循环。
  • 巧妙运用 tmp[k++] = q[i++] 这种写法，让 i, j, k 累加
  • 如果不是对半分，就会出现某一段数组比另一段更长，这时候直接全部放进去，因为肯定满足这一段数组剩下的数都大于另一段数组最大的数（递归过后每一段正在处理的数组都是排好序的）。
  • tmp 数组每次都是从 0 开始，但每一次递归的左右边界不同，所以最后将 tmp 存回的时候 q 数组是从右边界开始，tmp 从 0 开始。

二分算法

原理

  • 条件：一组具有左右边界且排好序的数据。
  • 先确定一个需要满足的条件，例如模板中的 q[mid] >= x。
  • 如果满足该条件，说明 x 在该数的左边。将右边界重置为 mid。
  • 该模板分为两种情况，如果满足条件时需要重置左边界，则 mid = l + r + 1 >> 1，需要 +1，避免出现边界问题；重置右边界时 mid = l + r >> 1 即可。

代码

重置右边界

1
2
3
4
5
6
int l = 0, r = n - 1;
while(l < r) {
    int mid = l + r >> 1;
    if(q[mid] >= x) r = mid;
    else l = mid + 1;
}

重置左边界

1
2
3
4
5
6
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;
}

高精度算法

在我的博客 高精度算法 中有详细介绍。

差分和前缀和

前缀和

用途

  • 最典型的是计算区间和，本质是运用数列的前 n 项和的知识，对每一项的前 n 项和都预先存储，后续直接调用可以大幅减少计算时间。

原理

  • 需要先插入原数组来初始化前 n 项和的数组，使用 s[i] = s[i - 1] + a[i]。
  • 当计算区间 [l, r] 的所有数据和时使用 s[r] - s[l - 1]。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>

using namespace std;

const int N = 100010;

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] = s[i - 1] + a[i]; // 前缀和的初始化

    while (m -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]); // 区间和的计算
    }

    return 0;
}

差分

原理

  • 差分其实就是前缀和的逆运算，可以通过操作区间中的单一元素达到操作前缀和的效果
  • 构造差分数组的过程完美体现了逆运算的特性，最终的答案需要通过前缀和还原。
1
2
3
4
5
6
7
--常规初始化过程--
// 构造差分数组 d
vector<int> d(n+1);
d[0] = a[0];
for (int i = 1; i < n; i++) {
    d[i] = a[i] - a[i-1];
}

示例题目

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

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

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

输入格式

第一行包含两个整数 n 和 m。

第二行包含 n 个整数，表示整数序列。

接下来 m 行，每行包含三个整数 l, r, c，表示一个操作。

输出格式

共一行，包含 n 个整数，表示最终序列。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>

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

解释

  • 本题初始化的过程就是将区间 [i, i] 中的数加上 a[i]，这样达到的效果是将 b[i] 变为 a[i] - s[i - 1]（假设 s[] 为前缀和数组）。
  • 将序列中 [l,r] 之间的每个数加上 c，只需要操作右边界，为了避免后面的无关元素被影响，需要把右边界的后一个数减去 c。
  • 前缀和还原
1
for (int i = 1; i <= n; i ++ ) b[i] += b[i - 1];

差分与前缀和对比总结

特性 差分 前缀和
核心功能 高效区间修改 高效区间查询
数学关系 前缀和的逆运算 差分的逆运算
预处理 构造差分数组 d 构造前缀和数组 s
操作复杂度 修改 O(1)，重建数组 O(n) 查询 O(1)，预处理 O(n)
依赖关系 修改后需前缀和重建数组 独立完成查询

关键理解

  • 差分通过记录相邻元素的差值，将区间修改转化为端点操作。
  • 前缀和通过累积和，将区间求和转化为端点差值。
  • 二者通过互逆运算紧密联系，共同解决数组的区间操作问题。

位运算

lowbit

  • 用途：只保留二进制数从最后一个 1 开始到结尾的所有数。

原理

  • 公式：x & -x;
  • 这里涉及到原码、反码和补码的知识。
  • C++ 中没有减法运算，因此使用 y + (-x) 达到 y - x 的效果。
  • -x = 反码(x) + 1。

例子

  • x = (12)₁₀ = (00000000000000000000000000001100)₂

  • -x =(−12)₁₀ = (11111111111111111111111111110100)₂

  • x & (-x) = (00000000000000000000000000000100)₂

离散化

原理

  • 一组数量非常多的数据，但是只操作其中分散的少部分数据，对于这些非常分散的数据我们可以将它们一一映射到方便操作的数上。
  • 在进行离散化前，我们需要先把这组数排序+去重，在 C++ 中可使用以下方法：
1
2
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());

例题

假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。

现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。

接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l, r] 之间的所有数的和。

输入格式

第一行包含两个整数 n 和 m。

接下来 n 行，每行包含两个整数 x 和 c。

再接下来 m 行，每行包含两个整数 l 和 r。

输出格式

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

数据范围

−109 ≤ x ≤ 109,
1 ≤ n, m ≤ 105,
−109 ≤ l ≤ r ≤ 109,
−10000 ≤ c ≤ 10000

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 300010;

typedef pair<int, int> PII;

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
4
for (auto item : add) {
    int x = find(item.first);
    a[x] += item.second;
}

将 a 数组的下标映射为要操作的数，查询时就可直接调用 a 数组的那个下标。

双指针算法

  • 这个其实只是一个思想，通过两个指针之间的配合优化时间复杂度。

例题

给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

输入格式

第一行包含整数 n。

第二行包含 n 个整数（均在 0 ~ 105 范围内），表示整数序列。

输出格式

共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。

数据范围

1 ≤ n ≤ 105

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
using namespace std;

const int N = 1e5 + 10;

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

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

    int res = 0;

    for (int i = 0, j = 0; i < n; i++) {
        s[a[i]]++;
        while (s[a[i]] > 1) {
            s[a[j]]--;
            j++;
        }
        res = max(res, i - j + 1);
    }

    cout << res << endl;

    return 0;
}
  • 这里其实也用到了映射的思想，就是将 a[i] 映射为 s 的下标。

区间合并

  • 这个看看题目理解一下，不是很复杂的思想。

例题

格式比较难打，直接看 AcWing 的 803. 区间合并。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

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

    segs = res;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }

    merge(segs);

    cout << segs.size() << endl;

    return 0;
}

C++ 中的 pair 类模板

  • 在此之前我还没有用过 pair，如果需要存储两个数据的时候使用 pair 会比较方便。

常用方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//通过 typedef 定义 pair<int, int> 为 PII，更方便。
typedef pair<int, int> PII;

//定义，一般使用 vector 数组。
vector<PII> segs;

//输入
int l, r;
cin >> l >> r;
segs.push_back({l, r});

//每次循环中，seg 会被初始化为 segs 容器中的一个元素的副本
for (auto seg : segs) {
    //调用的时候使用 seg.first 和 seg.second
    st = seg.first, ed = seg.second;
}

总结

  • 至此算法基础课中的 基础算法 部分就完成了，很久没碰算法捡起来真的是很有意思，但是学习也很费时间，基本上比较佛系的学一周也就只能学这么些内容。
  • 下一章就是数据结构，学完之后就可以开始刷 leetcode 了，到时候再更新数据结构的内容和一些力扣题解。
Algorithms
AcWing基础算法的收获复盘
http://www.cactily.me/2025/07/11/AcWing基础算法的收获复盘/
Author
Cactus
Posted on
July 11, 2025
Licensed under