AcWing 基础算法章节笔记

基础算法这一章的关键，不是把题一题一题硬背下来，而是把“题型 -> 模板 -> 复杂度”这条线打通。

本章核心模板

快速排序

1
2
3
4
5
6
7
8
9
10
11
void quick_sort(vector<int>& q, int l, int r) {
    if (l >= r) return;
    int x = q[(l + r) >> 1], 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);
}

归并排序与逆序对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
long long merge_sort(vector<int>& q, int l, int r) {
    if (l >= r) return 0;
    int mid = (l + r) >> 1;
    long long res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
    vector<int> tmp;
    int i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (q[i] <= q[j]) tmp.push_back(q[i++]);
        else {
            res += mid - i + 1;
            tmp.push_back(q[j++]);
        }
    }
    while (i <= mid) tmp.push_back(q[i++]);
    while (j <= r) tmp.push_back(q[j++]);
    for (int k = l, t = 0; k <= r; k++, t++) q[k] = tmp[t];
    return res;
}

整数二分

1
2
3
4
5
6
7
8
9
int bsearch_left(vector<int>& a, int x) {
    int l = 0, r = (int)a.size() - 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return a[l] == x ? l : -1;
}

浮点二分

1
2
3
4
5
6
7
8
9
double cubic_root(double n) {
    double l = -100, r = 100;
    while (r - l > 1e-8) {
        double mid = (l + r) / 2;
        if (mid * mid * mid >= n) r = mid;
        else l = mid;
    }
    return l;
}

高精度加减乘除

1
2
3
4
5
6
7
8
9
10
11
vector<int> add(vector<int>& A, vector<int>& B) {
    vector<int> C;
    int t = 0;
    for (int i = 0; i < (int)A.size() || i < (int)B.size() || t; i++) {
        if (i < (int)A.size()) t += A[i];
        if (i < (int)B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    return C;
}

前缀和与差分

1
2
3
4
5
6
7
8
// 1-indexed
for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
int query(int l, int r) { return s[r] - s[l - 1]; }

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

双指针

1
2
3
4
5
6
int res = 0;
for (int i = 0, j = 0; i < n; i++) {
    cnt[a[i]]++;
    while (cnt[a[i]] > 1) cnt[a[j++]]--;
    res = max(res, i - j + 1);
}

离散化与区间合并

1
2
3
4
5
6
7
8
9
10
11
12
13
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());

sort(segs.begin(), segs.end());
vector<pair<int,int>> res;
int st = -2e9, ed = -2e9;
for (auto [l, r] : segs) {
    if (ed < l) {
        if (st != -2e9) res.push_back({st, ed});
        st = l, ed = r;
    } else ed = max(ed, r);
}
if (st != -2e9) res.push_back({st, ed});

本章题目与题解要点

快速排序

  • 785 快速排序：典型分治排序。核心是选基准后把小于等于和大于等于基准的元素分到两边。
  • 786 第k个数：本质是快速选择。只递归包含第 k 小元素的那一半，平均复杂度 O(n)。

归并排序

  • 787 归并排序：先分后治，最后线性归并。适合稳定排序和后续区间统计。
  • 788 逆序对的数量：归并时如果右边元素先出队，就说明左边当前及后续元素都和它构成逆序对。

二分

  • 789 数的范围：分别做左边界二分和右边界二分，找第一次出现和最后一次出现的位置。
  • 790 数的三次方根：浮点二分模板题，关键是精度控制和区间初值。

高精度

前缀和与差分

  • 795 前缀和：区间和问题的标准入门题，核心公式是 s[r] - s[l - 1]。
  • 796 子矩阵的和：二维前缀和，矩形求和用容斥。
  • 797 差分：区间加法转成差分数组单点修改，最后再还原。
  • 798 差分矩阵：二维差分，对四个角做修改，最后二维前缀还原。

双指针算法

位运算

离散化

  • 802 区间和：值域很大但操作点少，先收集坐标离散化，再做前缀和。

区间合并

  • 803 区间合并：按左端点排序后线性扫描，维护当前合并段的右端点。

这一章怎么复习

  1. 先把二分、前缀和、差分、双指针四类模板手写一遍。
  2. 再做一遍 789、795、797、799 这四题，确认自己能独立写。
  3. 最后回头看 802 和 803，把“离散化”和“排序后扫描”的套路补齐。

返回导航