AcWing 算法基础课题单练习（一）

1. 基础算法

1.1 排序

1.1.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
#include<iostream>
#include<vector>

using namespace std;

const int N = 1e5+7;

void quickSort(vector<int>& nums, int l, int r) {
    if(l >= r) {
        return;
    }
    // 随机选择一个数作为基准
    int x = nums[rand()%(r-l+1)+l];
    int i=l-1, j=r+1;
    while(i<j) {
        // 满足条件就继续向后扫描
        do i++; while(nums[i] < x);  
        do j--; while(nums[j] > x);
        // 交换元素
        if(i < j) {
            // 中途停止，说明 nums[i] >= x && nums[j] <= x
            swap(nums[i], nums[j]);
        }
    }
    // 递归处理左右两个子区间
    quickSort(nums, l, j);
    quickSort(nums, j+1, r);
    return;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n, 0);
    for(int i=0; i<n; i++) {
        cin >> nums[i];
    }
    // 开始排序
    quickSort(nums, 0, n-1);
    // 输出排序后的结果
    for(int i=0; i<n; i++) {
        cout << nums[i] << " ";
    }
    return 0;
}

1.1.2 归并排序

归并排序 是一种基于分治思想的排序算法，其基本思想是将待排序的记录分割成若干个有序的子序列，然后把这些子序列合并成一个有序序列。这个处理的过程是 自下而上 的，因为每次合并两个有序的子序列，所以需要先处理子序列。

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
#include<iostream>
#include<vector>

using namespace std;

const int N = 1e5+7;
int tmp[N];

void mergeSort(vector<int>& nums, int l, int r) {
    if(l >= r) {
        return;
    }
    int mid = l+r>>1;
    // 先处理左右两个子区间
    mergeSort(nums, l, mid);
    mergeSort(nums, mid+1, r);
    // 开始合并两个有序的区间
    int k=0, i=l, j=mid+1;
    while(i<=mid && j<=r) {
        if(nums[i] <= nums[j]) {
            tmp[k++] = nums[i++];
        } else {
            tmp[k++] = nums[j++];
        }
    }
    // 将剩余的元素加入tmp
    while(i<=mid) tmp[k++] = nums[i++];
    while(j<=r) tmp[k++] = nums[j++];
    // 将tmp中的元素覆盖到nums中
    for(int p=l; p<=r; p++) {
        nums[p] = tmp[p-l];
    }
    return;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n, 0);
    for(int i=0; i<n; i++) {
        cin >> nums[i];
    }
    // 开始排序
    mergeSort(nums, 0, n-1);
    // 输出排序后的结果
    for(int i=0; i<n; i++) {
        cout << nums[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
#include<iostream>
#include<vector>

using namespace std;

const int N = 1e5 + 7;
int tmp[N]; 

void mergeSort(vector<int>& nums, int l, int r) {
	if(l >= r) {
		return;
	} 
	int mid = l+r>>1;
	// 分别处理左右两边
	mergeSort(nums, l, mid);
	mergeSort(nums, mid+1, r);
	int k=0, i=l, j=mid+1;
	while(i<=mid && j<=r) {
		// i扫描左半边的元素，j扫描右半边的元素
		if(nums[i] <= nums[j]) {
			// 记录较小的元素
			tmp[k++] = nums[i++]; 
		} else {
			tmp[k++] = nums[j++];
		}
	} 
	// 将剩余满足条件的元素加入tmp
	while(i<=mid) tmp[k++] = nums[i++];  // 先加入左边的较小元素
	while(j<=r) tmp[k++] = nums[j++];
	// tmp中存储着排好序的元素，将其覆盖在nums上
	for(int p=l; p<=r; p++) {
		nums[p] = tmp[p-l];
	}   
	return;
}

int main() {
	// 找出数组中逆序对的数量
	int n;
	cin >> n;
	vector<int> nums(n, 0);
	for(int i=0; i<n; i++) {
		cin >> nums[i];
	}
	// 开始计算
	mergeSort(nums, 0, n-1);
	for(int i=0; i<n; i++) {
		cout << nums[i] << " ";
	}
	return 0;
}

1.2 二分

1.2.1 数的范围（整数二分）

题目描述： 给定一个按照升序排列的长度为 n 的整数数组 nums 和若干个查询 queries。对于每个查询 i，请你计算 nums 中i值范围的起止下标。

输入格式： 第一行包含整数 n 和 m ，表示数组长度和查询个数。第二行包含 n 个整数，表示完整排序的数组 nums 。接下来 m 行，每行包含一个整数，表示一个查询。

输出格式： 对于每个查询，输出一个答案，包含两个整数，表示 nums 中元素值范围的起止下标。如果数组中存在重复元素，则输出满足条件的下标中 最小 的。如果不存在这样的下标，则输出 -1 -1。

输入样例：

1
2
3
4
5
6 3
1 2 2 3 4 5
1
4
6

输出样例：

1
2
3
0 0
3 3
-1 -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
#include<iostream>
#include<vector>

using namespace std;

const int N = 1e5 + 7;

int main() {
    int n, m; 
    cin >> n >> m;
    vector<int> nums(n, 0);
    for(int i=0; i<n; i++) {
        cin >> nums[i];
    } 
    // 开始处理每一个查询
    for(int i=0; i<m; i++) {
        int x;
        cin >> x;
        // 查找x的左边界
        // 循环结束时 l=r，指向第一个大于等于x的位置
        int l=0, r=n-1;
        while(l < r) {
            int mid = l+(r-l)/2;
            if(nums[mid] >= x) {
                r = mid;
            } else {
                l = mid+1;
            }
        }
        // 查找x的右边界
        // 循环结束时 L=R，指向第一个大于x的位置
        int L=0, R=n-1;
        while(L < R) {
            int mid = L+(R-L+1)/2;
            if(nums[mid] <= x) {
                L = mid;
            } else {
                R = mid-1;
            }
        }
        // 输出结果
        if(nums[l] != x) {
            cout << "-1 -1" << endl;
        } else {
            cout << l << " " << R << endl;
        }
    }
    return 0;
}

1.2.2 数的三次方根（浮点数二分）

题目描述： 给定一个浮点数 n ，求它的三次方根。

输入格式： 共一行，包含一个浮点数 n 。

输出格式： 共一行，包含一个浮点数，表示 n 的三次方根。答案需要保留 6 位小数。

数据范围： −10000≤n≤10000-10000≤n≤10000

输入样例：

1
-1000.00

输出样例：

1
-10.000000

解题思路：

浮点数二分的思路和整数二分类似，也是每次将查找范围缩小一半，直到找到目标值为止。对于浮点数二分，我们需要确定查找范围的上下界，然后每次将查找范围缩小一半，直到找到目标值为止。

浮点数二分和整数二分最大的区别在于 不需要考虑卡死问题，所以不需要设置 l=mid+1 和 r=mid-1，而是直接将查找范围缩小一半即可。

代码实现

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

using namespace std;

int main() {
    double n; 
    cin >> n;
    // y = x^3 函数单调递增，所以可以使用二分查找
    double l=-10000, r=10000;
    while(r-l > 1e-7) {
        double mid = l + (r-l)/2;
        if(mid*mid*mid >= n) {
            r = mid;
        } else {
            l = mid+1;
        }
    }
    printf("%.6lf", l);
    return 0;
}

1.3 高精度

1.3.1 高精度加法

题目描述： 给定两个正整数 a，b，计算 a+b 的结果。

输入格式： 输入包含两行，第一行包含一个正整数 a，第二行包含一个正整数 b 。数据保证 a 和 b 不超过 10000 位。

输出格式： 输出一个结果，表示 a+b 的结果。

输入样例：

1
2
12
23

输出样例：

1
35

解题思路：

对于高精度加法，我们需要将两个大数拆分成单个数字进行相加，然后将结果存储在一个数组中。具体步骤如下：

  1. 将两个大数拆分成单个数字，存储在两个数组中。
  2. 从个位开始，依次相加，将结果存储在一个新的数组中。
  3. 如果相加的结果大于等于10，则需要进位。
  4. 最后将结果数组中的数字输出。

代码实现

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>

using namespace std;

int main() {
    string A, B;
    cin >> A >> B;
    const int N = max(A.size(), B.size()) + 1;

    vector<int> a(N, 0), b(N, 0), c(N, 0);
    // 首先将大数转为数组
    int index = 0;
    for(int i=A.size()-1; i>=0; i--) {
        a[index++] = A[i] - '0';
    }
    index = 0;
    for(int i=B.size()-1; i>=0; i--) {
        b[index++] = B[i] - '0';
    }
    // 开始计算
    bool carry = false;  // 是否需要进位
    for(int i=0; i<N; i++) {
        c[i] += a[i] + b[i];
        if(carry) {
            c[i] += 1;
        }
        if(c[i] >= 10) {
            carry = true;
            c[i] -= 10;
        } else {
            carry = false;
        }
    }
    // 输出结果
    int k=N-1;
    while(c[k] == 0) k--;
    for(int i=k; i>=0; i--) {
        cout << c[i];
    }
    return 0;
}

1.3.2 高精度减法

题目描述： 给定两个正整数 a，b，计算 a−b 的结果。

输入格式： 输入包含两行，第一行包含一个正整数 a，第二行包含一个正整数 b 。数据保证 a 和 b 不超过 10000 位，计算结果可能为负值。

输出格式： 输出一个结果，表示 a−b 的结果。

输入样例：

1
2
12
23

输出样例：

1
-11

解题思路：

具体操作和高精度加法类似，只是需要注意以下几点：

  1. 需要判断两个大数的大小关系，如果被减数小于减数，则需要将结果取反。
  2. 在计算过程中，如果被减数的某一位小于减数的对应位，则需要借位。

代码实现

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
#include<iostream>
#include<vector>

using namespace std;

int main() {
    // 接收数据
    string A, B;
    cin >> A >> B;
    // 判断两个数的大小关系
    if(A < B) {
        cout << "-";
        swap(A, B);  // 保证 A > B
    }
    // 将字符串转为数组
    const int N = max(A.size(), B.size()) + 1;
    vector<int> a(N, 0), b(N, 0), c(N, 0);
    int index = 0;
    for(int i=A.size()-1; i>=0; i--) {
        a[index++] = A[i] - '0';
    }
    index = 0;
    for(int i=B.size()-1; i>=0; i--) {
        b[index++] = B[i] - '0';
    }
    // 开始计算
    bool borrow = false;  // 是否需要借位
    for(int i=0; i<N; i++) {
        c[i] += a[i] - b[i];
        if(borrow) {
            c[i] -= 1; // 上一位借位了
        }
        // 判断是否需要借位
        if(c[i] < 0) {
            borrow = true;
        } else {
            borrow = false;
        }
    }
    // 输出结果
    int k = N-1;
    while(c[k] == 0) k--;
    for(int i=k; i>=0; i--) {
        cout << c[i];
    }
    return 0;
}

1.3.3 高精度乘法

题目描述： 给定两个非负整数 a，b，计算 a×b 的结果。

数据范围： 1<=a的长度<=105,0<=b的长度<=100001<=a的长度<=10^{5}, 0<=b的长度<=10000

输入格式： 输入包含两行，第一行包含一个整数 a，第二行包含一个整数 b。

输出格式： 输出一个结果，表示 a×b 的结果。

输入样例：

1
2
12
23

输出样例：

1
276

解题思路：

高精度乘法和高精度加法类似，只是需要将两个大数拆分成单个数字进行相乘，然后将结果存储在一个数组中。具体步骤如下：

  1. 将两个大数拆分成单个数字，存储在两个数组中。
  2. 从个位开始，依次相乘，将结果存储在一个新的数组中。
  3. 如果相乘的结果大于等于10，则需要进位。
  4. 最后将结果数组中的数字输出。

代码实现

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
#include<iostream>
#include<vector>

using namespace std;

int main() {
    string A, B;
    cin >> A >> B;
    const int N = 10^7 + 7;
    vector<int> a(N, 0), b(N, 0), c(N, 0);
    int index = 0;
    for(int i=A.size()-1; i>=0; i--) {
        a[index++] = A[i] - '0';
    }
    index = 0;
    for(int i=B.size()-1; i>=0; i--) {
        b[index++] = B[i] - '0';
    }
    // 开始计算
    for(int i=0; i<A.size(); i++) {
        for(int j=0; j<B.size(); j++) {
            c[i+j] += a[i] * b[j];
        }
    }   
    // 处理进位
    for(int i=0; i<N; i++) {
        if(c[i] >= 10) {
            // 乘法进位可能不止加1
            c[i+1] += c[i] / 10;
            c[i] %= 10;
        }
    }
    // 输出结果
    int k = N-1;
    while(c[k] == 0) k--;
    for(int i=k; i>=0; i--) {
        cout << c[i];
    }
    return 0;
}

1.3.4 高精度除法

题目描述： 给定两个非负整数 a，b，计算 a÷b 的结果。

数据范围： 1<=a的长度<=105,0<=b的长度<=104,b不为01<=a的长度<=10^5, 0<=b的长度<=10^4, b 不为 0

输入格式： 输入包含两行，第一行包含一个整数 a，第二行包含一个整数 b。

输出格式： 共两行，第一行输出一个结果，表示 a÷b 的结果。第二行输出余数。

输入样例：

1
2
12
23

输出样例：

1
0

解题思路：

高精度除法和高精度加法类似，只是需要将两个大数拆分成单个数字进行相除，然后将结果存储在一个数组中。具体步骤如下：

  1. 将两个大数拆分成单个数字，存储在两个数组中。
  2. 从个位开始，依次相除，将结果存储在一个新的数组中。
  3. 如果相除的结果大于等于10，则需要进位。
  4. 最后将结果数组中的数字输出。

代码实现

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;

int main() {
    string A, B;
    cin >> A >> B;
    const int N = max(A.size(), B.size()) + 1;
    vector<int> a(N, 0), b(N, 0), c(N, 0);
    int index = 0;
    for(int i=A.size()-1; i>=0; i--) {
        a[index++] = A[i] - '0';
    }
    index = 0;
    for(int i=B.size()-1; i>=0; i--) {
        b[index++] = B[i] - '0';
    }
    // 开始计算除法
    for(int i=A.size()-1; i>=0; i--) {
        c[i] = a[i];
        for(int j=B.size()-1; j>=0; j--) {
            c[i-j] += c[i] / b[j];
            c[i] %= b[j];
        }
    }
    // 输出结果
    int k = N-1;
    while(c[k] == 0) k--;
    for(int i=k; i>=0; i--) {
        cout << c[i];
    }
}

1.4 前缀和与差分

1.4.1 一维前缀和

题目描述： 给定一个长度为 n 的整数序列，接下来再输入m个询问，每对询问包含两个整数 l 和 r，表示一个区间，请你对于每个询问输出该区间内数字和。

输入格式： 第一行包含两个整数 n 和 m，表示序列的长度和询问的个数。第二行包含 n 个整数，表示整数序列。接下来 m 行，每行包含两个整数 l 和 r，表示一个询问的区间范围。

输出格式： 输出 m 行，每行输出一个询问的结果。

输入样例：

1
2
3
4
5
5 3
1 3 5 2 4
1 2
2 4
3 5

输出样例：

1
2
3
4
11
9

解题思路：

前缀和是一种预处理技术，可以在 O(n) 的时间复杂度内计算出任意区间的和。具体步骤如下：

  1. 首先计算前缀和数组，前缀和数组的第 i 个元素表示从序列的第 1 个元素到第 i 个元素的和。
  2. 对于每个询问，只需要计算区间 [l, r] 的和，即前缀和数组中第 r 个元素减去第 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
#include<iostream>
#include<vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n+1, 0); // 前缀和数组
    for(int i=1; i<=n; i++) {
        cin >> a[i];
    }
    // 计算前缀和
    for(int i=1; i<=n; i++) {
        a[i] += a[i-1];
    }
    // 处理每个询问
    for(int i=0; i<m; i++) {
        int l, r;
        cin >> l >> r;
        cout << a[r] - a[l-1] << endl;
    }
    return 0;
}

1.4.2 二维前缀和

题目描述： 给定一个 n 行 m 列的矩阵，再输入 q 个询问，每个询问包含四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2，表示一个子矩阵的左上角坐标 (x1,y1)(x_1,y_1) 和右下角坐标 (x2,y2)(x_2,y_2)，请你输出每个子矩阵的元素和。

输入格式： 第一行包含三个整数 n，m，q，分别表示矩阵的行数、列数和询问的个数。接下来 n 行，每行包含 m 个整数，表示矩阵中的元素。接下来 q 行，每行包含四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2，表示一个询问的子矩阵的左上角坐标和右下角坐标。

输出格式： 输出 q 行，每行输出一个询问的结果。

输入样例：

1
2
3
4
5
6
7
8
3 4 3
1 2 3 4
5
6 7 8 9
10 11 12 13
1 1 2 2
1 2 2 3
1 1 3 4

输出样例：

1
2
3
16
25
84

解题思路：

二维前缀和是一种预处理技术，可以在 O(n2)O(n^2) 的时间复杂度内计算出任意子矩阵的和。具体步骤如下：

  1. 首先计算前缀和数组，前缀和数组的第 i 行第 j 列的元素表示从矩阵的第 1 行第 1 列到第 i 行第 j 列的元素和。
  2. 对于每个询问，只需要计算子矩阵的和，即前缀和数组中第 x2x_2 行第 y2y_2 列的元素减去第 x1−1x_1-1 行第 y2y_2 列的元素减去第 x2x_2 行第 y1−1y_1-1 列的元素加上第 x1−1x_1-1 行第 y1−1y_1-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
#include<iostream>
#include<vector>

using namespace std;

int main() {
    int n, m, q;
    cin >> n >> m >> q; // 矩阵的行数、列数和询问的个数
    vector<vector<int>> a(n+1, vector<int>(m+1, 0)); // 前缀和数组
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            cin >> a[i][j];
        }
    }
    // 计算前缀和
    for(int i=1; i<n; i++) {
        for(int j=1; j<=m; j++) {
            a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];
        }
    }
    // 处理每个询问
    for(int i=0; i<q; i++) {
        int x1, y1, x2, y2; // 子矩阵的左上角坐标和右下角坐标
        cin >> x1 >> y1 >> x2 >> y2;
        cout << a[x2][y2] - a[x1-1][y2] - a[x2][y1-1] + a[x1-1][y1-1] << endl;
    }
    return 0;
}

1.4.3 一维差分

题目描述： 给定一个长度为 n 的整数序列，接下来再输入 m 个操作，每个操作包含三个整数 l、r 和 c，表示将序列中区间 [l,r] 的每个数加上 c。
请你输出完成所有操作后的序列。

输入格式： 第一行包含两个整数 n 和 m，表示序列的长度和操作的总数。第二行包含 n 个整数，表示整数序列。接下来 m 行，每行包含三个整数 l、r 和 c，表示一个操作。

输出格式： 输出完成所有操作后的序列。

输入样例：

1
2
3
4
5
5 3
1 2 2 1 2
1 2 1
2 4 2
3 5 1

输出样例：

1
4 3 4 3 5

解题思路：

一维差分是一种预处理技术，可以在 O(n) 的时间复杂度内对区间进行加减操作。具体步骤如下：

  1. 首先计算差分数组，差分数组的第 i 个元素表示序列中第 i 个元素与第 i-1 个元素的差。
  2. 对于每个操作，只需要在差分数组中第 l 个元素加上 c，在差分数组中第 r+1 个元素减去 c。这样就可以保证区间 [l, r] 的每个元素都加上 c。
  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
#include<iostream>
#include<vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> d(n+2, 0); 
    for(int i=1; i<=n; i++) {
        cin >> d[i];
    }
    // 计算差分数组
    for(int i=1; i<=n; i++) {
        d[i] -= d[i-1];
    }
    // 处理每个操作
    for(int i=0; i<m; i++) {
        int l, r, c;
        cin >> l >> r >> c;
        d[l] += c;
        d[r+1] -= c;
    } 
    // 输出结果
    for(int i=1; i<=n; i++) {
        cout << d[i] + d[i-1] << " ";
    }
    return 0;
}

1.4.4 二维差分

题目描述： 给定一个 n 行 m 列的矩阵，再输入 q 个操作，每个操作包含四个整数 x1、y1、x2、y2 和 c，表示将矩阵中子矩阵 (x1,y1,x2,y2)(x_1,y_1,x_2,y_2) 的所有元素都加上 c。

请你输出完成所有操作后的矩阵。

输入格式： 第一行包含两个整数 n 和 m，表示矩阵的行数和列数。第二行包含一个整数 q，表示操作的总数。接下来 q 行，每行包含五个整数 x1、y1、x2、y2 和 c，表示一个操作。

输出格式： 输出完成所有操作后的矩阵。

输入样例：

1
2
3
4
3 3 3
1 2 2 3 2
1 1 2 2 1
2 2 3 3 2

输出样例：

1
2
3
3 3 3
4 3 4
3 2 3

解题思路：

二维差分是一种预处理技术，可以在 O(n2)O(n^2) 的时间复杂度内对子矩阵进行加减操作。具体步骤如下：

  1. 首先计算差分数组，差分数组的第 i 行第 j 列的元素表示矩阵中第 i 行第 j 列的元素与第 i-1 行第 j 列的元素的差。
  2. 对于每个操作，只需要在差分数组中第 x1 行第 y1 列的元素加上 c，在差分数组中第 x2+1 行第 y1 列的元素减去 c，在差分数组中第 x1 行第 y2+1 列的元素减去 c，在差分数组中第 x2+1 行第 y2+1 列的元素加上 c。这样就可以保证子矩阵 (x1,y1,x2,y2)(x_1,y_1,x_2,y_2) 的所有元素都加上 c。
  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
#include<iostream>
#include<vector>

using namespace std;

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> a(n+2, vector<int>(m+2, 0));
    // 接收输入
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            cin >> a[i][j];
        }
    }
    // 计算差分数组
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            // 本质上是前缀和的逆操作
            a[i][j] -= a[i-1][j] + a[i][j-1] - a[i-1][j-1];
        }
    }
    // 处理每个操作
    for(int i=0; i<q; i++) {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        a[x1][y1] += c;
        a[x2+1][y1] -= c;
        a[x1][y2+1] -= c;
        a[x2+1][y2+1] += c;
    }
    // 计算前缀和
    for(int i=1; i<=n i++) {
        for(int j=1; j<=m; j++) {
            a[i][j] += a[i-1][j] + a[i][j-1] -a[i-1][j-1];
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

1.5 双指针

1.5.1 最长连续不重复子序列

题目描述： 给定一个长度为 n 的整数序列，请找出最长的不包含重复数字的连续子序列，输出它的长度。

输入格式： 第一行包含一个整数 n。第二行包含 n 个整数，表示整数序列。

输出格式： 输出一个整数，表示最长的不包含重复数字的连续子序列的长度。

输入样例：

1
2
5
1 3 5 7 9

输出样例：

1
5

解题思路：

双指针是一种常见的算法技巧，可以在 O(n) 的时间复杂度内解决问题。具体步骤如下：

  1. 定义两个指针 l 和 r，分别表示子序列的左端点和右端点。
  2. 使用一个哈希表来记录当前子序列中每个数字出现的次数，初始时，哈希表为空。
  3. 当 r 指针向右移动时，将当前数字加入哈希表中，如果当前数字在哈希表中已经存在，则将 l 指针向右移动，直到当前数字在哈希表中不存在为止。
  4. 每次移动 r 指针时，更新最长子序列的长度。

代码实现

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>
#include<unordered_map>

using namespace std;

int main() {
    int n; 
    cin >> n; 
    vector<int> nums(n);
    for(int i=0; i<n; i++) {
        cin >> nums[i];
    }
    unordered_map<int, int> exist;  // 记录数字是否出现过
    int l = 0, r = 0, ans = 0;
    // 当前区间为 [l, r]，左闭右开
    while(r < n) {
        if(exist[nums[r]] == 0) {
            // 新数字
            exist[nums[r]] = 1;
            r++;
        } else {
            // 重复数字
            while(exist[nums[r]] > 0) {
                exist[nums[l]] = 0;  // 实际上是减一，但是原数值一定是1，所以可以这么写
                l++;
            }
        }
        ans = max(ans, r-l);
    }
    cout << ans << endl;
    return 0;
}

1.5.2 数组元素的目标和

题目描述： 给定两个升序排序的整数数组 nums1 和 nums2，以及一个整数 target，请你找出 nums1 和 nums2 中和为 target 的数对 (num1,num2)，解只有一个。

输入格式： 第一行包含三个整数 n、m 和 target。第二行包含 n 个整数，表示数组 nums1。第三行包含 m 个整数，表示数组 nums2。

输出格式： 共一行，包含两个整数，表示和为 target 的数对 (num1,num2)。

输入样例：

1
2
3
4 5 6
1 2 4 7
3 4 6 8 9

输出样例：

1
4 2

解题思路：

双指针是一种常见的算法技巧，可以在 O(n) 的时间复杂度内解决问题。具体步骤如下：

  1. 定义两个指针 l 和 r，分别指向 nums1 的左端点和 nums2 的右端点。
  2. 当 l 和 r 指针指向的元素之和大于 target 时，将 r 指针向左移动，直到 l 和 r 指针指向的元素之和小于等于 target。
  3. 当 l 和 r 指针指向的元素之和小于 target 时，将 l 指针向右移动，直到 l 和 r 指针指向的元素之和大于等于 target。
  4. 当 l 和 r 指针指向的元素之和等于 target 时，输出结果并结束程序。

代码实现

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>
#include<vector>

using namespace std;

int main() {
    int n, m, t;
    cin >> n >> m >> t;
    vector<int> nums1(n), nums2(m);
    for(int i=0; i<n; i++) {
        cin >> nums1[i];
    }
    for(int i=0; i<m; i++) {
        cin >> nums2[i];
    }
    int l = 0, r = m - 1;
    while(l < n && r >= 0) {
        if(nums1[l] + nums2[r] == t) {
            cout << nums1[l] << " " << nums2[r] << endl;
            return 0;
        } else if(nums1[l] + nums2[r] > t) {
            r--;
        } else {
            l++;
        }
    }
    return 0;
}

1.5.3 判断子序列

题目描述： 给定一个长度为 n 的整数序列 a1,a2,…,an 和一个长度为 m 的整数序列 b1,b2,…,bm，请你判断 a 序列是否为 b 序列的子序列。

输入格式： 第一行包含两个整数 n 和 m，分别表示序列 a 的长度和序列 b 的长度。第二行包含 n 个整数，表示序列 a。第三行包含 m 个整数，表示序列 b。

输出格式： 输出一个整数，如果 a 序列是 b 序列的子序列，则输出 1，否则输出 0。

输入样例：

1
2
3
3 5
1 3 5
1 2 3 4 5

输出样例：

1
1

解题思路：

双指针是一种常见的算法技巧，可以在 O(n) 的时间复杂度内解决问题。具体步骤如下：

  1. 定义两个指针 i 和 j，分别指向序列 a 和序列 b 的左端点。
  2. 当 i 和 j 指针指向的元素相等时，将 i 和 j 指针向右移动，直到 i 指针指向序列 a 的末尾。此时，a 序列是 b 序列的子序列。如果 j 指针指向 b 序列的末尾时 i 指针还没有指向 a 序列的末尾，则 a 序列不是 b 序列的子序列。
  3. 当 i 和 j 指针指向的元素不相等时，将 j 指针向右移动，直到 i 和 j 指针指向的元素相等。

代码实现

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
#include<iostream>
#include<vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int>  a(n), b(m);
    for(int i=0; i<n; i++) {
        cin >> a[i];
    }
    for(int i=0; i<m; i++) {
        cin >> b[i];
    }
    int i = 0, j = 0;
    while(i < n && j < m) {
        if(a[i] == b[j]) {
            i++;
            j++;
            if(i == n) {
                cout << 1 << endl;
                return 0;
            }
        } else {
            j++;
        }
    }
    cout << 0 << endl;
    return 0;
}

1.6 位运算

1.6.1 二进制中1的个数

题目描述： 输入一个长度为 n 的数组，输出这个数组中每个数二进制表示中 1 的个数。

输入格式： 第一行包含一个整数 n。第二行包含 n 个整数，表示数组中的元素。

输出格式： 共一行，包含 n 个整数，表示数组中每个数二进制表示中 1 的个数。

输入样例：

1
2
5
1 2 3 4 5

输出样例：

1
1 1 2 1 2

解题思路：

位运算是一种常见的算法技巧，可以在 O(n) 的时间复杂度内解决问题。具体步骤如下：

  1. 定义一个变量 count，用于记录当前数字二进制表示中 1 的个数。初始时，count 为 0。
  2. 当数字不为 0 时，将数字与 1 进行按位与运算，如果结果为 1，则将 count 加 1。然后将数字右移一位，继续进行按位与运算，直到数字为 0。
  3. 输出 count。

代码实现

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

using namespace std;

int main() {
    int n;
    cin >> n;
    for(int i=0; i<n; i++) {
        int x;
        cin >> x;
        int count = 0;
        // 位掩码遍历，避免处理负数右移的时候补1的问题
        for(int j=0; j<32; j++) {
            if(x & (1 << j)) {
                count++;
            }
        }
        cout << count << " ";
    }
    return 0;
}

1.7 离散化

1.7.1 区间和

题目描述： 给定一个无限长的数轴，数轴上每一点都是 0。现在，我们首先进行 n 次操作，每次操作将某一点的数 x 增加 c。接下来进行 m 次询问，每次询问一个区间 [l,r] 中所有数的和。

输入格式： 第一行包含两个整数 n 和 m。接下来 n 行，每行包含两个整数 x 和 c，表示一次操作。接下来 m 行，每行包含两个整数 l 和 r，表示一次询问。

输出格式： 共 m 行，每行包含一个整数，表示询问的答案。

输入样例：

1
2
3
4
5
6
3 2
1 2
3 4
5 6
1 3
2 6

输出样例：

1
2
2
12

解题思路：

离散化是一种常见的算法技巧，可以省略不必要的空间开支。具体步骤如下：

  1. 定义一个数组 a，用于存储所有操作的点的下标和值。初始时，a 为空。
  2. 对于每次操作，将操作点的下标和值添加到数组 a 中。
  3. 对数组 a 进行排序，并去重。
  4. 对每一组区间查询，利用二分法找到区间的左端点和右端点在数组 a 中的位置，然后计算区间和。

代码实现

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>

using namespace std;

int findL(vector<pair<int, int>>& a, int t) {
    // 找到第一个大于等于t的数的下标
    int l = 0, r = a.size()-1;
    while(l < r) {
        int mid = l + (r - l) / 2;
        if(a[mid].first >= t) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

int findR(vector<pair<int, int>>& a, int t) {
    // 找到最后一个小于等于t的数的下标
    int l = 0, r = a.size()-1;
    while(l < r) {
        int mid = l + (r - l + 1) / 2;
        if(a[mid].first <= t) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return l;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> a;
    for(int i=0; i<n; i++) {
        int x, c;
        cin >> x >> c;
        a.push_back(make_pair(x, c));
    }
    // 对操作点进行排序和合并
    sort(a.begin(), a.end()); // 对pair，默认是先比较first，再比较second
    // 合并相同位置的加法操作
    // 双指针
    int slow = 0;
    for(int i=0; i<n; i++) {
        if(a[i].first != a[slow].first) {
            // 将fast的值赋给slow
            a[++slow] = a[i];
        } else {
            // 相同，就合并，将fast的值累加到slow
            a[slow].second += a[i].second;
        }
    } 
    // 删除slow之后的元素
    a.erase(a.begin()+slow+1, a.end());
    // 将数组转换成前缀和数组以便于计算区间查询
    for(int i=1; i<a.size(); i++) {
        a[i].second += a[i-1].second;
    }
    // 处理查询
    for(int i=0; i<m; i++) {
        int l, r;
        cin >> l >> r;

        // 先判断是否脱离了数组
        if(l > a[a.size()-1].first || r < a[0].first) {
            cout << 0 << endl;
            continue;
        }

        // 二分查找
        // 找到第一个大于等于l的数
        int begin = findL(a, l);
        // 找到最后一个小于等于r的数
        int end = findR(a, r);
        if(begin > end || a[begin].first > r || a[end].first < l) {
            cout << 0 << endl;
        } else {
            cout << a[end].second - (begin == 0 ? 0 : a[begin-1].second) << endl;
        }
    }
    return 0;
}

1.8 区间合并

1.8.1 区间合并

题目描述： 给定 n 个区间 [l,r]，要求将这些区间合并成尽可能少的不相交区间。注意，如果在端点处相交，也算相交。

输入格式： 第一行包含一个整数 n。接下来 n 行，每行包含两个整数 l 和 r，表示一个区间的左右端点。

输出格式： 输出一行，包含一个整数，表示最少需要合并成的区间个数。

数据范围： 1≤n≤105,−109≤l≤r≤1091≤n≤10^5,−10^9≤l≤r≤10^9

输入样例：

1
2
3
4
5
5
1 2
2 4
5 6
7 8

输出样例：

1
3

解题思路：

区间合并是一种常见的算法技巧，可以省略不必要的空间开支。具体步骤如下：

  1. 定义一个数组 a，用于存储所有区间的左端点和右端点。初始时，a 为空。
  2. 对于每次操作，将操作点的下标和值添加到数组 a 中。
  3. 对数组 a 进行排序，并去重。
  4. 利用贪心算法向后延伸，检查能否与下一个区间合并，如果可以，则合并，否则，将当前区间加入结果集。

代码实现

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;

int main() {
    int n;
    cin >> n;
    if(n == 0) {
        cout << 0;
        return 0;
    }
    vector<pair<int, int>> a;
    for(int i=0; i<n; i++) {
        int l, r;
        cin >> l >> r;
        a.push_back(make_pair(l, r));
    }
    // 对操作点进行排序
    sort(a.begin(), a.end()); // 对pair，默认是先比较first，再比较second
    // 开始合并，从前向后扫描，使用一个指针指向当前合并区间的右端点
    int ans = 1;
    int r = a[0].second;
    for(int i=1; i<n; i++) {
        if(a[i].first > r) {
            // 不能合并
            ans++;
            r = a[i].second;
        } else {
            // 可以合并
            r = max(r, a[i].second);
        }
    }
    cout << ans;
    return 0;
}