快速排序

  1. 选取基准值（分界值）x，可以是数组的第一个元素，也可以是数组的最后一个元素，中间元素亦可。
  2. 使用双指针 i 和 j 从数组的两端开始扫描，从左端找到一个>=x的值a，从右端找到一个<=x的值b，交换ab的值，交换后i以及i之前的元素都小于等于x，j以及j之后的元素都大于等于x。交换后i应递增，j应递减，继续查找可以交换的值，知道ij相遇甚至错开（i > j）。
  3. 当数组成功划分两部分，左部分小于等于x，右部分大于等于x的时候，左右两部分分别递归调用快速排序。
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
//
// Created by Kahiva on 2024/1/4.
//
#include <iostream>

using namespace std;

const int N = 100010;
int t[N];

void quick_sort(int l, int r){
    if(l >= r) return;
    int i = l - 1, j = r + 1, x = t[(l + r) / 2];

    while(i < j){
        //基准值元素也可以交换，在左区间或者右区间都可以，因此while (t[i] < x);没有等号=。
        //如果是不能交换，即while (t[i] <= x);
        //那么比如6 2 3，基准值为2时。从左边找到了一个比2大的值6，但是从右边找不到比2小的，j--会一直执行，死循环了。
        do i++; while (t[i] < x);
        do j--; while (t[j] > x);
        if(i < j) swap(t[i],t[j]);
    }

    /*在划分区间递归调用快排的时候，i==j或者i>j
     ①当i==j时，举例数组为2 1. l==0，r==1。区间为[0,1]。
        x = t[(l + r) / 2];取值为x=2，相当于取数组首元素为基准值，经过循环后i==j==0。
        正确的分法：划分区间应为[0,0]和[1,1]，即[l, j]和[j + 1, r]，或者将j换成i。
        也就是将相遇处的元素划分给右区间。
        错误的分法：如果划分给左区间，即[l, j - 1]和[j, r]的话，区间为[0,-1]和[0,1]。
        右区间的快排与当前快排区间相同，导致右区间递归与当前相同，陷入死循环。
        若想使得该分法正确，应当x = t[(l + r + 1) / 2]，即取数组尾元素为基准值。
     ②当i>j时。举例，在上一轮while中交换ij元素后，进入下一轮while循环前，
        i == 1, j == 2，进入循环后，i++变成2，j--变成1，此时发生i > j的情况。且<2的元素<=x, >1的元素>=x。
        这种情况下划分区间时，根据①的两种分法，为了保证划分的正确性:
        若取数组首元素为基准值，则应采用j,即[l, j]和[j + 1, r]。
        如果采用[l, i]和[i + 1, r]，右区间为[3, r]很显然缺少了下标2对应的>=x的元素，同理左区间会多一个。
        若取数组尾元素为基准值，则应采用i,即[l, i - 1]和[i, r]。原理同上。

     总结：一整个快速排序中包含很多个小快速排序，可能出现i==j和i>j的情况。因此，为了确保两种情况下都正常运行，分类如下。
     ①x = t[(l + r) / 2];或者说取左端点元素为基准值的情况下，递归区间划分[l, j]和[j + 1, r]。
     ②x = t[(l + r + 1) / 2]；或者说取右端点元素为基准值的情况下，递归区间划分[l, i - 1]和[i, r]。
     */
    quick_sort(l,j);
    quick_sort(j + 1,r);
}

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

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

    quick_sort(0, n - 1);

    for(int i = 0; i < n; i++)
        printf("%d ",t[i]);
    return 0;
}

归并排序

  1. 数组一分为二，递归调用归并排序。
  2. 利用双指针，合并一分为二的数组，将结果存到额外数组 tmp 中。
  3. 合并完成后，将结果数组覆盖至原数组中。
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
//
// Created by Kahiva on 2024/1/16.
//
#include <iostream>

using namespace std;

const int N = 100010;
int t[N], tmp[N];

void merge_sort(int l, int r){
    if(l >= r) return;
    //右移等同除以二
    int mid = l + r >> 1;

    //从数组中间一分为二，各自归并排序
    merge_sort(l, mid), merge_sort(mid + 1, r);

    //k是结果数组的下一个放置元素的位置，ij为数组左右两部分的起始指针
    int k = 0, i = l, j = mid + 1;
    //比较ij指针值的大小，择其小存于结果中
    while(i <= mid && j <= r){
        if(t[i] <= t[j]) tmp[k++] = t[i++];
        else tmp[k++] = t[j++];
    }
    //当某一部分已经全部加入结果后，另一部分的剩余元素直接加入结果
    while(i <= mid) tmp[k++] = t[i++];
    while(j <= r) tmp[k++] = t[j++];

    //用有序的结果覆盖原来无序的数组
    for(int i = l, j = 0; i <= r; i++,j++)
        t[i] = tmp[j];
}

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

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

    merge_sort(0, n - 1);

    for(int i = 0; i < n; i++) printf("%d ", t[i]);

    return 0;
}

归并排序的应用——求解逆序对数量

对于任意给定的数字序列，举例如 4 3 2 1 ，若交换相邻元素，可以减少一个逆序对而不影响这两个元素于其它元素的逆序关系。此处交换 4 , 3 会得到 3 4 2 1 ，可以发现，前半部分元素与后半部分的逆序关系保持不变，前半部分内部消除了一个逆序对。

因此，我们可以考虑将数组一分为二，左右两部分分别消除内部逆序对，得到两个有序的序列，再消除序列之间的逆序对。若有两个有序序列为 2 4 6 和 1 3 5 ，使用双指针分别指向两个序列开头，将序列2的小元素移到大序列的前面，比如1移到2的前面，越过了2 4 6三个元素，那么就减少了三个逆序对。多次操作，直到大序列整体有序。

很显然，上述的操作就是归并排序的一种表现。将数组不断地一分为二，当一组只有两个元素的时候，对这一组一分为二成两个序列，每个序列一个元素，使用双指针归并后，表现为逆序的两个元素交换位置。同样长度为2的毗邻序列各自有序，同样可以使用双指针进行逆序对的消除。

因此，求解逆序对的数量，我们只需要在归并排序中，保存序列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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//
// Created by Kahiva on 2024/1/17.
//
//逆序对的数量
//https://www.acwing.com/problem/content/790/

#include <iostream>

using namespace std;

const int N = 100010;

long long t[N], tmp[N];

long long counts = 0;

void calculate_reverse_pair(int l, int r){
    if(l >= r) return;
    int mid = l + r >> 1;

    calculate_reverse_pair(l, mid), calculate_reverse_pair(mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r){
        if(t[i] <= t[j]) {
            tmp[k++] = t[i++];
        }
        else{
            tmp[k++] = t[j++];
            //将后半部分的小元素移到前半部分时，越过的前半部分元素个数即为逆序对个数
            counts += (mid - i + 1);
        }
    }
    while(i <= mid) tmp[k++] = t[i++];
    while(j <= r) tmp[k++] = t[j++];

    for(int i = l, j = 0; i <= r; i++, j++)
        t[i] = tmp[j];

}

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

    for(int i = 0; i < n; i++) scanf("%lld", &t[i]);

    calculate_reverse_pair(0, n - 1);

    printf("%lld", counts);

    return 0;
}

二分

二分就是寻找一个边界，将整个数组一分为二，一边满足性质，另一边不满足。

整数二分

AcWing—数的范围

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
//
// Created by Kahiva on 2024/1/16.
//

#include <iostream>

using namespace std;

const int N = 100010;
int t[N];


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

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

    while(q--){
        int x;
        scanf("%d", &x);

        int l = 0, r = n - 1;
        while(l < r){
            int mid = l + r >> 1;
            //查找x1位置时，x1以及其后元素都满足>=x这个性质
            //当mid对应元素满足性质时，x1应在mid或者mid前，更新右区间为mid
            if(t[mid] >= x) r = mid;
            //当mid对应元素不满足性质时，x1应在mid后，更新左区间为mid + 1.
            else l = mid + 1;
        }
        if(t[l] != x) printf("-1 -1\n");
        else{
            printf("%d ", l);
            int l = 0, r = n - 1;
            while(l < r){
                //在l == mid == r - 1时，若是t[mid]满足性质，左区间会更新为mid
                //为防止死循环，mid应上取整
                int mid = l + r + 1 >> 1;
                //查找x_last元素位置时，x_last及其前面元素满足<=x的性质
                //当mid对应元素满足该性质时，x_last应在mid或者mid后，更新左区间为mid
                //当mid对应元素不满足时，x_last应在mid前，更新右区间为mid - 1
                if(t[mid] <= x) l = mid;
                else r = mid - 1;
            }
            printf("%d\n", l);
        }
    }

    return 0;
}

浮点数二分

AcWing—三次方根

在求解次方根的问题中，需要注意，当x处于(0,1)的区间内时，其n次方根的结果会大于x。比如0.01的平方根是0.1。因此在使用二分求解n次方根的时候，我们需要将右边界加1。

二分结束的条件设置为一定的精度，比如当结果保留6位小数的时候，我们可以设置精度为1e-8，保留7位则1e-9，以此类推。确保结果的准确性。

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
//
// Created by Kahiva on 2024/1/16.
//

#include <iostream>

using namespace std;

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

    bool aboveZero = true;
    if(x < 0) aboveZero = false, x = 0 - x;

    double l = 0, r = x + 1;

    while(r - l > 1e-8){
        double mid = (l + r) / 2;
        if(mid*mid*mid >= x) r = mid;
        else l = mid;
    }

    printf("%lf", !aboveZero?-l:l);

    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
38
39
//
// Created by Kahiva on 2024/1/18.
//
#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; t != 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 = t >= 10 ? 1 : 0;
    }

    return C;
}

int main(){
    string a, b;
    vector<int> A, B;

    cin >> 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);


    while(C.size() != 0){
        cout << C.back();
        C.pop_back();
    }

    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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//
// Created by Kahiva on 2024/1/18.
//
#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 true;
        if(A[i] < B[i]) return false;
    }

    return true;
}

vector<int> sub(vector<int> &A, vector<int> &B){
    vector<int> C;
    int t = 0;
    for(int i = 0; t != 0 || i < A.size() || i < B.size(); i++){
        //A位减去被借的位
        if(i < A.size()) t = A[i] - t;
        //再减B位
        if(i < B.size()) t -= B[i];
        //若位运算结果为负数，代表需要借位。+10取余为借位后的结果。若不需借位也无妨，+10取余为0。
        C.push_back((t + 10) % 10);
        //保存借位
        t = t < 0 ? 1 : 0;
    }
    //去除最高位前面的0.比如运算结果为003，则去掉00，保留结果为3.
    while(C.size() > 1 && C.back() == 0)
        C.pop_back();
    return C;
}

int main(){
    string a, b;
    vector<int> A, B;

    cin >> 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');

    //将小数-大数转换成-（大数-小数）
    bool a_greater = cmp(A, B);
    auto C = a_greater ? sub(A, B) : sub(B, A);

    //如果是小数-大数，则在结果前面添加负号
    if(!a_greater) printf("-");
    while(C.size() != 0){
        cout << C.back();
        C.pop_back();
    }

    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
38
39
//
// Created by Kahiva on 2024/1/22.
//
#include <iostream>
#include <vector>
using namespace std;

//乘法的实质就是123 * 4 = 100 * 4 + 20 * 4 + 3 * 4.结果的个位诞生于最低位乘以4，十位诞生于十位乘以4加上个位进的位
//以此类推。
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;
    }
    if(t) C.push_back(t);

    while(C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

int main(){
    string a;
    int b;
    cin >> a >> b;

    vector<int> A;
    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
38
39
40
41
42
43
44
45
46
47
48
49
//
// Created by Kahiva on 2024/1/22.
//
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


vector<int> div(vector<int> A, int b){
    vector<int> C;
    int t = 0;

    //从大数高位开始除
    for(int i = A.size() - 1; i >= 0; i--){
        t = t * 10 + A[i];
        //能除就除
        if(t >= b) C.push_back(t / b), t = t % b;
        //不能除，商就置零
        else C.push_back(0);
    }

    //翻转数组，并去除高位0。
    reverse(C.begin(), C.end());
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    //翻转回来，把最终的余数补在数组最后面
    reverse(C.begin(), C.end());
    C.push_back(t);

    return C;
}

int main(){
    string a;
    int b;
    vector<int> A;

    cin >> a >> b;

    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');

    auto C = div(A, b);

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

    printf("\n%d", C.back());

    return 0;
}

前缀与差分

前缀和（一维）

对于一个普通的一维数组（从 a1 = a[1] 开始，a[0] = 0），前n项和称为前缀和。通过Sn - S(k-1)可以得到S[k,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
//
// Created by Kahiva on 2024/1/23.
//
#include <iostream>
using namespace std;

const int N = 100010;
int a[N], s[N];

int main(){
    int n, m;
    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;
}

子矩阵的和

796. 子矩阵的和 - AcWing题库

要求解一个矩阵的子矩阵的元素和，只需要想象一个矩阵，切割成十字形，按需拼凑即可。

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
//
// Created by Kahiva on 2024/1/23.
//
#include <iostream>

using namespace std;

const int N = 1010;
int a[N][N], s[N][N];

int main(){
    //n行m列，q个询问
    int n, m, q;
    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]);

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            /*
             *  a11 a12 | a13
             *  a21 a22 | a23
             *  --------|----
             *  a31 a32 | a33
             * 比如s[3][3] = s[3][2] + s[2][3] - s[2][2]（这是去除重复加的部分）+ a[3][3]
             * */
            s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];

    while(q--){
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        /*
         *  a11 a12 a13 | a14 a15
         *  a21 a22 a23 | a24 a25
         *  ------------|--------
         *  a31 a32 a33 | a34 a35
         *  a41 a42 a43 | a44 a45
         * s[[3][4], [4][5]] = s[4][5] - s[4][3] - s[2][5] + s[2][3]（补回多减的重叠部分）
         * 实际上，这里的s[[3][4], [4][5]]整体类似于上一个注释位置中的a[3][3]，都是被夹的一部分，只是包含数据个数不同的区别。
         * */
        printf("%d\n", s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);
    }

    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
38
39
40
41
42
43
44
//
// Created by Kahiva on 2024/1/25.
//
#include <iostream>

using namespace std;

const int N = 100010;
//a数组为前缀和数组，b为差分数组
int a[N], b[N];

void insert(int l, int r, int c){
    //对于前缀和数组a而言，要使[l, r]的前缀和+c
    //只需使差分数组b的第l位元素+c，这会让l及其以后的前缀和+c
    //然后第r+1位元素-c，这会让r+1及其以后的前缀和-c，即[r + 1, ?]的前缀和保持不变。
    b[l] += c;
    b[r + 1] -= c;
}

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

    //初始时，将a和b都看作全为零的的数组，前缀和和差分都为0。
    //然后输入数组a。
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

    //将输入的数组a看作待添加的元素c，即区间[i,i]上的元素都加上常数c（a[i]）。
    for(int i = 1; i <= n; i++) insert(i, i, a[i]);

    //同样的执行m次insert即可。
    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;
}

二维差分

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
//
// Created by Kahiva on 2024/1/27.
//
#include <iostream>

using namespace std;

const int N = 1010;
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(){
    int n, m, q;
    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]);

    //初始化差分数组
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; 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++)
            a[i][j] = a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1] + b[i][j];

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++)
            printf("%d ", a[i][j]);
        printf("\n");
    }


    return 0;
}