Acwing算法基础课：基本算法

快速排序

步骤：

1. 随机取一元素“pivot”
2. 划分区间
3. 递归对左右区间进行快速排序

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) {
            int t=q[i];
            q[i]=q[j];
            q[j]=t;
        }
    }
    quick_sort(q, l, j);
    quick_sort(q, j+1, r);
}

上面写法中（递归区间：[l, j] [j+1, r]），x只能取q[l]或q[(l+r)/2]，取q[r]或q[(l+r+1)/2]会导致死循环。示例数据：

1 2

性质：每次划分后，两个区间的元素被“固定”在该区间中。即左区间中元素排序完后仍在该区间中，右区间同理。

变形：第k小数

#include <iostream>

using namespace std;

int a[100000+5];

int kth_min(int q[], int l, int r, int k){
    if (l>=r) return q[l];
    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]);
    }
    if (j>=k) return kth_min(q, l, j, k);
    else return kth_min(q, j+1, r, k);
}

int main(){
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i=1; i<=n; i++)
        scanf("%d", &a[i]);
    printf("%d\n", kth_min(a, 1, n, k));
}

归并排序

步骤：

1. 递归分别对左、右区间归并排序
2. 归并操作（“双指针算法”）

void merge_sort(int q[], int l, int r){
    if (l>=r) return;
    int mid = (l+r)/2;
    merge_sort(q, l, mid);
    merge_sort(q, mid+1, r);
    int i=l, j=mid+1, k=0;
    while (i<=mid && j<=r){
        if(q[i]<=q[j]) t[k++]=q[i++];
        else t[k++]=q[j++];
    }
    while (i<=mid)
        t[k++]=q[i++];
    while (j<=r)
        t[k++]=q[j++];
    for(i=0, j=l; i<k; i++, j++)
        q[j]=t[i];
}

变形：求逆序对数量

逆序对数 = 左区间逆序对数 + 右区间逆序对数 + 两数分别位于左、右区间的逆序对数

其中，分别位于左、右区间的逆序对数可在归并的过程中被统计。

二分

整数二分

在一整数区间上定义一性质，将区间划分为两部分，一部分满足性质，另一部分不满足。

寻找满足/不满足性质的边界：左边/右边

// 二分，找左边区间边界（左边符合性质）
int bisearch_l(int l, int r){
    while (l<r) {
        int mid = (l+r+1)/2;
        if (check(mid)) l=mid;
        else r=mid-1;
    }
    return l;
}

// 二分，找右边区间边界（右边符合性质）
int bisearch_r(int l, int r){
    while (l<r) {
        int mid = (l+r)/2;
        if (check(mid)) r=mid;
        else l=mid+1;
    }
    return l;
}

应用

• “数的范围”：求某个数在有序数列中起始、终止下标
• 离散化中 find() 求离散化后的下标

浮点数二分

eps 比边界精确度再精确两位小数即可。

高精度

A、B代表高精度数，b代表低精度数（int）

高精度数的表示

使用vector<int>存储，每个int存一位十进制数；先存低位，再存高位（方便进位时扩展位数）。

A+B

由低位到高位依次迭代，维护一进位t

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(1);
    return c;
}

A-B

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;
    int t=0;
    for (int i=0; i<a.size(); i++) {
        t = a[i] - t;
        if (i < b.size()) t -= b[i];
        c.push_back((t+10)%10);
        t = t<0 ? 1 : 0;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

A*b

维护一”进位”t

vector<int> mul(vector<int> a, int b) {
    vector<int> c;
    int t=0;
    for (int i=0; i<a.size(); i++) {
        t += a[i] * b;
        c.push_back(t%10);
        t /= 10;
    }
    while (t) {
        c.push_back(t%10);
        t /= 10;
    }
    while (c.size()>1 && c.back()==0) c.pop_back();
    return c;
}

A/b

从高位到低位开始迭代，维护一”余数”r

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

前缀和与差分

前缀和

应用：快速求一段区间（区域）和（O(1)）

预处理：s[i]=s[i-1]+a[i]

求[l,r]区间和：sum=s[r]-s[l-1]

二维前缀和

预处理：依次迭代

求和：容斥原理

差分

假设存在一数列，原数列是该数列的前缀和。

应用：快速对一段区间（区域）加一个数（O(1)）

假设差分数列 $b[i]$：

\[b[i]+c \iff a[i, +∞]+c\]

故 $a[l, r]+c \iff b[l]+c, b[r+1]-c $

无需构造，构造过程可视为依次更新[i, i]区间。

二维差分

类似于一维差分，假设一矩阵的前缀和是原矩阵。假设差分矩阵 $b[i][j]$ ：

\[b[i][j] + c \iff b[i, +∞][j, +∞]\]

无需构造。

双指针算法

广义的使用两个指针的算法

• 快速排序划分
• 归并排序归并
• 其他例题
  • 求最长不重复连续子串
  • “数组元素目标和”

一般思考步骤：

1. 尝试写暴力
2. 尝试利用指针移动方向的单调性优化

位运算

• 求某一二进制位：(x >> k) & 1

• lowbit(x) = x & (-x)：求最低权重（$2^k$）

  • 应用：求二进制“1”的个数、树状数组？

离散化

将范围较大的数（较稀疏）映射到小范围数的集合。

映射 $ f: X\rightarrow Y$ 其中 $X\subset Z, Y={1, 2, 3, …}$，且映射有保序性:

$ \forall x, y \in X, x \lt y \Rightarrow f(x) \lt f(y) $​

步骤：

1. 对集合 $X$​ 排序、去重
2. 实现find()函数，二分查找离散化后的下标（函数 $f$​）

vector<int> alls;

int find(int x) {
    int l=0, r=alls.size()-1;
    while (l<r) {
        int mid = (l+r)/2;
        if (alls[mid]>=x) r=mid;
        else l=mid+1;
    }
    return l+1;
}

sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());

区间合并

步骤：

1. 按区间左端点排序（升序）
2. 维护一个区间的左右端点，枚举排序好的区间
   1. 左端点 <= 维护的右端点：合并
   2. 否则，新区间