前言

此笔记基于Acwing算法基础课程。

第一章 基础算法

快排

基本思想：

  1. 确定分界点x：可以是左边界，可以是右边界，可以是左右边界的一半，也可随机取一个点为x。
  2. 调整区间：使得x左边的数都小于等于x，x右边的数都大于等于x。
  3. 递归处理左右两段。

代码模板如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static void quickSort(int[] q, int l, int r) {
        if (l >= r) return;
     	//(l+r)>>相当于l+r/2
        int x = q[(l+r)>>1];

        //Define positions of two pointers
        int i = l - 1;
        int j = r + 1;

        while (i < j) {
            do i++; while (q[i] < x);
            do j--; while (q[j] > x);
            //do Swap
            if (i < j) {
                int temp = q[i];
                q[i] = q[j];
                q[j] = temp;
            }
        }

        quickSort(q, l, j);
        quickSort(q, j + 1, r);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
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);
}

归并排序

基本思想：

  1. 确定分界点x：q[l+r/2]。
  2. 递归排序左右。
  3. 归并—-合二为一。

代码模板如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int temp[N];
public static void merge_sort(int[] a,int l, int r)
{
    if (l >= r) return;
    int mid = l+r>>1;
    merge_sort(l, mid), merge_sort(mid+1, r);
    int k = 0, i = l, j = mid+1;
    while (i <= mid && j <= r)
    {
        if (a[i] < a[j]) temp[k ++ ] = a[i ++ ];
        else temp[k ++ ] = a[j ++ ];

    }
    while (i <= mid) temp[k ++ ] = a[i ++ ];
    while (j <= r) temp[k ++ ] = a[j ++ ];
    for (int i = l, j = 0; i <= r; i ++ , j ++ ) a[i] = temp[j];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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];
}

二分查找

二分的本质是边界问题。

整数二分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int lower_bound(int A[], int l, int r, int x)
{
    int mid = l + r >> 1;
    while (l < r)
    {
        if (A[mid] >= x)
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    return l;
}

浮点数二分：

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
}

高精度

高精度应用场景：两个比较大的数（1e6）相加减、一个大的数乘一个比较小的整数、一个大的数除以一个比较小的数。

大整数在C++中是用数组将每一位存进去。

1
2
//若有数为123456789
int a[]={9,8,7,6,5,4,3,2,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
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<vector>
using namespace std;
const int N = 1e6 + 10;

//模板
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;
    vector<int> A,B;
    cin>>a>>b;// a= "123456"
    for(int i =a.size()-1;i>=0;i--){
        A.push_back(a[i]-'0');
    }
    // A=[6,5,4,3,2,1]
    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;
}

减法

一般前提：A>=B

分成两种情况：若A[i]-B[i]-t>=0,返回A[i]-B[i]-t，否则向前面借一位返回A[i]-B[i]+10-t

1
2
3
4
5
6
7
8
9
10
11
12
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;
}

乘法

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>
#include<vector>
using namespace std;
const int N = 1e6 + 10;

//模板
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;
    }
    C.push_back(t);
    while(C.size()>1&&C.back()==0) C.pop_back();
    return C;
}

int main(){
    string a;
    int b;
    vector<int> A;
    cin>>a>>b;// a= "123456"
    for(int i =a.size()-1;i>=0;i--){
        A.push_back(a[i]-'0');
    }
    auto C = mul(A,b);
    for(int i =C.size()-1;i>=0;i--){
        printf("%d",C[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
34
35
36
37
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 1e6 + 10;

//模板A/b 商是C 余数是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;
}

int main(){
    string a;
    int b;
    vector<int> A;
    cin>>a>>b;// a= "123456"
    for(int i =a.size()-1;i>=0;i--){
        A.push_back(a[i]-'0');
    }
    int r;
    auto C = div(A,b,r);
    for(int i =C.size()-1;i>=0;i--){
        printf("%d",C[i]);
    }
    cout<<endl;
    cout<<r<<endl;
    return 0;
}

前缀和与差分

前缀和

假设一个数组为[a1,a2,...,an]，求其前缀和Si=a1+a2+...+ai其中S0=0

如何求Si：S[i]=S[i-1]+a[i]

作用是能快速求出原数组中一段数的和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int N =100010;
int n,m;
int a[N],s[N];
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;
    cout<<s[r]-s[l-1];
}

差分

假设一个数组为[a1,a2,...,an]，构造[b1,b2,...,bn]，使得ai=b1+b2+...+bi,b就称为a的差分，a就是b的前缀和。

应用场景：若想使数组a的[l,r]区间内的所有元素都＋c，只需要在数组b的b[l]+c,b[r+1]-c，这样就可在复杂度为O(1)的条件下完成。

二维差分

给以(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

双指针

核心思想：将时间复杂度为O(n^2)的算法转化为复杂度为O(n)。

常见问题分类：
(1) 对于一个序列，用两个指针维护一段区间
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

1
2
3
4
for(i=0,j=0;i<n;i++){//i是终点j是起点
    //具体逻辑
    while(j<i&&check(i,j)) j++;
}

位运算

常用场景1：求n的二进制表示的第k位数是多少

思想：将n右移k位（n>>k）然后与1进行于操作（n>>k&1）

1
2
//lowbit 返回n的最后一个1. x=1010 返回10
lowbit(n) = n & -n // -n为补码，表示n取反+1（~x+1）

离散化

前提：数组a是有序的，如数组a[ ]中包含的元素有[1,3,100,2000,500000]，将其映射为[0,1,2,3,4]。

可能包含的问题：

  1. 数组a[ ]中可能有重复的元素，需要去重。
  2. 如何算出a[i]离散后的值是多少，二分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
}

区间合并

将n个有交集的区间进行合并，返回合并后的区间个数。

思路：

  1. 按区间左端点进行排序。
  2. 扫描整个区间，将可能有交集的区间进行合并。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 将所有存在交集的区间合并
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;
}