基础算法学习

基础算法
Word count: 42.1k   |   Reading time≈ 202 min

学习算法的小tips:

课前提醒

上课：理解算法主要思想

下课：①背模板，默写（以题来默写） 将模板写下来调试通过！

​ ②课后题目 提高熟练度：重复写一遍！3~5次！

学算法和学英语不一样，需要自己推一遍！

第一讲——基础算法

快速排序——分治 O(nlogn)

算法步骤：

  1. 确定分界点：取左边界、中间值、有边界
  2. 调整区间：所有小于等于x的在左边，所有大于等于x的在右边（难点！）
  3. 递归处理左右两段

暴力做法：开两个数组a[ ] b[ ] 小于等于x的放a[ ]，大于等于x的放b[ ]

巧妙做法：定义指针i（i指针前面所有的数，不包括i，应该都小于等于x）和指针j （j指针后面所有的数，应该都大于等于x），i 和 j 不断往中间走，如果不满足则交换指针

背过模板就能解决边界问题！

C++快排模板如下：

C++中如果输入数据过大，建议用 scanf 函数 ，而不是 cin ！

Java里面不要用Scanner来读数据，要用 BufferedReader ，会更快！

快排模板考试很少用，面试可能会让手写！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N];
void quick_sort(int q[], int l , int r){
    if (l >= r) return;
    int x = q[l] , 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);
}
int main(){
    scanf("%d" , &n);
    for(int i = 0; i < n; i ++) scanf("%d", &q[i]);    
    quick_sort(q, 0, n-1);
    for(int i = 0; i < n; i ++) printf("%d ", q[i]);
    return 0;
}

归并排序——分治 O(nlogn)

算法步骤

  1. 确定分界点：mid = (l + r) / 2
  2. 递归排序左边和右边
  3. 将两个有序的数组合并为一个有序的数组——合二为一 （难点！） 时间复杂度O(n)

答案数组res[ ] 双指针思想！

两个有序数组分别对应指针i 和指针 j ，比较两个指针所指向的值大小，谁小谁放进res数组，相等的话把第一个数组中的值放进res[ ]，最后哪个数组还剩下东西，就直接插进res数组中

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
#include <iostream>
using namespace std;
const int N = 1000010;
int n;
int q[N], tmp[N];
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];
}
int main(){
    scanf("%d". &n);
    for (int i = 0; i < n; i ++) scanf("%d", &q[i]);
    merge_sort(q, 0, n - 1);
    for (int i = 0; i < n; i ++) printf("%d ", q[i]);
    return 0;
}

排序还有C++中的库函数可以用

在头文件中引入#include 库 然后就可以用sort（）函数

sort()函数可以对给定区间所有元素进行排序。它有三个参数sort(begin, end, cmp)，其中

begin为指向待sort()的数组的第一个元素的指针，

end为指向待sort()的数组的最后一个元素的下一个位置的指针，

cmp参数为排序准则，cmp参数可以不写，如果不写的话，默认从小到大进行排序。

这里附上某题的sort使用，以便理解其规则

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

using namespace std;

const int N = 1010;

int n;
int q[N];

int main(){
    cin >> n;
    for(int i = 0 ; i < n; i ++) scanf("%d", &q[i]);
    sort(q, q + n, [&](int a, int b){
        int x = a % 2 , y = b % 2;
        if(x != y) return x > y;
        return a < b;
    });
    for(int i = 0 ; i < n; i ++) printf("%d ", q[i]);
}

整数二分

lower_bound 和 upper_bound详细用法，二者返回的都是迭代器：

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<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N = 1e5 + 5;

int main() {
	// 升序
	int arr[] = {1,3,2,8,5};
	sort(arr, arr + 5);
	cout << "序列为(从小到大排序):";
	for(auto x : arr) cout << x << ' ';
	cout << endl;
	// 1.lower_bound
	cout << lower_bound(arr, arr+5, 5) - arr << endl; // 第一个大于等于5的是5,下标是3
	// 2.upper_bound
	cout << upper_bound(arr, arr+5, 6) - arr << endl; // 第一个大于6的是8,下标是4
	
	// 降序
	sort(arr,arr+5,greater<int>()); // greater<int>()表示降序规则
	cout << "序列为(从大到小排序):";
	for(auto x : arr) cout<<x<<' ';
	cout << endl;
	// 3.lower_bound
	cout << lower_bound(arr, arr+5, 3, greater<int>()) - arr << endl; // 第一个小于等于3的是3,下标是2
	// 4.upper_bound
	cout << upper_bound(arr, arr+5, 3, greater<int>()) - arr << endl; // 第一个小于3的是2,下标是3
	return 0;
}

整数二分会有很多边界问题！有单调性一定可以二分，没有单调性有的也可以二分

二分的本质：区间一分为二，半边满足某个性质，半边不满足某个性质，二分就可以寻找该性质的边界，找的是哪个半边的边界点就对应不同模板

算法步骤：

情况1：二分左边时

  1. 找中间值 mid = l + r + 1 >> 1 如果 l = mid 则需要补上＋1
  2. 看中间值是否满足该性质，如果满足，则答案在[mid, r]区间内，更新方式为l = mid；如果不满足，则答案在[l, mid - 1]区间内，更新方式为r = mid - 1；

情况2：二分右边时

  1. mid = l + r >> 1
  2. if ( check( mid ) ) ，如果true，则答案在[l , mid]区间，更新方式为 r = mid；如果false，则答案在[mid+1, r]区间，更新方式为 l = mid + 1；

先写一个check函数，想不同情况如何更新区间 (l + r) / 2 等同于 l + (r - l) / 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
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int q[N];
int main(){
    scanf("%d" , &n, &m);
    for(int i = 0; i < n; i ++) scanf("%d", &q[i]);    
    while (m --){
        int x;
        scanf("%d", &x);
        int l = 0, r = n - 1;
        while(l < r){
            int mid = l + r >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }
        if(q[l] != x) cout << "-1 -1" << endl;
        else{
            cout << l << ' ';
            int l = 0, r = n - 1;
            while(l < r){
                int mid = l + r + 1 >> 1;
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }
            cout << l << endl;
        }
    }
    return 0;
}

二分的主要思想：每次将区间一分为二，选择答案所在的区间继续进行处理，当区间长度为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
bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

浮点数二分

浮点数二分不会有任何边界问题，答案区间很小的时候，就当作找到了答案

根据题干中所给信息来确定精度：四位小数 1e-6 五位小数 1e-7 六位小数 1e-8 推荐写法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
int main(){
    double x;
    cin >> x;
    double l = 0, r = max(1.0, x);
    while(r - l > 1e-8){
        double mid = (l + r) / 2;
        if(mid * mid >= x) r = mid;
        else l = mid;
    }
    printf("%lf\n", l);
    return 0;
}

另一种写法就是直接迭代循环100次，不用精度的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
int main(){
    double x;
    cin >> x;
    double l = 0, r = max(1.0, x);
    for(int i = 0; i < 100; i ++){
        double mid = (l + r) / 2;
        if(mid * mid >= x) r = mid;
        else l = mid;
    }
    printf("%lf\n", l);
    return 0;
}

高精度

只有C++同学需要学高精度！Java和Python同学可以不学！

C++里面没有大整数类，面试不常考，笔试偶尔会出现！

四种考法：A和B位数大概在十的六次方左右 A+B A-B A*a A/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
#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; 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(t);
    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);
    for (int i = C.size() - 1; i >= 0; i --) printf("%d", C[i]);
    return 0;
}

高精度压位

加法可以压9位，乘法可以压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
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <vector>

using namespace std;

const int base = 1e9;

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 % base);
        t /= base;
    }
    if (t) C.push_back(t);
    return C;
}

int main(){
    string a, b;
    vector<int> A, B;
    cin >> a >> b;
    
    for (int i = a.size() - 1, s = 0, j = 0, t = 1; i >= 0; i --){ // j来存储当前压了几位了
        s += (a[i] - '0') * t;
        j ++, t *= 10;
        if(j == 9 || i == 0) {
            A.push_back(s);
            s = j = 0;
            t = 1;
        }
    }
    
    for (int i = b.size() - 1, s = 0, j = 0, t = 1; i >= 0; i --){
        s += (b[i] - '0') * t;
        j ++, t *= 10;
        if(j == 9 || i == 0) {
            B.push_back(s);
            s = j = 0;
            t = 1;
        }
    }
    
    auto C = add(A, B);
    
    cout << C.back();
    
    for (int i = C.size() - 2; i >= 0; i --) printf("%09d", C[i]);
    cout << endl;
    return 0;
}

减法如下：

高精度减法注意看题干中是否是两个正整数相减，负数相减可以看作绝对值相减再取/不取负号，因此需要cmp函数来调整两个数的次序，使得大数减小数

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;
bool cmp(vector<int> &A, vector<int> &B){ // 判断 A 是否 >= 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]; // 判断B[i]是否存在
        C.push_back((t + 10) % 10); // t >= 0 则为 t; t < 0 则为 t + 10
        if (t < 0) t = 1;
        else t = 0;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back(); // 去掉前导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');
    if(cmp(A, B)){
        auto C = sub(A, B);
        for (int i = C.size() - 1; i >= 0; i --) printf("%d", C[i]);
    }
    else {
        auto C = sub(B, A);
        printf("-");
        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
#include <iostream>
#include <vector>

using namespace std;

vector<int> mul(vector<int> &A, int b){ // 加引用可以提高效率
    vector<int> C;
    int t = 0; // 进位
    for (int i = 0; i < A.size() || t; i ++){
        if(i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
// 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;
    cin >> a >> b;
    vector<int> A;
    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 << r << endl;
    return 0;
}

前缀和与差分

前缀和与差分是一对逆运算

前缀和

原数组 a[ ]

前缀和数组（下标从1开始）Si = a1 + a2 + … + ai

① 如何求Si 通过Si-1 + ai 来求得 （定义边界S0 = 0）

② 作用 求数组中一段数的和 Sr - Sl-1 实现O(1)的时间复杂度来求解数组中一段的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 一维前缀和
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int a[N], s[N];
int main(){
	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;
}
1
2
ios::sync_with_stdio(false); // 提高cin的读取速度 同时不能再使用scanf了
// ios+cin 和 scanf都差不多快，但还是scanf更快一些

二维前缀和

image-20250217102137551

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 二维前缀和
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N], s[N][N];
int main(){
    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 ++)
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]; // 求前缀和
    while (q --){
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]); // 算子矩阵的和
    }
    return 0;
}

差分

前缀和的逆运算

原数组 a1，a2，…，an

构造数组 b1，b2，…，bn 使得 ai = b1 + b2 + … + bi

数组 b 称为 数组 a 的差分

对数组 b 求前缀和得到原数组 a

应用：让 al 到 ar 内所有元素都加上 c 暴力 O(n) 差分 O(1)

在b数组里修改两个数即可：

bl 加上 c (会使得 al 到 an 全部元素加 c) 因此再让 br+1 减去 c

差分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N];
void insert(int l, int r, int c){
    b[l] += c;
    b[r + 1] -= c;
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i ++) insert(i, i, a[i]); // 构造差分数组b
    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;
}

二维差分 应用 给子矩阵中的所有数加一个值

在二维数组 b 里修改四个数即可

image-20250217113149943

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
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, q;
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(){
    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]); // 构造差分数组b
    while(q --){
        int x1, y1, x2, y2, c;
        cin >> 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 ++)
        	b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
    for(int i = 1; i <= n; i ++){ 
        for(int j = 1; j <= m; j ++) printf("%d ", b[i][j]);
        puts(""); // 等效于 cout << endl;
    }
    return 0;
}

双指针

双指针算法用的非常多！归并排序中把两个有序序列排序用的就是双指针算法！

第一类：两个指针分别指向两个序列

第二类：两个指针指向同一个序列

1
2
3
4
for(i = 0, j = 0; i < n; i ++){
    while(j < i && check(i, j)) j++;
    // 每道题的具体逻辑...
}

⭐ 双指针算法最核心思想：从 O(n2) 可以优化到 O(n)

双指针算法就是在朴素算法的基础上发现单调性来求解！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 双指针最简单应用，将字符串分割为若干单词输出
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int main(){
    char str[N];
    fgets(str, N, stdin);
    int n = strlen(str);
    for(int i = 0; i < n; i ++){
        int j = i;
        while(j < n && str[j] != ' ') j ++;
        for(int k = i; k < j; k ++) printf("%c", str[k]);
        puts("");
        i = j;
    }
    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
// 最长连续不重复子序列
for(int i = 0, j = 0; i < n; i ++){
    while(j <= i && check(j, i)) j ++;
    res = max(res, i - j + 1);
}

#include <iostream>
using namespace std;
const int N = 100010;
int a[N];
int s[N]; // 存当前[j, i]区间内每个数出现次数
int main(){
    cin >> n;
    for(int i = 0; i < n; i ++){
        cin >> a[i];
        s[a[i]] ++;
    } 
    int res = 0;
    for(int i = 0, j = 0; i < n; i ++){
        while(s[a[i]] > 1){
            s[a[j]] --;
            j ++;
        }
        res = max(res, i - j + 1);
    }
    cout << res << endl;
    return 0;
}

位运算

位运算最常用操作：

① 整数 n 的二进制表示里面第 k 位数字是几：要么是0 要么是1（个位是第0位，十位是第1位）

  1. 先把第 k 位数字移到最后一位 n >> k

  2. 看一下个位是几， x & 1（x和1做与运算）

总结：n >> k & 1

1
2
3
4
// 输出n的各位二进制表示
int n = 10;
for(int i = 3; i >= 0; i --) 
    cout << (n >> i & 1);

② lowbit 操作（树状数组的基本操作）

lowbit(x)：返回x的最后一位1（最右边的一位1）

x = 1010 ；lowbit(x)返回的是10

实现：x & -x 因为：C++中一个整数的负数是这个数的取反加1（补码表示）

应用：统计 x 里面1的个数！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 统计数组里面每个数的1的个数！
#include <iostream>
using namespace std;
int n;
int q[n];
int lowbit(int x){
    return x & -x;
}
int main(){
    cin >> n;
    for(int i = 0; i < n; i ++) scanf("%d", &q[i]);
    while(n --){
        int x;
        cin >> x;
        int res = 0;
    	while (x) { // 每次减去x的最后一位1
        	x -= lowbit(x);
        	res ++;
   		}
    	cout << res << " ";
    }
    return 0;
}

为什么计算机不用反码，反而引入补码的概念？

因为计算机底层实现是没有减法的，利用加法来做减法，负数的性质：一个数加上它的负数应该等于0

-x = 0 - x = 00…0 - x（向上借位）= 100…0 - x = x取反 + 1

离散化

离散化特指整数的离散化（保序的离散化）

值域大 个数少

image-20250218085557689

离散化需要注意的两个问题：

① a 数组中可能有重复元素，需要去重！

② 如何算出 x 离散化后的值是多少，二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <vector>
vector<int> alls;
sort(alls.begin(), alls.end()); // 从小到大排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去重
// unique函数作用是将数组中该范围内的元素去重，并且返回去重后的数组的尾端点，unique函数会把重复元素放到最后那部分，所以返回的尾端点下表往后到数组结束都是重复元素，再删去即可完成去重工作！
int find(int x){ // 二分求出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 即映射到1,2,...,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
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
// 区间和
// 给定一个无限长的数轴，数轴上的每个坐标的数都是0，现在有n次操作，每次操作将某一位置上的数加c，接下来进行m次询问，每个询问包含两个整数l和r，你需要求出在区间[l, r]之间所有数的和
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
int n, m;
int a[N], s[N];
vector<int> alls; // 存所有待离散化的值
vector<PII> add, query; // 存储插入操作和查询操作
int find(int 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开始：因为用前缀和，所以从1开始
}
int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i ++){
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});
        alls.push_back(x);
    }
    for(int i = 0; i < m; i ++){
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});
        alls.push_back(l);
        alls.push_back(r);
    }
    // 去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    // 处理插入
    for (auto item : add){
        int x = find(item.first);
        a[x] += item.second;
    }
    // 预处理前缀和
    for (int i = 1; i <= alls.size(); i ++) s[i] = s[i - 1] + a[i];
    // 处理询问
    for (auto item : query){
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
// unique函数的实现：①它是第一个数 ②a[i]≠a[i-1]
// 双指针算法，第一个指针i遍历所有数，第二个指针j存当前存到了几个不同的数(j<=i)
vector<int>::iterator unique(vector<int> &a){
    int j = 0;
    for(int i = 0; i < a.size(); i ++) 
        if(!i || a[i] != a[i - 1]
        	a[j ++] = a[i];  
	// a[0] ~ a[j - 1] 所有a中不重复的数
    return a.begin() + j;
}

区间合并

用的情况不多，偶尔会用到

应用场景：给很多很多区间，如果两个区间有交集，就合并为一个区间

image-20250218105722418

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
// 输入n个区间，要求把有交集的区间进行合并（只有端点为交集也算可以合并为一个），输出合并后的区间个数
// 1. 按区间左端点排序
// 2. 扫描整个区间，扫描过程中把可能有交集的区间合并
// 实际上就是 模拟 + 贪心
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
int n;
vector<PII> segs;
void merge(vector<PII> &segs){
    vector<PII> res;
    sort(segs.begin(), segs.end()); // pair排序优先以左端点排序，再以右端点排序
    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;
}
int main(){
    cin >> n;
    for(int i = 0; i < n; i ++){
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }
    merge(segs);
    cout << segs.size() << endl;
    return 0;
}

习题课

求第k个数

给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列的第k小的数是多少

1
2
3
4
5
6
7
8
9
10
11
12
13
// 快排 O(nlogn)，快速选择时间复杂度 O(n)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n,k;
int a[N];
int main(){
    cin >> n >> k;
    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
    sort(a, a + n);
    cout << a[k - 1] << endl;
}

快排：递归左右两边

快选：选择一边进行递归就可以了，快选时间复杂度 O(n)

image-20250218153956301

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
// 快选
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n,k;
int q[N];
int quick_sort(int l, int r, int k){
    if(l >= r) return q[l];
    int x = q[l], i = l - 1, j = r + 1;
    while(i < j){
        while(q[i ++] < x);
        while(q[j --] > x);
        if(i < j) swap(q[i], q[j]);
    }
    int sl = j - l + 1; // 左半边区间数的个数
    if(k <= sl) return quick_sort(l, j, k);
    return quick_sort(j + 1, r, k - sl);
}
int main(){
    cin >> n >> k;
	for(int i = 0; i < n; i ++) scanf("%d", &q[i]);
    cout << quick_sort(0, n - 1, k) << endl; // 直接返回答案k
    return 0;
}

求逆序对的数量

逆序对是一个数对，选俩数，如果前面的比后面大，就是一个逆序对

思路：分治

归并排序思想：

  1. 将整个区间一分为二 [L, R] - > [L, mid], [mid + 1, R]
  2. 递归排序 [L, mid] 和 [mid + 1, R]
  3. 归并，将左右两个有序序列合并成一个有序序列

逆序对 可以被分为三大类：

  1. 两个数同时出现在左半边
  2. 两个数同时出现在右半边
  3. 两个数一个在左半边，一个在右半边

image-20250218172601418

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>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;
int q[N], tmp[N];
LL merge_sort(int l, int r){
    if(l >= r) return 0;
    int mid = l + r >> 1;
    LL res = merge_sort(l, mid) + merge_sort(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 ++];
            res += mid - i + 1;
        }
    }
    // 扫尾工作（以下两个循环最多只执行一个循环）
    while(i <= mid) tmp[k ++] = q[i ++];
    while(j <= r) tmp[k ++] = q[j ++];
    // 物归原主
    for(int i = l, j = 0; i <= r; i ++, j ++) q[i] = tmp[j];
    return res;
}
int main(){
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> q[i];
    cout << merge_sort(0, n - 1) << endl;
    return 0;
}

数的三次方根

给定一个浮点数n，求它的三次方根，保留六位小数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <algorithm>
using namespace std;
double n;
int main(){
    cin >> n;
    double l = -1e5, r = max(1.0, n);
    while(r - l > 1e-8){
        double mid = (l + r) / 2;
        if(mid * mid * mid >= n) r = mid;
        else l = mid;
    }
    printf("%.6lf", l); // printf 默认保留六位小数
    return 0;
}

前缀和

一维前缀和：

  1. S[i] = a1 + a2 + … + ai
  2. sum(L, R) = aL + aL + 1 + aL + 2 + … + aR = SR - SL-1

预处理前缀和数组 用公式求区间和

输入一个长度为n的整数序列，接下来再输入m个询问，每个询问输入一对l，r

对于每个询问，输出原序列中第l个数到第r个数的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int a[N], s[N];
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]); // 下标均从1开始！
    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] << endl;
    }
    return 0;
}

DP问题、前缀和、哈希问题下标都是从 1 开始！

二维前缀和：S[ i , j ] 的含义，两个下标也是从1开始

以(x1, y1)为左上角, (x2, y2)为右下角 这一子矩阵中所有数的和该如何计算：S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

S[i, j]如何计算：S[i , j] = S[i - 1, j] + S[i , j - 1] - S[i - 1, j - 1] + a[i , j]

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;
const int N = 1010;
int n, m, q;
int a[N][N], s[N][N];
int main(){
    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 ++)
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
    while(q --){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        printf("%d\n", s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1]);
    }
    return 0;
}

差分

差分的题目没有前缀和数组！

给定 a[1], a[2], … , a[n] 构造差分数组b[N], 使得 a[i] = b[1] + b[2] + … + b[i]

核心操作：将a [L~R] 全部加上C，等价于让 b[L] += C, b[R + 1] -= C

为什么python、JavaScript运行速度这么快？

因为python、JavaScript是不需要编译的，而C++、Go、Java等语言需要编译，因此在运行小数据时前者更快，但运行大数据时C++和Go更快，Java最慢！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m; // n是数组长度，m是操作个数
int a[N], b[N]; // a是原数组，b是差分数组
void insert(int l, int r, int c){
    b[l] += c;
    b[r + 1] -= c;
}
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++) insert(i, i, a[i]);
    while(m --){
        int l, r, c;
        cin >> l >> r >> c;
        insert(l, r, c);
    }
    for(int i = 1; i <= n; i ++) a[i] = a[i - 1] + b[i];
    for(int i = 1; i <= n; i ++) printf("%d ", a[i]);
    puts("");
    return 0;
}

差分矩阵

给定原矩阵a[i, j]，构造差分矩阵b[i, j]，使得a矩阵是b矩阵的二维前缀和

核心操作：以(x1, y1)为左上角, (x2, y2)为右下角 这一子矩阵中所有数加上C

对于差分数组的影响：S[x1, y1] += C，S[x1, y2 + 1] -= C，S[x2 + 1, y1] -= C，S[x2 + 1, y2 + 1] += 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
34
35
#include <iostream>
using namespace std;
const int N = 1e3 + 10;
int n, m, q; 
int a[N][N], b[N][N]; // a是原数组，b是差分数组
void insert(int x1, int y1, int x2, int y2, int c){
    b[x1][y1] += c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= c;
    b[x2 + 1][y2 + 1] += c;
}
int main(){
    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;
        cin >> 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 - 1][j] + a[i][j - 1] - 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]);
        }
        puts("");
    }
    return 0;
}

数组元素的目标和

image-20250222095857078

双指针算法：

先想暴力做法如何做，再看是否有单调性，如果有单调性则看如何优化！

双指针算法的优化：找单调性！

A数组和B数组都是单调上升的

1
2
3
4
// 双指针算法，单调性
// 可以发现当A[i] + B[j] >= x时，当i再往后移动，j只会向左移动看是否满足题意
for(int i = 0; i < n; i ++)
    while(j >= 0 && A[i] + B[j] > x) j--;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m, x;
int a[N], b[N];
int main(){
    scanf("%d%d%d", &n, &m, &x);
    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
    for(int i = 0; i < m; i ++) scanf("%d", &b[i]);
    for(int i = 0, j = m - 1; i < n; i ++){
        while(j >= 0 && a[i] + b[j] > x) j--;
        if(a[i] + b[j] == x) {
            cout << i << " " << j << endl;
            break;
        }
    }
    return 0;
}

区间和

image-20250222105656501

快速求区间和 -> 用前缀和来做 10^9 -> 10^5 用离散化来做（把规模较大的数转化成规模较小的数） 离散化除了配合前缀和以外，配合线段树和树状数组也很多

排序、去重、查找（手写二分或用lower_bound）

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
// 区间和
// 给定一个无限长的数轴，数轴上的每个坐标的数都是0，现在有n次操作，每次操作将某一位置上的数加c，接下来进行m次询问，每个询问包含两个整数l和r，你需要求出在区间[l, r]之间所有数的和
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
int n, m;
int a[N], s[N];
vector<int> alls; // 存离散化的值
vector<PII> add, query;
int find(int x){ // 前缀和下标要从1开始，所以最后要加1
    return lower_bound(alls.begin(), alls.end(), x) - alls.begin() + 1;
}
int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i ++){
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});
        alls.push_back(x);
    }
    for(int i = 0; i < m; i ++){
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});
        alls.push_back(l);
        alls.push_back(r);
    }
    // 去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    // 处理插入
    for (auto item : add){
        int x = find(item.first);
        a[x] += item.second;
    }
    // 预处理前缀和
    for (int i = 1; i <= alls.size(); i ++) s[i] = s[i - 1] + a[i];
    // 处理询问
    for (auto item : query){
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}

第二讲——数据结构

链表与邻接表

单链表

一般用数组模拟链表（静态链表）

结构体＋指针也可以实现链表（面试用的多，笔试用的不多），但这种方式很慢，C++中new()函数动态分配节点是相对较慢的，可能会TLE（超时），平时不会采用这种动态链表的方式，改进后可以用

① 数组模拟单链表：邻接表（邻接表其实是n个链表）用于存储图和树

e [N]（存储该点的值） ne[N]（存储该点的指向下一个节点指针）

e 和 ne 是用下标关联起来的

image-20250219090616401

实现一个单链表，链表初始为空，支持三种操作：

  1. 向链表头插入一个元素
  2. 删除第k个插入的数后面的数（删除下标是k-1的点后面的一个点）
  3. 在第k个插入的数后插入一个数（在下标是k-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
54
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
// head表示头节点下标
// e[i]表示节点i的值
// ne[i]表示节点i的next指针对应节点下标的值
// idx存储当前已经用到了哪个点
int head, e[N], ne[N], idx;
void init(){
    head = -1;
    idx = 0;
}
// 将 x 插到头节点，用的最多！
void add_to_head(int x){
    e[idx] = x;
    ne[idx] = head;
    head = idx ++;
}
// 将 x 插入到下标为 k 的点的后面
void add(int k, int x){
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx ++;
}
// 将下标为 k 的后面的一个点删除
void remove(int k){
    ne[k] = ne[ne[k]]；
}
int main(){
    int m;
    cin >> m;
    init();
    while(m --){
        int k, x;
        char op;
        cin >> op;
        if(op == 'H'){
            cin >> x;
            add_to_head(x);
        }
        else if(op == 'D'){
            cin >> k;
            if(!k) head = ne[head];
            remove(k - 1);
        }
        else{
            cin >> k >> x;
            add(k - 1, x)
        }
    }
    for(int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
    cout << endl;
    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
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int m;
int e[N], l[N], r[N], idx;
// 初始化
void init(){
    // 0表示左端点，1表示右端点
    r[0] = 1, l[1] = 0;
    idx = 2; // 因为0和1已经被占用过了，所以idx从2开始
}
// 在下标为k的点右边，插入x
void add(int k, int x){ // 若在k的左边插入x，则为add(l[k], x)
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx++;
}
// 删除下标为k的点
void remove(int k){
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

邻接表

head[1] 是一个单链表；head[2] 是一个单链表 … ；head[i] 是一个单链表

栈与队列

栈

栈和队列用 stl 容器可以直接写，数组来模拟

栈：先进后出（先插入的元素会被后弹出来）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 栈的模拟 栈初始时tt = 0
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int stk[N], tt; // 栈用stk[N]表示，tt表示栈顶下标
// 插入
stk[++ tt] = x;
// 弹出
tt --;
// 判断栈是否为空
if(tt > 0) not empty; // 不空
else empty;
// 栈顶
stk[tt];

队列

队列：先进先出（先插入的元素会先弹出来）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 队列的模拟 队列初始时tt = -1
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
// hh表示队头，tt表示队尾，一般在队尾插入元素，在队头弹出元素
int q[N], hh, tt = -1;
// 插入
q[++ tt] = x;
// 弹出
hh ++;
// 判断队列是否为空
if(hh <= tt) not empty
else empty;
// 取出队头元素
q[hh]
// 取出队尾元素
q[tt]

应试教育考察的就是：记忆力和自制力！

单调栈

单调栈和单调队列能用到的题型很少！

单调栈常见的有一种题型：

给定一个序列，求一下这个序列中的每一个数 左边（右边）离它最近的且比它本身大（小）的数 在什么地方

例如：3 4 2 7 5 求每个数左边离它最近 且比它本身小的数 是多少 若没有返回-1

ans：-1 3 -1 2 2

先考虑暴力做法是什么，再挖掘一些性质，可以把目光集中到较小的状态，使得时间复杂度降低

暴力做法： 时间复杂度O(n^2)

1
2
3
4
5
6
7
8
for(int i = 0; i < n; i ++){
	for(int j = i - 1; j >= 0; j --){
		if(a[i] > a[j]){
			cout << a[j] << " " << endl;
			break;
		}
	}
}

优化：可以用一个栈来存储该 a[i] 左边的所有元素 时间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int stk[N], tt;
int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 0; i < n; i ++){
        int x;
        cin >> x;
        while(tt && stk[tt] >= a[i]) tt --;
        if(tt) cout << stk[tt] << ' ';
        else cout << -1 << ' ';
        stk[++ tt] = x;
    }
    return 0;
}

在本题跑的时间中 cin 和 cout 要比 scanf printf 慢10倍左右

单调队列

应用：求滑动窗口里的最大值（最小值），找出来离它最近且比它小（大）的元素

可以用单调队列优化的最典型模型

先考虑暴力做法是什么，再挖掘一些性质，可以把目光集中到较小的状态，使得时间复杂度降低

窗口可以用队列来维护

先考虑用栈和队列暴力模拟遍历所有元素，再看栈和队列里哪些元素没有用，再看剩下的元素是否有单调性，再利用单调性优化

拿数组来模拟 stl 会更快

99%情况下C++是不会开O(2)优化，stl 容器某些情况下会慢一些

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
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n, k;
int a[N], q[N];
int main(){
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
    int hh = 0, tt = -1;
    for(int i = 0; i < n; i ++){
        // 判断队头是否已经滑出窗口
        if(hh <= tt && i - k + 1 > q[hh]) hh ++;
        while(hh <= tt && a[q[tt]] >= a[i]) tt --;
        q[++ tt] = i;
        if(i >= k - 1) printf("%d ", a[q[hh]]);
    }
    puts("");
    
    hh = 0, tt = -1;
    for(int i = 0; i < n; i ++){
        // 判断队头是否已经滑出窗口
        if(hh <= tt && i - k + 1 > q[hh]) hh ++;
        while(hh <= tt && a[q[tt]] <= a[i]) tt --;
        q[++ tt] = i;
        if(i >= k - 1) printf("%d ", a[q[hh]]);
    }
    puts("");
    
    return 0;
}

kmp

KMP算法的时间复杂度 O(n)

先想一下暴力算法怎么做，再想如何优化

1
2
3
4
5
6
7
8
9
10
// 暴力算法
// s[N], p[M]
for(int i = 1; i <= n; i ++){
    bool flag = true;
    for(int j = 1; j <= m; j ++)
        if(s[i] != p[j]){
            flag = false;
            break;
        }
}

KMP字符串：

求出模板串P在模式串S中所有出现的位置的起始下标。

第一行输入整数N，表示字符串P的长度；第二行输入字符串P

第三行输入整数M，表示字符串S的长度；第四行输入字符串M

next数组含义：可以满足模板串P中最大后缀和前缀完全一致的最长长度

image-20250219175933822

匹配过程 比较的是 S[ i ] 和 P[ j + 1 ]，拿这两个元素比较

若比较失败：P的指针 j 往前跳 ne[ 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
// KMP 下标从1开始
#include <iostream>
using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10;
int n, m;
char p[N], s[M];
int ne[N]; // next数组可能在C++中某些头文件被用过，因此起名为ne
int main(){
    cin >> n >> p + 1 >> m >> s + 1; // 下标从1开始！
    // 求next过程
    for(int i = 2, j = 0; i <= n; i ++){ // next从2开始循环，因为next[1]=0
        while(j && p[i] != p[j + 1]) j = ne[j];
        if(p[i] == p[j + 1]) j ++;
        ne[i] = j;
    }
    // kmp匹配过程
    for(int i = 1, j = 0; i <= m; i ++){ // i是遍历S所有字母，j是从0开始做，每次试着往前走
        while(j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++;
        if (j == n){
            printf("%d ", i - n);
            j = ne[j]; // 匹配成功的话
        }
    }
    return 0;
}

Trie树（字典树）

非常简单的数据结构：Trie树

基本作用：高效地存储和查找字符串集合（字母类型不会多）的数据结构

存储结构如下：

image-20250220094530120

查找结构如下：

image-20250220094735725

Trie字符串统计：

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>
using namespace std;
const int N = 1e5 + 10;
// son存的是该节点后代，cnt存的是以该字符结尾的字符串数量，idx存的是当前用到的下标
int son[N][26], cnt[N], idx; // 下标是0的点，既是根节点，又是空节点
void insert(char str[]){
    int p = 0; // 存放当前所在位置
    for(int i = 0; str[i]; i ++){ // C++中字符串以\0结尾
        int u = str[i] - 'a'; // 获取字母编号
        if(!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++; // 以该字母结尾的字符串数量加1
}
int query(char str[]){
    int p = 0;
    for(int i = 0; str[i]; i ++){
        int u = str[i] - 'a';
        if(!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}
int main(){
    int n;
    scanf("%d", &n);
    while(n --){
        char op[2];
        scanf("%s%s", op, str);
        if(op[0] == 'I') insert(str);
        else printf("%d\n", query(str));
    }
}

并查集

面试和比赛都容易出的数据结构，代码短，思路精巧！

作用：

  1. 将两个集合合并
  2. 询问两个元素是否在一个集合当中

并查集可以近乎O(1)（不一定是完全O(1)）的时间来完成以上两个操作

基本原理：用树的形式来维护集合，一个集合对应一棵树，树根的编号就是集合的编号，每个节点都存储它的父节点，p[x] 表示 x 的父节点

问题1：如何判断树根：if (p[x] == x)

问题2：如何求x的集合编号：while (p[x] != x) x = p[x]（一直求x的父节点往上走）

问题3：如何合并两个集合：将一个集合根节点当成另一个集合根节点的子节点

px 是 x 的集合编号，py 是 y 的集合编号。p[x] = y

以上中的问题2时间复杂度仍很高，就有了以下的路径压缩优化：

一旦往上走的时候找到了根节点，就会把整个路径上的点直接指向根节点！

image-20250220101808848

并查集加上这个优化，基本上实现O(1)

按值合并优化的并不明显，故一般只会写以上的路径压缩优化！

按值合并的值指的是树的高度，倾向于将矮的树接到高的树上！

朴素并查集

image-20250220102433807

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>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int p[N];
int find(int x){ // 返回x的祖宗节点（所在集合的编号） + 路径压缩优化
    if(p[x] != x)  p[x] = find(p[x]); // 如果说x不是根节点，就让其父节点等于其祖宗节点
    return p[x]; // 返回其父节点
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) p[i] = i;
    while(m --){
        char op[2]; // scanf的缺点：如果是%c会读一些空格和回车等字符，如果是%s会自动忽略空格和回车，因此建议读一个字母的话还是读字符串的形式！
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if(op[0] == 'M') p[find(a)] = find(b); // a的祖宗节点父亲等于b的祖宗节点，等价于让a和b所在集合合并
        else {
            if(find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

维护每个集合顶点数目的并查集

以下讲解并查集的拓展情况，添加额外变量，维护额外信息：

  1. 想要动态地知道每个集合当前有多少个元素

参考下题：连通块中点的数目

image-20250220104052265

前两个操作和上题一样，多了一个额外操作：统计集合中点的数目

size[ i ]，我们只保证根节点的 size 是有意义的

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>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int p[N], size[N]; // size表示每一个集合中点的数目
int find(int x){ // 返回x的祖宗节点（所在集合的编号） + 路径压缩优化
    if(p[x] != x)  p[x] = find(p[x]); // 如果说x不是根节点，就让其父节点等于其祖宗节点
    return p[x]; // 返回其父节点
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++){
        p[i] = i;
        size[i] = 1; // 初始化每个集合点的数目为1
    }
    while(m --){
        char op[2]; // scanf的缺点：如果是%c会读一些空格和回车等字符，如果是%s会自动忽略空格和回车，因此建议读一个字母的话还是读字符串的形式！
        int a, b;
        scanf("%s", op);
        if(op[0] == 'C') {
            scanf("%d%d", &a, &b);
            if(find(a) == find(b)) continue; // 如果a和b在同一个集合里，没有必要进行以下操作
            size[find(b)] += size[find(a)];
            p[find(a)] = find(b); // a的祖宗节点父亲等于b的祖宗节点，等价于让a和b所在集合合并
        }
        else if(op[1] == '1'){
            scanf("%d%d", &a, &b);
            if(find(a) == find(b)) puts("Yes");
            else puts("No");
        }
        else{
            scanf("%d", &a);
            printf("%d\n", size[find(a)]);
        }
    }
    return 0;
}

记录偏移量的并查集

维护每个顶点到根节点的距离，见例题：《算法竞赛进阶指南》中的 “食物链”

堆

stl 里面的堆就是优先队列

可以支持修改和删除任意元素的堆，后面图论中的迪杰斯特拉算法会用到

堆支持以下操作（前三个 stl 有直接的函数，后两个 stl 没有）：

  1. 插入一个数
  2. 求集合当中的最小值
  3. 删除最小值
  4. 删除任意一个元素
  5. 修改任意一个元素

堆是一棵完全二叉树：除最后一层节点外，上面所有节点都是非空的，最后一层节点从左到右依次排布的

小根堆：每一个节点都是小于等于左右子树的所有节点值，根节点就是最小值

堆的存储：全新的存储方式，用一个一维数组来存！

1号点是根节点，2号点是1的左孩子，3号点是1的右孩子

以此类推：x的左儿子为2x，x的右儿子为2x+1

堆的两个基本操作： 时间复杂度 O(logn)

1
2
3
4
5
6
7
8
9
down(x){ // 一个值变大了，则将该节点往下移
    int t = u; // t表示三个点里的最小值
    if(u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if(u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if(u != t){ // u不是最小值，即需要更换的话
        swap(h[u], h[t]);
        down(t);
    }
}
1
2
3
4
5
6
up(x){ // 一个值变小了，则将该节点往上移
    while(u / 2 && h[u / 2] > h[u]){ // u有父节点并且u的父节点比它本身大
        swap(h[u / 2], h[u]);
        u /= 2;
    }
}

下标均从1开始！因为0的左孩子就是2*0=0，冲突了！

  1. 插入一个数

    heap[++ size] = x; up[size];

  2. 求集合当中的最小值

    heap[1]

  3. 删除最小值

    heap[1] = heap[size]; size --; down(1);

    先用最后一个点覆盖第一个点，再将最后一个点去掉，再让第一个点往下走

  4. 删除任意一个元素

    heap[k] = heap[size]; size --; down(k); up(k);

  5. 修改任意一个元素

    heap[k] = x; down(k); up(k)

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>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int h[N], size;
void down(int u){
    int t = u; // t表示三个点里的最小值
    if(u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if(u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if(u != t){ // u不是最小值，即需要更换的话
        swap(h[u], h[t]);
        down(t);
    }
}
void up(int u){
    while(u / 2 && h[u / 2] > h[u]){ // u有父节点并且u的父节点比它本身大
        swap(h[u / 2], h[u]);
        u /= 2;
    }
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%d", &h[i]);
    size = n;
    for(int i = n / 2 ; i ; i --) down(i); // 从 n/2 down 到 1 来建堆时间复杂度为O(n)，正常插入节点的时间复杂度为O(nlogn)
    while(m --){
        printf("%d ", h[1]);
        h[1] = h[size];
        size --;
        down(1);
    }
    return 0;
}

从 n/2 down 到 1 来建堆时间复杂度为O(n) 的证明如下：（错位相减法证明）

倒数第二层最多只能down一次，倒数第三层最多只能down两次…

n/4 * 1 + n/8 * 2 + n/16 * 3…可证 < n

image-20250220120110489

以下例题涉及全部五个操作：

第四个和第五个操作和上述不太相同：第k个插入的数需要提前存储，能够快速找到

image-20250220121438083

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
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = 1e5 + 10;
int n, m;
// ph[k]存的是第k个插入的点是哪个（在堆里的下标） 下标映射到堆
// hp[k]存的是堆里的第k个点是第几个插入的（插入的顺序）  堆映射到下标
int h[N], ph[N], hp[N], size;
void heap_swap(int a, int b){
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);    
}
void down(int u){
    int t = u; // t表示三个点里的最小值
    if(u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if(u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if(u != t){ // u不是最小值，即需要更换的话
        heap_swap(u, t);
        down(t);
    }
}
void up(int u){
    while(u / 2 && h[u / 2] > h[u]){ // u有父节点并且u的父节点比它本身大
        heap_swap(u / 2, u);
        u /= 2;
    }
}
int main(){
    int n, m = 0;
    scanf("%d", &n);
    while(n --){
        char op[10];
        int k, x;
        scanf("%s", op);
        if(!strcmp(op, "I")){
            scanf("%d", &x);
            size ++;
            m ++;
            ph[m] = size, hp[size] = m;
            h[size] = x;
            up(size);
        }
        else if(!strcmp(op, "PM")) printf("%d\n", h[1]);
        else if(!strcmp(op, "DM")){
            heap_swap(1, size);
            size --;
            down(1);
        }
        else if(!strcmp(op, "D")){
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, size);
            size --;
            down(k), up(k);
        }    
        else {
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x;
            down(k), up(k);
        }
    }
    return 0;
}

哈希表

把一个比较庞大的空间映射到比较小的空间，例如 0 ~ 10^9 映射到 0 ~ 10^5

前面讲的离散化是需要保序的（单调递增），算是一种特殊的哈希方式，现在讲的是一般的哈希方式！一般情况下的时间复杂度 O(1)

哈希函数怎么写？取模的数要尽可能取成质数，而且离2的整次幂尽可能远！

因为这么取的话冲突概率最小！

① x mod 10^5 ∈ (0, 10^5)

② 冲突（若干个不同的数映射到同一个数）

存储结构

存储结构分为 开放寻址法 和 拉链法 两种都很常用！

拉链法：如果存在冲突，则一个槽上多拉几个数组成一条链

image-20250220153548270

算法题里面一般是添加和查找这两种操作！如果非要实现删除，则对删除的该点标记！

拉链法：

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 <cstring>
using namespace std;
const int N = 1e5 + 3; // 这么取是因为大于十万的第一个质数是十万零三
int h[N], e[N], ne[N], idx; // 开的槽，每个槽上有个链
void insert(int x){
    int k = (x % N + N) % N; // 在C++里面负数取模也是负数，所以这里目的就是变成整数
    e[idx] = x;
    ne[idx] = h[k]; 
    h[k] = idx ++;
}
bool find(int x){
    int k = (x % N + N) % N;
    for(int i = h[k]; i != -1; i = ne[i]) // i = ne[i]即为链表遍历写法
        if(e[i] == x) return true;
    return false;
}
int main(){
    int n;
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    while(n --){
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if(*op == 'I') insert(x);
        else{
            if(find(x)) puts("Yes");
            else puts("No");
        }
    }
}

开放寻址法：只开了一个一维数组，一维数组的长度得是原数据长度的两到三倍，这样冲突概率较低

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
// 开放寻址法
#include <iostream>
#include <cstring>
using namespace std;
const int N = 2e5 + 3, null = 0x3f3f3f3f; 
int h[N]; 
int find(int x){ // 如果x已经存在，则返回x的位置，反之为应该存储的位置
    int k = (x % N + N) % N; 
    while(h[k] != null && h[k] != x){
        k ++;
        if(k == N) k = 0;
    }
    return k;
}
int main(){
    int n;
    scanf("%d", &n);
    memset(h, 0x3f, sizeof h); // 按照字节来memset，memset中设为-1的话：一个字节中的每一位就都是1
    while(n --){
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        int k = find(x);
        if(*op == 'I') h[k] = x;
        else{
            if(h[k] != null) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

strcpy() 复制字符串时候是遇到 \0 停止

字符串哈希方式

一个比较重要的哈希方式，特殊的哈希方式！

字符串前缀哈希法

预处理出来所有前缀的哈希

image-20250221093020166

两个问题：

  1. 如何定义某个前缀的哈希值？

    把字符串看成是一个P进制的数！把P进制的数转化为十进制的数，把字符串转化成数字，但数字可能会很大，所以最后求得的数字要取模Q，这样就能把任何一个字符串映射到 0 ~ Q-1 之间的一个数

    image-20250221093836478

    注意：① 一般情况下不能将某个字母映射成0，因为比如A是0，那么AA也是0，可能会产生冲突！

    ​ ② 假定RP足够好，不存在冲突，经验值为P取131或13331时，Q取2^64，这么取的话 在99.9%的情况下不存在冲突！

  2. 如何求得任意字串的哈希值？

    从L到R这一段的哈希值的 求法如下图：

    image-20250221094410894

    h[R] - h[L] * P^(R- L + 1)

    用 unsigned long long 来存储所有的哈希值h，这样就不需要取模了，溢出就相当于取模！

    h(i) = h(i - 1) * P + str[ i ]

字符串哈希例题：

image-20250221094718474

首先把源字符串所有前缀的哈希值求出来，当想用到哪个区间时再求该区间的哈希值！

很多时候特别困难的字符串题目，当我们需要快速判断两个字符串是否相等的时候，都可以用字符串哈希来做！KMP的劲敌！但有些问题只能用KMP来做，比如KMP可以求循环节，除了这个之外，好像KMP就完全不如字符串哈希了！

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
#include <iostream>
using namespace std;
typedef unsigned long long ULL;
const int N = 1e5 + 10, P = 131; // P取131或13331就可以
int n, m;
char str[N];
ULL h[N], p[N]; // h数组表示某一个前缀的哈希值，p数组表示某一位的哈希值！
ULL get(int l, int r){
    return h[r] - h[l - 1] * p[r - l + 1];
}
int main(){
    scanf("%d%d%s", &n, &m, str + 1);
    p[0] = 1;
    for(int i = 1; i <= n; i ++){
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + str[i];
    }
    while(m --){
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if(get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}

C++ STL使用技巧

接下来是C++语法课内容，STL中有很多已经实现的数据结构，可以直接拿来用

很早前算法竞赛有人用C或PASCAL，现在这两种语言在算法竞赛都已经销声匿迹了，主要是因为C++的STL非常方便，有很多实现好的数据结构

vector——变长数组，倍增的思想

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 <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
// size(), empty(), clear(), front(), back(), push_back(), pop_back()
// 迭代器: begin(), end()   a.begin() = a[0], a.end() = a[a.size()]
// vector支持随机寻址，和数组一样，vector[i]
// vector支持比较运算！按字典序
using namespace std;
int main(){
    vector<int> a(10, 3); // 定义一个长度为10的vector，并且里面每个数都是3
    vector<int> a[10]; // 定义一个vector数组，里面包含10个vector
    a.size(); // 返回vector里的元素个数
    a.empty(); // 返回vector是否为空
    // 以上两个操作时间复杂度为O(1)，所有容器都有这两个函数
    a.clear(); // 清空vector，并不是所有容器都有这个函数
    a.front(); // 返回vector第一个数
    a.back(); // 返回vector最后一个数
    a.push_back(val); // 向vector最后插入一个数val
    a.pop_back(); // 将vector最后一个数删掉
    a.begin(); // vector第0个数
    a.end() // vector最后一个数的后面一个数
    
    vector<int> b;
    for(int i = 0; i < 10; i ++) b.push_back(i);
    
    // 三种遍历vector方式
    for(int i = 0; i < b.size(); i ++) cout << b[i] << ' ';
    cout << endl;
    
    for(vector<int>::iterator i = b.begin(); i != b.end(); i ++) cout << *i << ' ';
    cout << endl;
    
    for(auto x: b) cout << x << ' ';
    cout << endl;
    
    // 支持比较运算
    vector<int> a(4, 3), b(3, 4);
    if(a < b) cout << "a < b"; // 会打印输出
    return 0;
}

操作系统为某个程序/进程分配空间时，所需的时间与空间大小无关，与申请次数有关

正因有这个特点，因此变长数组vector要有倍增的特点

因此一开始分配一个长度不大（32）的空间，当元素个数大于32时，再申请一个长度64的空间，再把之前的元素copy过来，以此类推每次倍增！

因此申请长度为n的数组，时间复杂度为O(logn)，而且额外copy的次数是O(1)的

pair<int, int>——存储二元组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
// pair前后的两个数据类型可以任意
// first(), second();
// 支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
// make_pair()
using namespace std;
int main(){
    pair<int, string> p;
    pair<int, pair<int, int>> q;
    p = make_pair(10, "yxc");
    p = {20, "abc"};
    return 0;
}

string——字符串，substr(), c_str()

C++把字符串进行了封装！字符数组来存不方便，string存字符串较为方便

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
// size(), empty(), clear(), length()   size和length都是返回字符串长度
// substr(l, r) 返回从下标l开始长度为r的子串，当长度很大超出字符串总长度时，只输出到字符串结尾为止，当第二个参数缺省时，输出从下标l到结尾为止
// c_str() 返回存储字符串的字符数组的起始地址
using namespace std;
int main(){
    string a = "yxc";
    a += "def";
    a += 'c';
    cout << a << endl;
    cout << a.substr(1, 2) << endl;
    printf("%s\n", a.c_str()); // 如果想要输出字符串a，其实就是输出字符数组的起始地址，用a.c_str()返回存储字符串a的字符数组起始地址
    return 0;
}

queue——队列,push(), front(), pop(), priority_queue（优先队列，即堆）,push(), top(), pop()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
// 队列是 向队尾插入，队头弹出 的先入先出的数据结构
// size(), empty(), queue、priority_queue、stack都没有clear()这个函数！
// push() 向队尾插入一个元素
// front() 返回队头元素
// back() 返回队尾元素
// pop() 弹出队头元素

using namespace std;
int main(){
    queue<int> q;
    q = queue<int>(); // 想要去清空一个queue时，可以这样重新构造 
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
// 优先队列，其实就是堆，默认是大根堆
// size(), empty(), queue、priority_queue、stack都没有clear()这个函数！
// push() 向堆中插入一个元素
// top() 返回堆顶元素
// pop() 弹出堆顶元素

using namespace std;
int main(){
    priority_queue<int> heap;
    // 定义小根堆的方式：
    // 1. 向堆中插入元素的时候插入相反数
    // 2. 定义时直接定义为小根堆
    priority_queue<int, vector<int>, greater<int>> heap; // 定义小根堆
    
    return 0;
}

stack——栈, push(), top(), pop()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <stack>
// size(), empty(), queue、priority_queue、stack都没有clear()这个函数！
// push() 向栈顶插入一个元素
// top() 返回栈顶元素
// pop() 弹出栈顶元素
using namespace std;
int main(){
    
    return 0;
}

deque——双端队列（队头队尾都可以插入删除，可以支持随机访问）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <deque>
// deque是一个加强版的vector
// size(), empty(), clear()
// front()指队首, back()指队尾
// push_back(), pop_back()
// push_front(), pop_front()
// begin(), end()
// 支持随机寻址，deque比一般容器慢好几倍
using namespace std;
int main(){
    
    return 0;
}

set, map, multiset, mutimap——基于平衡二叉树（红黑树），动态维护有序序列

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
// 所有
// size(), empty(), clear(), 
// begin(), end() ++,-- 返回前驱和后继，时间复杂度 O(logn)

// set 和 multiset
// set里不能有重复元素，如果添加重复元素，则该操作会被忽略掉；multiset里可以有重复元素
// set和multiset里面都支持：
// insert()插入一个数
// find()查找一个数，如果不存在返回end()迭代器
// count()，返回某一个数的个数
// erase(): erase(i) 输入一个数x，则删除所有x；输入一个迭代器，删除这个迭代器，时间复杂度 O(k + logn)，k是x的个数
// ⭐核心操作：lower_bound()返回大于等于x的最小的数的迭代器, upper_bound返回大于x的最小的数的迭代器，如果不存在则返回end

// map 和 multimap
// insert() 插入的数是一个pair
// erase() 输入的参数是pair或者迭代器
// find() 
// [] map可以像数组一样随机寻址，但是时间复杂度为 O(logn)
// ⭐核心操作：lower_bound()返回大于等于x的最小的数的迭代器, upper_bound返回大于x的最小的数的迭代器，如果不存在则返回end
using namespace std;
int main(){
    set<int> S;
    multiset<int> MS;
    map<string, int> a;
    a["yxc"] = 1;
    cout << a["yxc"] << endl;
    return 0;
}

unordered_set, unordered_map, unordered_multiset, unordered_mutimap（基于哈希表实现）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
// 和上面类似，增删改查的时间复杂度是 O(1)
// 但不支持 lower_bound()和upper_bound()
// 不支持迭代器的 ++、--

using namespace std;
int main(){
    unordered_multimap<string, int> a;
    
    return 0;
}

bitset（状态压缩，压位）

如果我们想开一个长度为1024的布尔数组（C++中bool类型长度为一字节）

占用空间为：1024B = 1KB

如果我们压位的话只需要：1024/8 = 128B，即将一个字节压到一位里，占用空间是原来的1/8

应用：存一个10000*10000的布尔矩阵，如果采用布尔变量来存就需要10^8B，也就是100MB的空间，此时题目要求控制在64MB内，就可以采用bitset来存，节省空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <bitset>
// bitset<10000> S;
// 支持所有位运算操作，例如 取反~s，与运算&，或运算|，异或运算^
// 支持移位操作，>>，<<，==，!=
// 支持[]操作符，可以取出来某一位是0或1
// 支持count()，返回有多少个1
// any()，判断是否至少有一个1
// none()，判断是否全为0
// set()，把所有位 置成1
// set(k, v)，将第k位变成v
// reset()，将所有位变成0
// flip()，把所有位取反，等价于~运算符
// flip(k)，把第k位取反

习题课

单链表

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 <algorithm>
using namespace std;
const int N = 1e5 + 10;
int head, e[N], ne[N], idx;
void init(){
    head = -1;
    idx = 0; // 可不写，全局变量默认是0
}
void add_head(int x){
    e[idx] = x, ne[idx] = head, head = idx ++;
}
void add_k(int k, int x){
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++; 
}
void remove(int k){
    ne[k] = ne[ne[k]];
} 
int main(){
    init();
    int m;
    cin >> m;
    while(m --){
        char op;
        int k, x;
        cin >> op; // cin读字符会过滤空格和回车，scanf读字符不会自动过滤
        if(op == 'H'){
            cin >> x;
            add_head(x);
        }
        else if(op == 'I'){
            cin >> k >> x;
            add_k(k - 1, x);
        }
        else {
            cin >> k;
            if(!k) head = ne[head]; // 如果删除的点是头节点
            else remove(k - 1); 
        }
    }
    for(int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
    cout << endl;
    
    return 0;
}

补充知识：循环链表

循环链表一般来说是 循环双链表，单链表很少有循环的，一般情况下指的并不是一道题只考链表，而是一道题里面需要链表来做优化

循环双链表的定义：双链表的基础上，头节点的pre指向尾节点，尾节点的next指向头节点

双链表

双链表和单链表不同，单链表有head = -1，双链表让0号点表示左侧，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
54
55
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int e[N], l[N], r[N], idx;
void init(){
    r[0] = 1;
    l[1] = 0;
    idx = 2; // 0和1已经被用过了，因此idx从2开始
}
void add(int k, int x){
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx; // 这行和下面一行一定不要反着写！
    r[k] = idx;
    idx ++;
}
void remove(int k){
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}
int main(){
    init(); // 记得调用初始化！
    int m;
    cin >> m;
    while(m --){
        string op;
        int k, x;
        cin >> op;
        if(op == "L"){
            cin >> x;
            add(0, x);
        }
        else if(op == "R"){
            cin >> x;
            add(l[1], x);
        }
        else if(op == "D"){
            cin >> k;
            remove(k + 1);
        }
        else if(op == "IL"){
            cin >> k >> x;
            add(l[k + 1], x);
        }
        else {
            cin >> k >> x;
            add(k + 1, x);
        }
    }
    for(int i = r[0]; i != 1; i = r[i]){ // 双链表里没有空指针一说，因此终止条件应该为i != 1
        cout << e[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 <cstring>
#include <algorithm>
#include <stack>
#include <unordered_map>

using namespace std;
const int N = 1e5 + 10;
stack<int> num;
stack<char> op;

void eval(){
    auto b = num.top(); num.pop();
    auto a = num.top(); num.pop();
    auto c = op.top(); op.pop();
    int x;
    if(c == '+') x = a + b;
    else if(c == '-') x = a - b;
    else if(c == '*') x = a * b;
    else x = a / b;
    num.push(x);
}

int main(){
    unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    char str[N];
    cin >> str;
    int n = strlen(str);
    for(int i = 0 ; i < n; i ++){
        auto c = str[i];
        if(isdigit(c)){
            int x = 0, j = i;
            while(j < n && isdigit(str[j]))
                x = x * 10 + str[j ++] - '0';
            i = j - 1;
            num.push(x);
        }
        else if(c == '(') op.push(c);
        else if(c == ')'){
            while(op.top() != '(') eval();
            op.pop();
        }
        else{
            while(op.size() && pr[op.top()] >= pr[c]) eval();
            op.push(c);
        }
    }
    while(op.size()) eval();
    cout << num.top() << endl;
    return 0;
}

单调栈

思路：先考虑暴力是如何做的，再从中挖掘单调性，最后利用单调性做优化求解

单调栈常见的有一种题型：

给定一个序列，求一下这个序列中的每一个数 左边（右边）离它最近的且比它本身大（小）的数 在什么地方？

例如：3 4 2 7 5 求每个数左边离它最近 且比它本身小的数 是多少 若没有返回-1

ans：-1 3 -1 2 2

先考虑暴力做法是什么，再挖掘一些性质，可以把目光集中到较小的状态，使得时间复杂度降低

暴力做法： 时间复杂度O(n^2)

1
2
3
4
5
6
7
8
for(int i = 0; i < n; i ++){
	for(int j = i - 1; j >= 0; j --){
		if(a[i] > a[j]){
			cout << a[j] << " " << endl;
			break;
		}
	}
}

优化：可以用一个栈来存储该 a[i] 左边的所有元素 时间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int stk[N], tt;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 0; i < n; i ++){
        int x;
        cin >> x;
        while(tt && stk[tt] >= a[i]) tt --;
        if(tt) cout << stk[tt] << ' ';
        else cout << -1 << ' ';
        stk[++ tt] = x;
    }
    return 0;
}

在本题跑的时间中 cin 和 cout 要比 scanf printf 慢10倍左右

单调队列

应用：求滑动窗口里的最大值（最小值）！

可以用单调队列优化的最典型模型

先考虑暴力做法是什么，再挖掘一些性质，可以把目光集中到较小的状态，使得时间复杂度降低

窗口可以用队列来维护

先考虑用栈和队列暴力模拟遍历所有元素，再看栈和队列里哪些元素没有用，再看剩下的元素是否有单调性，再利用单调性优化

拿数组来模拟 stl 会更快

99%情况下C++是不会开O(2)优化，stl 容器某些情况下会慢一些

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>
using namespace std;
const int N = 1e6 + 10;
int n, k;
int a[N], q[N];
int main(){
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
    // 求最小值
    int hh = 0, tt = -1;
    for(int i = 0; i < n; i ++){
        // 判断队头是否已经滑出窗口
        if(hh <= tt && i - k + 1 > q[hh]) hh ++;
        while(hh <= tt && a[q[tt]] >= a[i]) tt --;
        q[++ tt] = i;
        if(i >= k - 1) printf("%d ", a[q[hh]]); 
    }
    puts("");
    
    // 求最大值
    hh = 0, tt = -1;
    for(int i = 0; i < n; i ++){
        // 判断队头是否已经滑出窗口
        if(hh <= tt && i - k + 1 > q[hh]) hh ++;
        while(hh <= tt && a[q[tt]] <= a[i]) tt --;
        q[++ tt] = i;
        if(i >= k - 1) printf("%d ", a[q[hh]]); // 输出队头即为最大值
    }
    puts("");
    
    return 0;
}

最大异或对

本题为Trie树的应用

image-20250222182206120

先给出暴力做法，再想如何优化暴力做法

1
2
3
4
5
6
int res = 0;
for(int i = 0; i < n; i ++){ // 枚举第一个数
    for(int j = 0; j < i; j ++){ // 枚举第二个数，异或运算满足交换律，因此这里默认第二个数下标比第一个小，第二个数下标枚举到j结束
        res = max(res, a[i] ^ a[j]);
    }
}

可以用Trie树这个数据结构将内层循环做优化，第二层循环是枚举从a0到a(i-1)，可以用Trie来优化

在题干中有Ai<2^31 每一个数都可以看做是长度为31位的二进制数，想要结果越大，肯定是高位越大，从左往右考虑，应该每一位都尽量和当前的这个数的该位不一样，这样得到的异或值就是最大化的

image-20250222195142383

C++ 一秒内大概可以计算 10^7 ~ 10^8 次运算，因此优化算法，使时间复杂度降低

核心思想：Trie树不光可以存取字符串，也可以存取整数、二进制数！

先查找异或的最大值，再将该数的二进制数插入到Trie树中

image-20250222200851198

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 <algorithm>
using namespace std;
const int N = 1e5 + 10, M = 31 * N; // 31个数，每个数最大10万
int n;
int a[N];
int son[M][2], idx;
void insert(int x){
    int p = 0;
    for(int i = 30; i >= 0; i --){
        int u = x >> i & 1;
        if(!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
}
int query(int x){
    int p = 0, res = 0;
    for(int i = 30; i >= 0; i --){
        int u = x >> i & 1;
        if(son[p][!u]){
            p = son[p][!u];
            res = res * 2 + !u;
        }
        else{
            p = son[p][u];
            res = res * 2 + u;
        }
    }
    return res;
}
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
    int res = 0;
    for(int i = 0; i < n; i ++){
        insert(a[i]); // 先插入再查询，避免Trie树是空的判断
        int t = query(a[i]);
        res = max(res, a[i] ^ t);
    }
    printf("%d\n", res);
    return 0;
}

食物链

本题考察 并查集，源自**《算法竞赛进阶指南》** 题目描述如下：

image-20250223202003599

image-20250223202227937

大致有两种做法：这里采用 用并查集维护信息 这种做法

假话条件中的2和3较好判断，1较难判断！

根据题意可以 根据前面两类A吃B、B吃C，提前推断出最后一种C吃A

并查集里面每一个集合是一个树的形式！记录每个点和根节点之间的关系，就知道任意两个点之间的关系！

每个点到根节点的距离来表示它和根节点之间的关系

如果一个节点到根节点距离为1：则它被根节点吃

如果一个节点到根节点距离为2：则它吃根节点

如果一个节点到根节点距离为3：则它和根节点为同类

所有点到根节点的距离模3取余对应这三种情况：

image-20250223203518634

余2的点可以吃余1的点，1吃0，0吃2，这就是并查集维护的关系：维护该节点到根节点的距离！

根节点是第0代，吃第0代的就是第1代，吃第1代的就是第2代，吃第2代的就是第3代，第3代就和第0代同类了！代就是模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
#include <iostream>
using namespace std;
const int N = 5e4 + 10;
int n, m;
int p[N], d[N];
int find(int x){ // 返回该节点x的祖宗节点
    if(p[x] != x) { // 如果x不是树根的话
        int t = find(p[x]);
        d[x] += d[p[x]]; // d[x] 需要更新为他到根节点的距离
        p[x] = t;
    }
    return p[x];
}
int main(){
    scanf("%d%d%", &n, &m);
    for(int i = 1; i <= n; i ++) p[i] = i;
    int res = 0;
    while(m --){
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);
        
        if(x > n || y > n) res ++;
        else{
            int px = find(x), py = find(y);
            if(t == 1){
                if(px == py && (d[x] - d[y]) % 3) res ++;
                else if(px != py){
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }
            }
            else {
                if(px == py && (d[x] - d[y] - 1) % 3) res ++;
                else if(px != py){
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }
    printf("%d\n", res);
    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
61
62
63
64
65
66
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = 1e5 + 10;
int n, m;
// ph[k]存的是第k个插入的点是哪个（在堆里的下标） 下标映射到堆
// hp[k]存的是堆里的第k个点是第几个插入的（插入的顺序）  堆映射到下标
int h[N], ph[N], hp[N], size;
void heap_swap(int a, int b){
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);    
}
void down(int u){
    int t = u; // t表示三个点里的最小值
    if(u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if(u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if(u != t){ // u不是最小值，即需要更换的话
        heap_swap(u, t);
        down(t);
    }
}
void up(int u){
    while(u / 2 && h[u / 2] > h[u]){ // u有父节点并且u的父节点比它本身大
        heap_swap(u / 2, u);
        u /= 2;
    }
}
int main(){
    int n, m = 0;
    scanf("%d", &n);
    while(n --){
        char op[10];
        int k, x;
        scanf("%s", op);
        if(!strcmp(op, "I")){
            scanf("%d", &x);
            size ++;
            m ++;
            ph[m] = size, hp[size] = m;
            h[size] = x;
            up(size);
        }
        else if(!strcmp(op, "PM")) printf("%d\n", h[1]);
        else if(!strcmp(op, "DM")){
            heap_swap(1, size);
            size --;
            down(1);
        }
        else if(!strcmp(op, "D")){
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, size);
            size --;
            down(k), up(k);
        }    
        else {
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x;
            down(k), up(k);
        }
    }
    return 0;
}

第三讲——搜索与图论

图论中最常考的：① 最短路 ② 最小生成树

图论主要学习方法：描述算法思路流程，来巧记模板

DFS 与 BFS

从数据结构来看，DFS用的是栈，BFS用的是队列

从空间来看，DFS O(h)（与树高相关），BFS O(2^h)

BFS第一次拓展到的点一定是最近的点，因此其有”最短路“的特点，DFS不具有最短性

凡是算法、思路比较奇怪，对空间要求较高的，都是DFS，凡是最短的，都是BFS

深度优先搜索 DFS

尽可能往深搜，搜到叶节点或当前子树搜完了 就回溯到上一个父节点

每一个DFS一定对应一棵搜索树，DFS俗称暴搜，一定要注意遍历的顺序！

排列数字

深搜经典题目 排列数字：按顺序输出1~n全排列结果

image-20250224104447775

下图为搜索过程：

image-20250224105039435

DFS搜索顺序可以看作一棵树！回溯时注意恢复现场！DFS就是把所有情况搜一遍！

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>
using namespace std;
const int N = 10;
int n;
int path[N];
bool st[N]; // 开一个布尔数组存储路径上哪些点被用过了，true代表被用过了
void dfs(int u){
    if(u == n){ // 最后一层，即为叶节点！
        for(int i = 0; i < n; i ++) printf("%d ", path[i]);
        puts("");
        return;
    }
    for(int i = 1; i <= n; i ++){
        if(!st[i]){ // 这个数没有被用过
            path[u] = i;
            st[i] = true;
            dfs(u + 1);
            // 以下操作用于恢复现场
            // path[u] = 0; // 这句话可以删去，因为每次循环path[u]上的数会被覆盖掉
            st[i] = false;
        }
    }
}
int main(){
    cin >> n;
    dfs(0);
    return 0;
}

n-皇后问题

image-20250224110754317

image-20250224110926421

第一种搜索顺序：像全排列那样，每一行都要放一个皇后且只能放一个皇后，因此就一行一行来看

剪枝：当前子树一定不合法，不需要接着往下搜了，提前结束搜索并回溯（最优性剪枝和可行性剪枝）

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
#include <iostream>
using namespace std;
const int N = 20;
int n;
char g[N][N];
bool col[N], dg[N], udg[N]; // dg存储正对角线，udg存储反对角线
void dfs(int u){
    if(u == n){
        for(int i = 0; i < n; i ++) puts(g[i]);
        puts("");
        return;
    }
    for(int i = 0; i < n; i ++){
        if(!col[i] && !dg[u + i] && !udg[n - u + i]){ // (u, i)这个点，y = x + b和 y = -x + b中截距的两种表达式：y - x和y + x，y - x有可能是负数，所以要加上个偏移量
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - u + i] = true;
            dfs(u + 1);
            // 以下操作用于恢复现场
            col[i] = dg[u + i] = udg[n - u + i] = false;
            g[u][i] = '.';
        }
    }
}
int main(){
    cin >> n;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            g[i][j] = '.';
    dfs(0);
    return 0;
}

第二种搜索顺序：

我们也可以用一种更原始的方式来枚举八皇后问题：一个格子一个格子地枚举

image-20250224134223375

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
#include <iostream>
using namespace std;
const int N = 20;
int n;
char g[N][N];
bool row[N], col[N], dg[N], udg[N]; // dg存储正对角线，udg存储反对角线
void dfs(int x,int y, int s){
    if(y == n) y = 0, x ++; // 如果当前到达行末了，需要转行开始枚举下一行
    if(x == n){ // 如果当前枚举的是最后一行
        if(s == n){ // 如果摆的皇后个数等于n，说明找到了解
            for(int i = 0; i < n; i ++) puts(g[i]);
            puts("");
        }
        return;
    }
    // 不放皇后
    dfs(x, y + 1, s);
    // 放皇后
    if(!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]){
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
        dfs(x, y + 1, s + 1);
        // 以下步骤为恢复现场
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
        g[x][y] = '.';
    }
}
int main(){
    cin >> n;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            g[i][j] = '.';
    dfs(0, 0, 0);
    return 0;
}

宽度优先搜索 BFS

尽可能往宽搜，一层搜完搜一层，宽搜优势：可以搜到最短路（图中边的权重都一致）

宽搜模板如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size())
{
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

走迷宫：

DP问题和最短路问题是互通的，DP问题可以看成是特殊的最短路问题，最短路问题包含DP问题，DP问题是没有环的最短路问题

image-20250224140900564

深搜没有常用框架，宽搜有常用框架，所有边权都是1时，才可以用BFS求解最短路

image-20250224141816797

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
#include <iostream>
#include <cstring>
#include <algorithm>
// #include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int n, m;
int g[N][N]; // g数组存图
int d[N][N]; // d数组存每个点到起点的距离
PII q[N * N], Prev[N][N]; // Prev记录路径
int bfs(){
    int hh = 0, tt = 0;
    q[0] = {0, 0};
    memset(d, -1, sizeof d);
    d[0][0] = 0;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; // 用向量来表示四个方向的点
    while (hh <= tt){ // 当队列不空
        auto t = q[hh ++]; // 取出队头
        for(int i = 0; i < 4; i ++){
            int x = t.first + dx[i], y = t.second + dy[i];
            if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1){ // 该点第一次被搜到
                d[x][y] = d[t.first][t.second] + 1;
                Prev[x][y] = t;
                q[++ tt] = {x, y};
            }
        }
    }
    int x = n - 1, y = m - 1;
    while(x || y){
        cout << x << ' ' << y << endl;
        auto t = Prev[x][y];
        x = t.first, y = t.second;
    }
    return d[n - 1][m - 1];
}
int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            cin >> g[i][j];
    cout << bfs() << endl;
    return 0;
}

树与图的遍历：拓扑排序

树与图的存储

树是一种特殊的图，无环且连通的图

图分为有向图和无向图，因此算法题中无向图看成特殊的有向图，每条边看作两条有向边

有向图的存储分为两大类，邻接矩阵g[a, b]存储a到b的信息，有重边的话邻接矩阵无法存储

用的最多的是邻接表，即每个点开一个单链表，n个点每个点上都有一个单链表，每个点上的单链表存的是这个点可以走到哪个点，单链表内部次序是无关紧要的。插节点的时候选择在该单链表上头插法

image-20250224144331589

树和图的存储模板如下：采用邻接表的形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, M = N * 2;
// n个单链表，所以这里对应n个head，也就是h[N]
int h[N], e[M], ne[M], idx;
void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}
int main(){
    memset(h, -1, sizeof h); // 链表初始化，让n个头节点都指向-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 <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, M = N * 2;
// n个单链表，所以这里对应n个head，也就是h[N]
int h[N], e[M], ne[M], idx;
bool st[N];
void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}
void dfs(int u){
    st[u] = true; // 标记一下，该节点被搜过了
    for(int i = h[u]; i != -1; i = ne[i]){ // 遍历该节点的所有出边
        int j = e[i]; // j表示该节点出边指向的节点编号
        if(!st[j]) dfs(j); // 如果j没被搜过，则递归搜索
    }
}
int main(){
    memset(h, -1, sizeof h); // 链表初始化，让n个头节点都指向-1
    dfs(1)
}

例题如下：

树的重心：

image-20250224150903087

思路：依次枚举，对于每个点都求一遍最大的子树节点数目；如何快速求出该值：深搜可以快速知道每个子树的点数量！

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 <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, M = N * 2;
// n个单链表，所以这里对应n个head，也就是h[N]
int n;
int h[N], e[M], ne[M], idx;
bool st[N];
int ans = N;
void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}
int dfs(int u){ // 以u为根的子树中点的数目
    st[u] = true; // 标记一下，该节点被搜过了
    int sum = 1, res = 0; // sum存的是当前子树的大小，res存的是删除该点后每个连通块中点数目的最大值
    for(int i = h[u]; i != -1; i = ne[i]){ // 遍历该节点的所有出边
        int j = e[i]; // j表示该节点出边指向的节点编号
        if(!st[j]){
            int s = dfs(j); // 用s来表示当前子树的大小，如果j没被搜过，则递归搜索
            res = max(res, s);
            sum += s;
        } 
    }
    res = max(res, n - sum);
    ans = min(ans, res);
    return sum;
}
int main(){
    cin >> n;
    memset(h, -1, sizeof h); // 链表初始化，让n个头节点都指向-1
    for(int i = 0; i < n - 1; i ++){
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    dfs(1); // 这里从哪个点开始搜结果都是一样的
    cout << ans << endl;
    return 0;
}

树与图的宽度优先遍历

例题如下：

图中点的层次

image-20250224154011545

所有边的长度都为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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N], q[N];
void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}
int bfs(){
    int hh = 0, tt = 0;
    q[0] = 1;
    memset(d, -1, sizeof d);
    d[1] = 0;
    while(hh <= tt){
        int t = q[hh ++];
        // 扩展每个点的邻边
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(d[j] == -1){
                d[j] = d[t] + 1;
                q[++ tt] = j;
            }
        }
    }
    return d[n];
}
int main(){
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i ++){
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    cout << bfs() << endl;
    return 0;
}

拓扑排序

图的宽搜经典应用：求图的拓扑序列，拓扑序列是针对有向无环图来说的，无向图没有拓扑序这一说

一个有向无环图一定存在拓扑序列的，有向无环图也被称作拓扑图，入度为0的点才可以作为拓扑序列的起点

有向无环图至少存在一个入度为0的点，选择入度为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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N], q[N]; // d代表该顶点的入度大小
void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}
bool topsort(){
    int hh = 0, tt = -1;
    for(int i = 1; i <= n; i ++){
        if(!d[i]) // 如果该节点入度为0
            q[++ tt] = i;
    }
    while(hh <= tt){
        int t = q[hh ++];
        for(int i = h[t] ; i != -1; i = ne[i]){
            int j = e[i];
            d[j] --;
            if(d[j] == 0) q[++ tt] = j;
        }
    }
    return tt == n - 1; // 如果所有点都入队了，那么就是一个有向无环图
}
int main(){
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i ++){
        int a, b;
        cin >> a >> b;
        add(a, b);
        d[b] ++;
    }
    if(topsort()){ // 拓扑排序
        for(int i = 0; i < n; i ++) printf("%d ", q[i]);
        puts("");
    }
    else puts("-1");
    return 0;
}

最短路

常见的最短路问题可以分为两大类（有向图）：

单源最短路：求从一个点到其它所有点的最短距离，求完后显然从1号点到n号点最短路就出来了

可分为以下两大类 ( 图中 n 表示点的数量，m 表示边的数量) （稠密图指的是 m 与 n^2 一个级别，稀疏图指的是 m 和 n 一个级别）

稠密图用邻接矩阵来存，稀疏图用邻接表来存

​ a. 所有边权都是正数------朴素Dijkstra算法 O(n^2)（与边数无关，适合稠密图）堆优化版的Dijkstra算法 O(mlogn)（适合稀疏图）

​ b. 存在负权边------Bellman-Ford O(nm)，SPFA 一般是O(m) 最坏O(nm) （Bellman-Ford的优化）

如果对最短路边数做了限制，那么只能用Bellman-Ford

多源汇最短路：（源点即起点，汇点即终点）起点和终点都是不确定的，所以叫多源汇最短路，Floyd算法 O(n^3)

image-20250303135342562

最短路算法考题的难点在于建图，而不是在于验证算法正确性！（如何把原问题抽象成最短路问题，如何定义点和边）

Dijkstra算法基于贪心，Floyd算法基于动态规划，Bellman-Ford算法（贝尔曼福特算法）基于离散数学的知识

图论里的问题侧重于抽象，而不是算法原理！

朴素Dijkstra算法——稠密图 (邻接矩阵来存)

1.初始化距离每个点一个dis，dis[1] = 0, 其它所有点的 dis[i] = ∞，初始化集合S存放当前已经确定最短距离的点

2.for(i : 0 ~ n) 找到不在S中的距离最近的点 -> t , 把 t 加到 S 中去，用 t 更新其它点的距离（看一下 dis[x] 是不是 大于 dis[t] + 权重 w ）

第二步的过程迭代n次，就能得到每个点的最短路了

image-20250303142236034

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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 510;

int n, m;
int g[N][N]; // 稠密图用邻接矩阵来存
int dist[N];
bool st[N];

int dijkstra(){
	memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int i = 0; i < n; i ++){
        int t = -1;
        for(int j = 1; j <= n; j ++)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j; // 在所有st为false的点中找到dist最小的点 赋值给t
        
        if(t == n) break; // 优化
        
        st[t] = true;
        
        for(int j = 1; j <= n; j ++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    // 本题中存在重边，如果有重边，只需要保留距离最短的那条边
    memset(g, 0x3f, sizeof g);
    while(m --){
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);
    }
    cout << dijkstra();
    return 0;
}

算法题追求的是让自己看得懂；工程化追求的是让别人看得懂，而且日后好维护与修改

堆优化版的Dijkstra算法——稀疏图(邻接表来存)

for(i : 0 ~ n) 找到不在S中的距离最近的点 -> t

这一步中找到距离最近的点：可以用堆来快速找到该点并更新 t 到其它点的距离，实现从 O(n^2) 到 O(mlogn) 的优化

堆有两种方法实现：1.手写堆（n个数） 2.优先队列来做（m个数），优先队列不支持修改任意一个元素 都是O(mlogn)

所以堆优化的Dijkstra是不需要手写堆的，可以用优先队列

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 1.5e5 + 10;

int n, m;
int h[N], e[N], ne[N], w[N], dist[N], idx;
bool st[N];

void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int dijkstra(){
	memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    priority_queue<PII, vector<PII>, greater<PII>> heap; // 定义小根堆
    heap.push({0, 1});
    
    while(heap.size()){
        auto t = heap.top();
        heap.pop();
        
        int ver = t.second, distance = t.first; // ver代表节点编号，distance表示距离
        if(st[ver]) continue;
        st[ver] = true;
        
        for(int i = h[ver]; i != -1; i = ne[i]){
            int j = e[i];
            if(dist[j] > distance + w[i]){
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    // 本题中存在重边，如果有重边，只需要保留距离最短的那条边
    memset(h, -1, sizeof h);
    while(m --){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    cout << dijkstra() << endl;
    return 0;
}

Bellman-Ford算法

迭代 n 次，每次循环所有边 a, b, w，表示存在一条从 a 指向 b 的边，权重为 w

定义专门存储边的结构体 edge[M]

1
2
3
struct{
    int a, b, w;
} edge[M];

遍历所有边的时候，更新就可以了，dist[b] = min(dist[b], dist[a] + w); 更新的过程叫 松弛操作

image-20250303205905371

三角不等式：dist[b] <= dist[a] + w 如果图中有负权回路，则该图中最短路是不存在的！

Bellman-Ford算法可以求出是否有负权回路的！时间复杂度 O(nm)

有边数限制的最短路，则用Bellman-Ford算法

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 <algorithm>
#include <cstring>

using namespace std;

const int N = 5e2 + 10, M = 1e4 + 10;
int n, m, k;
int dist[N], backup[N];

struct Edge{
    int a, b, w;
}edges[M];

int bellman_ford(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int i = 0; i < k; i ++){
        memcpy(backup, dist, sizeof dist); // backup里存的是上一次迭代的结果，防止串联现象
        for(int j = 0; j < m; j ++){
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            dist[b] = min(dist[b], backup[a] + w);
        }
    }
    if(dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}    
    
int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m >> k;
    for(int i = 0; i < m; i ++){
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }
    int t = bellman_ford();
    if(t == -1 && dist[n] != -1) puts("impossible");
    else cout << t << endl;
    return 0;
}

SPFA算法

其实大部分正权图问题用SPFA算法也可以做，有很多都可以用这个算法来过掉！大概类似的网格结构图可能会卡SPFA。

用SPFA算法则一定要求图不含负环！只要没有负环就可以用SPFA算法，99.9%的最短路问题没有负环。

Bellman-Ford算法遍历所有边，但并不是所有边都要被更改，SPFA就是在这个点上用宽搜进行优化

SPFA求最短路问题代码如下：

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 150010;

int n, m;
int h[N], e[N], ne[N], w[N], idx; // 用 w 来表示权重
int dist[N];
bool st[N]; // st数组存的是当前这个点是不是在队列中，防止队列中存重复的点

void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int spfa(){
	memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    queue<int> q;
    q.push(1);
    st[1] = true;
    
    while(q.size()){
        int t = q.front();
        q.pop();
        st[t] = false;
        
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(dist[j] > dist[t] + w[i]){
                dist[j] = dist[t] + w[i];
                if(!st[j]){
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    // 本题中存在重边，如果有重边，只需要保留距离最短的那条边
    memset(h, -1, sizeof h);
    while(m --){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    int t = spfa();
    if(t == -1 && dist[n] != -1) puts("impossible");
    else cout << t << endl;
    return 0;
}

SPFA判断负环问题代码如下（SPFA算法判断负环时间复杂度还是蛮高的）：

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 150010;

int n, m;
int h[N], e[N], ne[N], w[N], idx; // 用 w 来表示权重
int dist[N], cnt[N];
bool st[N]; // st数组存的是当前这个点是不是在队列中，防止队列中存重复的点

void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int spfa(){
    queue<int> q;
    for(int i = 1; i <= n; i ++){
        st[i] = true;
        q.push(i);
    }
    
    while(q.size()){
        int t = q.front();
        q.pop();
        st[t] = false;
        
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(dist[j] > dist[t] + w[i]){
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                
                if(cnt[j] >= n) return true; // 由抽屉原理推导可得有负权环的条件
                if(!st[j]){
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while(m --){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    if(spfa()) puts("Yes");
    else puts("No");
    return 0;
}

Floyd算法

Floyd算法非常简单，用于求解多源汇最短路问题，基于动态规划

邻接矩阵d[ i , j ]来存储图中所有的边，三重循环后可以把 邻接矩阵 变成 存放最短距离 的矩阵

image-20250304105755802

可以处理负权，但不能有负权回路

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 <algorithm>
#include <cstring>

using namespace std;
const int N = 210, INF = 1e9;

int n, m, Q;
int d[N][N];
void floyd(){
    for(int k = 1; k <= n; k ++)
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
int main(){
    cin >> n >> m >> Q;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            if(i == j) d[i][j] = 0;
            else d[i][j] = INF;
    
    while(m --){
        int a, b, w;
        cin >> a >> b >> w;
        d[a][b] = min(d[a][b], w); // 重边保留最小权的边
    }
    floyd();
    
    while(Q --){
        int a, b;
        cin >> a >> b;
        if(d[a][b] > INF / 2) puts("impossible");
        else cout << d[a][b] << endl;
    }
    return 0;
}

最小生成树

最小生成树问题一般对应于无向图，有大致两种算法来求解（最小生成树问题和边权的正负无关系，不需要考虑）

一般来讲，如果是稠密图会用朴素版Prim算法，稀疏图会用Kruskal算法，堆优化版的Prim不常用（一般不会用到）

image-20250304213820432

Prim算法

普利姆算法和迪杰斯特拉算法流程比较相似，稠密图——朴素版Prim算法 O(n^2)，稀疏图——堆优化版的Prim算法 O(mlogn)

朴素版的Prim算法要掌握算法流程，和迪杰斯特拉算法较为相似，流程如下：

先初始化距离dist[ i ]为正无穷；迭代 n 次（加到集合n个点，所以是迭代n次）：找到集合外距离最近的点并赋值给 t，用 t 更新其它点到集合的距离（dijkstra算法是更新到起点的距离），把 t 加到集合中去。

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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 5e2 + 10, INF = 0x3f3f3f3f;

int n, m;
int g[N][N]; // 稠密图用邻接矩阵来存
int dist[N];
bool st[N];

int prim(){
	memset(dist, 0x3f, sizeof dist);
    int res = 0; // res存的是最小生成树里面所有边的长度之和
    for(int i = 0; i < n; i ++){
        int t = -1;
        for(int j = 1; j <= n; j ++)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        
        if(i && dist[t] == INF) return INF;
        if(i) res += dist[t]; // 不是第一个点，才加到res中
        
        for(int j = 1; j <= n; j ++) dist[j] = min(dist[j], g[t][j]); // 由于距离定义不同，所以这里不同
        
        st[t] = true;
    }
	return res;
}

int main(){
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while(m --){
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    int t = prim();
    if(t == INF) puts("impossible");
    else cout << t << endl;
    return 0;
}

如果是稀疏图，则用Kruskal算法

Kruskal算法

时间复杂度固定 O(mlogm)，时间主要花在排序上，克鲁斯卡尔算法是个很优美的算法

基本思路很简单：

  1. 先将所有边按照权重从小到大排序，调用sort函数 O(mlogm)
  2. 枚举每条边a, b，权重是c，如果当前节点 a 和 b 不连通，我们就把这条边加入到集合中（并查集的简单应用 O(1) * m）

由于只枚举每条边，所以不需要用邻接表或邻接矩阵来存图，只需要定义一个结构体来存就行

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2e5 + 10;

int n, m;
int p[N];

struct Edge{
    int a, b, w;
    bool operator < (const Edge &W)const{
        return w < W.w;
    }
}edges[N];

int find(int x){
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i ++){
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }
    sort(edges, edges + m);
    for(int i = 1; i <= n; i ++) p[i] = i;
    int res = 0, cnt = 0; // res存最小生成树中所有树边的权重之和，cnt存当前加入了多少条边
    for(int i = 0; i < m; i ++){
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        
        a = find(a), b = find(b);
        if(a != b){ // 如果不在同一集合，则将两个集合合并
            p[a] = b; 
            res += w;
            cnt ++;
        }
    }
    
    if(cnt < n - 1) puts("impossible");
    else cout << res << endl;
    return 0;
}

二分图

二分图主要讲解两种方法，一个是染色法 O(n + m)，一个是匈牙利算法 最坏 O(mn)，实际运行时间一般远小于 O(mn)

image-20250304214029285

染色法

染色法的作用：判断是不是二分图。一个图是二分图，当且仅当图中不含奇数环（奇数环指的是环中边的数量是奇数）

二分图就是把所有点分成两个集合，使得边都是连接两个集合的，而集合内部没有边

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 <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10; // 无向图 —— 边的个数得是点的2倍
int n, m;
int h[N], e[M], ne[M], idx;
int color[N];

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool dfs(int u, int c){
    color[u] = c;
    
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(!color[j]){
            if(!dfs(j, 3 - c)) return false; // 3 - c 可以把 1 变成 2，把 2 变成 1
        }
        else if(color[j] == c) return false;
    }
    return true;
}

int main(){
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while(m --){
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    bool flag = true; // flag来表示染色时是否有矛盾发生，即是否失败
    for(int i = 1; i <= n; i ++){
        if(!color[i]){
            if(!dfs(i, 1)){
                flag = false;
                break;
            }
        }
    }
    if(flag) puts("Yes");
    else puts("No");
    return 0;
}

匈牙利算法

给定一个二分图，求它的最大匹配，可以返回成功匹配中匹配数量最大的数字（可以确定多少个匹配对）O(n*m)

每次匹配时，如果当前匹配的点已经属于别的点了，那就再看它对应的点能否匹配别的点，不断尝试，找到成功匹配

做错一件事并不后悔，错过一件事才后悔，如果前方有困难，没关系，我们可以曲线救国，只有尝试各种各样的方法之后还不行才放弃

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 <algorithm>
#include <cstring>
using namespace std;

const int N = 5e2 + 10, M = 1e5 + 10;
int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N];
bool st[N];
void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool find(int x){
    for(int i = h[x]; i != -1; i = ne[i]){
        int j = e[i];
        if(!st[j]){
            st[j] = true;
            if(match[j] == 0 || find(match[j])){ // 如果说当前右侧的点还没有匹配 或者 已经匹配了但是对应左侧的点有下家
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}
int main(){
    cin >> n1 >> n2 >> m;
    memset(h, -1, sizeof h);
    while(m --){
        int a, b;
        cin >> a >> b;
        add(a, b); /////
    }
    int res = 0;
    for(int i = 1; i <= n1; i ++){
        memset(st, false, sizeof st); /////
        if(find(i)) res++;
    }
    cout << res << endl;
    return 0;
}

附：匈牙利算法究极故事理解，不看血亏！ ^ _ ^

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
    第一个男生遍历自己所有喜欢的女生，找到了，去询问(判断state数组)
    发现这个女生是单身，ok，这一双就匹配了，成功res++。
    情况一：
        第二个男生遍历自己所有喜欢的女生，哎我焯，发现也喜欢第一个女生
    他只是耳闻好像这个女生有喜欢的人了，但是不甘心，还是想去问问(将state数组全部置成false)
    去询问发现确实有对象了，还是不甘心，舔着狗脸问那个女生，能不能让你现在的男友换一个女友
    这个女生可能也很喜欢第二个男生，就照做了，让她的男朋友去备胎里看一看(女友的现男友进递归)，结果发现
    这个女生的现男友还真有喜欢的，并且匹配成功了，好，女友把现男友给踹了，和第二个男生好了，这样成功
    匹配了两对 res又++。
    情况二：
        第二个男生遍历自己所有喜欢的女生，哎我焯，发现也喜欢第一个女生
    他只是耳闻好像这个女生有喜欢的人了，但是不甘心，还是想去问问(将state数组全部置成false)
    去询问发现确实有对象了，还是不甘心，舔着狗脸问那个女生，能不能让你现在的男友换一个女友
    这个女生可能也很喜欢第二个男生，就照做了，让她的男朋友去备胎里看一看(女友的现男友进递归)，结果发现
    这个女生的现男友没有喜欢的了，那么没办法，第二个男生只能放弃这个女生，然后去自己的后续备胎中看
    如果第二个男生后续没有喜欢的了，那么很遗憾，这个男生知识一厢情愿，最终没有摆脱单身狗的身份；
    如果第二个男生后面还有喜欢的，那么继续询问下去直至匹配。
*/

习题课

八数码

把状态抽象成图中的节点，状态转换就是权值为1的边，可以用BFS来求最短路

两个问题：1 状态表示复杂 2 如何记录每个状态的距离

可以用字符串来表示状态，这样就可以用queue来存，dist数组可以用哈希表unordered_map<string, int>来存

移动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
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <queue>

using namespace std;

int bfs(string start){
    string end = "12345678x";
    
    queue<string> q;
    unordered_map<string, int> d;
    
    q.push(start);
    d[start] = 0;
    
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    
    while(q.size()){
        auto t = q.front();
        q.pop();
        
        int distance = d[t];
        
        if(t == end) return distance;
        
        int k = t.find('x'); // 用 k 来存储 x 的位置，find('x')会返回 x 的下标
        int x = k / 3, y = k % 3;
        
        for(int i = 0; i < 4; i ++){
            int a = x + dx[i], b = y + dy[i];
            if(a >= 0 && a < 3 && b >= 0 && b < 3){
                swap(t[k], t[a * 3 + b]);
                
                if(!d.count(t)){
                    d[t] = distance + 1;
                    q.push(t);
                }
                
                swap(t[k], t[a * 3 + b]);
            }
        }
    }
    
    return -1;
}

int main(){
    string start; // 表示初始状态
    for(int i = 0; i < 9; i ++){
        char c;
        cin >> c;
        start += c;
    }
    cout << bfs(start) << endl;
    return 0;
}

第四讲——数学知识

数论题需要看时间复杂度！

数论

质数

质数是针对所有大于1的自然数定义的，所有小于等于1的整数既不是质数也不是合数

在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数，或者叫素数

（1）质数的判定——试除法 O(n)

1
2
3
4
5
6
7
bool is_prime(int n){
    if(n < 2) return false;
    for(int i = 2; i < n; i ++)
        if(n % i == 0)
            return false;
    return true;
}

上述算法可以被优化，枚举的时候，可以只枚举到根号n 一定是 O(sqrt(n))

1
2
3
4
5
6
7
bool is_prime(int n){
    if(n < 2) return false;
    for(int i = 2; i <= n / i; i ++) // 不推荐写成 i <= sqrt(n)，因为比较慢；也不推荐写成 i * i <= n，可能会溢出
        if(n % i == 0)
            return false;
    return true;
}

（2）分解质因数——试除法 最坏 O(sqrt(n)) 最好 O(logn)

从小到大枚举尝试 n 的所有数

质因子：一个数既是质数又是该数的因数

n 中最多只包含一个大于 sqrt(n) 的质因子，所以枚举时候可以先把所有小于 sqrt(n) 的质因子枚举出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void divide(int n){
    for(int i = 2; i <= n / i; i ++){
        if(n % i == 0){ // i 一定是质数
            int s = 0;
            while(n % i == 0){
                n /= i;
                s ++;
            }
            printf("%d %d\n", i, s);
        }
    }
    if(n > 1) printf("%d %d\n", n, 1);
    puts("");
}

（3）筛质数

朴素筛法：从前往后看把每个数的所有倍数删掉，以此类推删过之后所有剩下的数就是质数 O(nlog n)

1
2
3
4
5
6
7
8
9
10
11
int primes[N], cnt;
bool st[N];

void get_primes(int n){
    for(int i = 2; i <= n; i ++){
        if(!st[i]){
            primes[cnt ++] = n;
        }
        for(int j = i + i; j <= n; j += i) st[j] = true;
    }
}

优化（埃式筛法）：不需要删掉每个数对应的所有倍数，只需要删掉质数的所有倍数

1
2
3
4
5
6
7
8
9
10
11
int primes[N], cnt;
bool st[N];

void get_primes(int n){
    for(int i = 2; i <= n; i ++){
        if(!st[i]){
            primes[cnt ++] = n;
            for(int j = i + i; j <= n; j += i) st[j] = true;
        }
    }
}

1 ~ n 中有 n / ln n 个质数 所以时间复杂度约等于 O(n) 真实的时间复杂度为 O (n log log n)，其实很接近于 O(n)！

线性筛法：n 只会被它的最小质因子筛掉，每个数只有一个最小质因子，每个数只会被筛一次——所以线性筛法比埃式筛法更优

1
2
3
4
5
6
7
8
9
10
11
12
int primes[N], cnt;
bool st[N];

void get_primes(int n){
    for(int i = 2; i <= n; i ++){
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0; primes[j] <= n / i; j ++){ // 从小到大枚举所有质数，一定是用最小质因子来筛的
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break; // primes[j] 一定是 i 的最小质因子
        }
    }
}

在 10^7 数量级 大概能比埃式筛法快一倍， 10^6 二者相差不大

埃式筛法思想很重要，线性筛法最常用！

约数

（1）试除法求约数：从小到大判断，如果能整除，则找到了约数，优化方法同质数一样，枚举到 sqrt(n) O (sqrt(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
vector<int> get_divisors(int n){ // 从小到大枚举约数，只需要枚举小的，大的就能直接添加
    vector<int> res;
    for(int i = 1; i <= n / i; i ++)
        if(n % i == 0){
            res.push_back(i);
            if(i != n / i) res.push_back(n / i); // i 和 n/i 不能重复
        }
    sort(res.begin(), res.end());
    return res;
}

int main(){
    int n;
    cin >> n;
    
    while(n --){
        int x;
        cin >> x;
        auto res = get_divisors(x);
        for(auto t : res) cout << t << ' ';
        cout << endl;
    }
    return 0;
}

image-20250306160318525

（2）约数个数

先分解质因数，再把每个数的指数加1再相乘到一块儿

image-20250306171529993

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 <unordered_map>
typedef long long LL;

const int mod = 1e9 + 7;

int main(){
	int n;
    cin >> n;
    unordered_map<int, int> primes; // 存储所有的质数和对应的个数
    while(n --){
        int x;
        cin >> x;
        
        for(int i = 2; i <= x / i; i ++){
            while(x % i == 0){
                x /= i;
                primes[i] ++;
            }
        }
        if(x > 1) primes[x] ++;
    }
    LL res = 1;
    for(auto prime : primes) res = res * (prime.second + 1) % mod;
    
    cout << res << endl;
    
    return 0;
}

（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
#include <unordered_map>
typedef long long LL;

const int mod = 1e9 + 7;

int main(){
	int n;
    cin >> n;
    unordered_map<int, int> primes; // 存储所有的质数和对应的个数
    while(n --){
        int x;
        cin >> x;
        
        for(int i = 2; i <= x / i; i ++){
            while(x % i == 0){
                x /= i;
                primes[i] ++;
            }
        }
        if(x > 1) primes[x] ++;
    }
    LL res = 1;
    for(auto prime : primes){
        int p = prime.first, a = prime.second;
        LL t = 1;
        while(a --) t = (t * p + 1) % mod;
        res = res * t % mod;
    }
    
    cout << res << endl;
    
    return 0;
}

（4）欧几里得算法（辗转相除法）：最大公约数 O(log n)

(a, b)的最大公约数等同于(b, a mod b)的最大公约数，证明：a mod b 可以看作是 a - c * b，故成立

求 a 和 b 的最大公约数的一行代码模板：

1
2
3
int gcd(int a, int b){
    return b ? gcd(b, a % b) : a; // 如果b不为0，则拓展，为0则等于a
}

欧拉函数

欧拉函数 φ(n)\varphi(n) 指的是 1 ~ n 中与 n 互质的数的个数，例如 φ(6)=2\varphi(6) = 2 (1 和 5 与 6 互质)

要求一个数的欧拉函数的话，需要先对该数分解质因数，分解质因数后欧拉函数可以套公式求

image-20250306183952593

这个公式的证明用到了 容斥原理，欧拉函数公式的证明如下：

image-20250306184721686

用公式来求一个数的欧拉函数的时间复杂度 O(sqrt(n))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main(){
    int n;
    cin >> n;
    while(n --){
        int a;
        cin >> a;
        
        int res = a;
        for(int i = 2; i <= a / i; i ++){
            if(a % i == 0){
                res = res  / i * (i - 1); // 利用公式来求
                while(a % i == 0) a /= i;
            }
        }

        if(a > 1) res = res / a * (a - 1);
        cout << res << endl;
    }
    return 0;
}

线性筛法过程中顺便求欧拉函数

如果要求 1 ~ n 中每个数的欧拉函数的和，可以用线性筛法来用 O(n) 的时间复杂度来求1 ~ n 中每一个数的欧拉函数

当 i mod pj = 0 和 ≠ 0 时，φ(pj⋅i)\varphi(p_j ·i) 的表达式推导证明 如下图：

image-20250306190929227

image-20250306191324030

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
typedef long long LL;
const int N = 1e6 + 10;
int primes[N], cnt;
int phi[N];
bool st[N];

LL get_eulers(int n){
    phi[1] = 1;
    for(int i = 2; i <= n; i ++){
        if(!st[i]){
            primes[cnt ++] = i; 
            phi[i] = i - 1; // 如果一个数是质数，显然它前面的数都是与它互质的，欧拉函数值为 i - 1
        }
        for(int j = 0; primes[j] <= n / i; j ++){
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) {
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }
    
    LL res = 0;
    for(int i = 1; i <= n; i ++) res += phi[i];
    
    return res;
}

int main(){
    int n;
    cin >> n;
    cout << get_eulers(n) << endl;
}

欧拉定理：image-20250306193151780

例如：image-20250306193227171

当 n 是质数时，有以下推论（即费马定理和费马小定理）：

image-20250306194951687

快速幂

快速幂 能够快速地求出来 aka^k mod p 的结果 O(log k) 暴力的话就是 O(k)

核心思路：反复平方法，预处理出来以下值，来组合出来 aka^k：

把 k 拆成若干个2的次幂数之和，即把 k 化成二进制表示，看哪些位是1，把 1 对应的位乘起来就行

image-20250306195730667

如何预处理前面的数：

image-20250306195932347

举个例子如下：

image-20250306200331286

数论里的常客，快速幂！

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 <algorithm>
using namespace std;

typedef long long LL;

// 求的就是 a^k mod p
int qmi(int a, int k, int p){
    int res = 1;
    while(k){
        if(k & 1) res = (LL)res * a % p;
        k >>= 1; // 找 k 的二进制表示的下一位
        a = (LL)a * a % p;
    }
    return res;
}

int main(){
    int n;
    scanf("%d", &n);
    while(n --){
        int a, k, p;
        scanf("%d%d%d", &a, &k, &p);
        printf("%d\n", qmi(a, k, p));
    }
    return 0;
}

快速幂的用处太多了！

快速幂求逆元（p 得是质数才能用费马定理这么做！）

逆元的概念：a / b 同余于 a * (b的逆元)（mod m），即把除法转化为乘法

即转化为以下问题，x是b的逆元，则满足下式：

image-20250306203156194

再由费马定理可以转化为求 bp−2b^{p-2}：

image-20250306203352286

本质上用的就是快速幂：

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
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;

// 求的就是 a^k mod p
int qmi(int a, int k, int p){
    int res = 1;
    while(k){
        if(k & 1) res = (LL)res * a % p;
        k >>= 1; // 找 k 的二进制表示的下一位
        a = (LL)a * a % p;
    }
    return res;
}

int main(){
    int n;
    scanf("%d", &n);
    while(n --){
        int a, p;
        scanf("%d%d", &a, &p);
        int res = qmi(a, p - 2, p); 
        if(a % p) printf("%d\n", res); // p = 2的时候比较特殊，一定返回 1
        else puts("impossible");
    }
    return 0;
}

扩展欧几里得算法

把辗转相除法进行拓展，讲之前先看 裴蜀定理：

对于任意正整数 a, b，那么一定存在非零整数 x, y，使得 ax + by = (a, b)（a 和 b 的最大公约数）

证明存在性定理，可以用构造法，这个方法就是 拓展欧几里得算法 可以求系数 x 和 y

原先的 欧几里得算法 原理： gcd(a , b) = gcd(b, a mod b)；

1
2
3
int gcd(int a, int b){
    return b ? gcd(b, a % b) : a; // 如果b不为0，则拓展，为0则等于a
}

拓展欧几里得算法 推导如下：

image-20250307104654858

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int exgcd(int a, int b, int &x, int &y){ // 记得加引用符，不加的话值传不过来
    if(!b){
    	x = 1, y = 0;
        return a;
    } 
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main(){
    int n;
    scanf("%d", &n);
    while(n --){
    	int a, b, x, y;
        scanf("%d%d", &a, &b);
        
        exgcd(a, b, x, y);
        printf("%d %d\n", x, y);
    }
    return 0;
}

扩展欧几里得算法应用：求解线性同余方程 image-20250307105124709

给定 a 和 b，求解 x 的值（输出一个在范围内的解就行）

思路：将等式作变形，只要 d 是 a 和 m 的最大公约数的倍数，就有解

image-20250307110139493

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int exgcd(int a, int b, int &x, int &y){ // 记得加引用符号，不加的话值传不过来
    if(!b){
    	x = 1, y = 0;
        return a;
    } 
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main(){
    int n;
    scanf("%d", &n);
    while(n --){
    	int a, b, m;
        scanf("%d%d%d", &a, &b, &m);
        int x, y;
        int d = exgcd(a, m, x, y);
        if(b % d) puts("impossible"); // 如果 b 不是 d 的倍数 一定无解
        else printf("%d\n", (LL)x * (b / d) % m); // 等式两边同时放大 b/d 倍就行
    }
    return 0;
}

中国剩余定理

中国剩余定理很简单：给定一堆两两互质的数，需要解决一个一维线性同余方程组，并求出最小的正整数x

image-20250307110517668

中国剩余定理有个限制条件，要求m1、m2…、mk两两互质

下面来看推导过程：

image-20250310170018765

这样的线性方程组就有一个公式通解：

image-20250307111005169

求逆可以用 拓展欧几里得算法 来求，用以下公式：

image-20250307110837460

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 <algorithm>
using namespace std;
typedef long long LL;

LL exgcd(LL a, LL b, LL &x, LL &y){
    if(!b){
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main(){
    int n;
    cin >> n;
    
    bool has_answer = true;
    LL a1, m1; // 现有的方程
    
    cin >> a1 >> m1;
    
    for(int i = 0; i < n - 1; i ++){
        LL a2, m2;
        cin >> a2 >> m2;
        
        LL k1, k2;
        LL d = exgcd(a1, a2, k1, k2);
        if((m2 - m1) % d){ // 无解的情况
            has_answer = false;
            break;
        }
        
        k1 *= (m2 - m1) / d; // 翻该倍数
        LL t = a2 / d;
        k1 = (k1 % t + t) % t; // 把它变成最小的正整数解
        
        m1 = a1 * k1 + m1;
        a1 = abs(a1 / d * a2);
        
    }
    if(has_answer){
        cout << (m1 % a1 + a1) % a1 << endl; // m1 % a1 的正的余数
    }
    else puts("-1");
    
    return 0;
}

高斯消元

高斯消元是用来解方程的，一般是可以在 n^3 的时间内，求解一个包含 n 个方程和 n 个未知数的多元线性方程组

解会有三种情况：1.无解 2.无穷多组解 3.只有一组解

高斯消元原理：将系数抽出来得到系数矩阵，再对该矩阵进行初等行列变换操作：

  1. 把某一行乘一个非 0 的数
  2. 交换某两行
  3. 把某行的若干倍加到另一行上去

进行初等行列变换是不会改变解的情况的！通过以上操作变换，将矩阵变为上三角形式！

如果消完后恰好是 完美的阶梯形，就对应唯一解；不完美阶梯形：0 = 非零——无解； 0 = 0——无穷多组解

详细过程：枚举每一列 c，

① 先找到该列中绝对值最大的一行（除去已固定好的行） ② 将这一行换到最上面去

③ 将该行第一个数变成 1 ④ 将下面所有行的第 c 列消成 0

若化为上三角矩阵，则从最后一列开始，将第一个数变成 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
54
55
56
57
58
59
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 110;
const double eps = 1e-6;

int n;
double a[N][N];

int gauss(){
    int c, r;
    for(c = 0, r = 0; c < n; c ++){
        int t = r;
        for(int i = r; i < n; i ++)
            if(fabs(a[i][c]) > fabs(a[t][c]))
                t = i;
        
        if(fabs(a[t][c]) < eps) continue;
        
        for(int i = c; i <= n; i ++) swap(a[t][i], a[r][i]);
        for(int i = n; i >= c; i --) a[r][i] /= a[r][c];
        for(int i = r + 1; i < n; i ++)
            if(fabs(a[i][c]) > eps)
                for(int j = n; j >= c; j --)
                    a[i][j] -= a[r][j] * a[i][c];
        r ++;
    }
    if(r < n){
        for(int i = r; i < n; i ++)
            if(fabs(a[i][n]) > eps)
                return 2; // 无解
        return 1; //有无穷多组解
    }
    
    for(int i = n - 1; i >= 0; i --)
        for(int j = i + 1; j < n; j ++)
            a[i][n] -= a[i][j] * a[j][n];
    
    return 0; // 有唯一解
}

int main(){
	cin >> n;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n + 1; j ++)
    		cin >> a[i][j];
   	
    int t = gauss();
    if(t == 0){
        for(int i = 0; i < n; i ++) printf("%.2lf\n", a[i][n]);
    }
    else if(t == 1) puts("Infinite group solutions");
    else puts("No solution");
    
    return 0;
}

组合计数

组合数计算注意数据范围，选择不同的方法！

组合数的计算公式：

image-20250307160023648

求组合数I

可以先由以下公式预处理出来所有组合数的值

image-20250307160500597

计算的时候再进行查表计算即可！

10万组询问，a和b范围是2000，采用递推预处理出来所有组合数的值！ Cn0=1C_n^0= 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
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 2010, mod = 1e9 + 7;

int c[N][N];

void init(){
    for(int i = 0; i < N; i ++)
        for(int j = 0; j <= i; j ++)
        	if(!j) c[i][j] = 1; 
    		else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}

int main(){
    init();
    int n;
    scanf("%d", &n);
    while(n --){
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", c[a][b]);
    }
    return 0;
}

北大计算机系是 理科

培养方案有 技术导向——高等数学2学期、线性代数1学期、离散数学2学期

​ 科学导向——数学分析3学期、高等代数2学期、离散数学3学期

求组合数II

1万组询问，a和b范围是10万，预处理！ 预处理阶乘值！以查表思想来求，求逆元可以用快速幂

image-20250307164939617

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

using namespace std;

typedef long long LL;
const int N = 1e5 + 10, mod = 1e9 + 7;

int fact[N], infact[N];

int qmi(int a, int k, int p){
    int res = 1;
    while(k){
        if(k & 1) res = (LL)res * a % p;
        k >>= 1;
        a = (LL)a * a % p;
    }
    return res;
}

int main(){
    fact[0] = infact[0] = 1;
    for(int i = 1; i < N; i ++){
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
    int n;
    scanf("%d", &n);
    while(n --){
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
    }
    return 0;
}

求组合数III

20组询问，a 和 b 的范围是10^18，p 的范围是10^5，这时就可以用卢卡斯定理 Lucas

image-20250307165855857

时间复杂度为 image-20250307170719433

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

using namespace std;

typedef long long LL;

int p;

int qmi(int a, int k){
    int res = 1;
    while(k){
        if(k & 1) res = (LL)res * a % p;
        k >>= 1;
        a = (LL)a * a % p;
    }
    return res;
}

int C(int a, int b){
    int res = 1;
    for(int i = 1, j = a; i <= b; i ++, j --){
        res = (LL)res * j % p;
        res = (LL)res * qmi(i, p - 2) % p;
    }
    return res;
}

int lucas(LL a, LL b){
    if(a < p && b < p) return C(a, b);
    return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}

int main(){
    int n;
    cin >> n;
    while(n --){
        LL a, b;
        cin >> a >> b >> p;
        cout << lucas(a, b) << endl;
    }
    return 0;
}

求组合数IV

输入 a，b，求组合数 CabC_a^b 的值，a 和 b 数据范围到 5000

可以直接用定义求，先把组合数分解质因数，就会变成只有乘法的形式，再进行高精度乘法就可以了

image-20250308090825865

C++ 开 O2 优化 在最上面写一句 #pragma GCC optimize(2) O2 优化考试时候会被禁用，所以建议自己平时不要写

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

using namespace std;

const int N = 5e3 + 10;

int primes[N], cnt;
int sum[N];
bool st[N];

void get_primes(int n){
    for(int i = 2; i <= n; i ++){
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0; primes[j] <= n / i; j ++){
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int get(int n, int p){
    int res = 0;
    while(n){
        res += n / p;
        n /= p;
    }
    return res;
}

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

int main(){
    int a, b;
    cin >> a >> b;
    
    get_primes(a);
    
    for(int i = 0; i < cnt; i ++){
        int p = primes[i];
        sum[i] = get(a, p) - get(b, p) - get(a - b, p);
    }
    
    vector<int> res;
    res.push_back(1);
    
    for(int i = 0; i < cnt; i ++) // 枚举所有质数
        for(int j = 0; j < sum[i]; j ++) // 枚举该质数的次数
            res = mul(res, primes[i]);
    
    for(int i = res.size() - 1; i >= 0; i --) printf("%d", res[i]);
    puts("");
    return 0;
}

卡特兰数

卡特兰数应用很广泛，很多问题的方案数都是卡特兰数

image-20250308092515337

把问题转化成从原点走路径的问题，从(0, 0) 走到 (6, 6)有多少种方案，0表示向右走一格，1表示向上走一格

把每一个序列都可以看作一条路径

任意前缀0的个数大于1的个数，到路径上体现出来的就是在y = x斜线下面，任意时刻满足x >= y

问题转化为从(0, 0) 走到 (n, n) 不经过红颜色这条边的所有路径的个数

image-20250308093632308

总共方案数 - 经过红颜色边的方案数 = 答案

总共方案数 C126C_{12}^6

经过红颜色边的方案数 可以看作 从 (0, 0) 走到 (5, 7) 的路径方案数 C125C_{12}^5

总共方案数 = C2nn−C2nn−1=C2nn/(n+1)C_{2n}^n - C_{2n}^{n-1} = C_{2n}^n / (n + 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
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 1e9 + 7;

int qmi(int a, int b, int p){ // 求逆元可以用快速幂，因为取模的数是质数，如果不是质数只能用拓展欧几里得算法来求
    int res = 1;
    while(k){
        if(k & 1) res = (LL)res * a % p;
        k >>= 1;
        a = (LL)a * a % p;
    }
    return res;
}

int main(){
    int n;
    cin >> n;
    int a = 2 * n, b = n;
    int res = 1;
    for(int i = a; i > a - b; i --) res = (LL)res * i % mod;
    for(int i = 1; i <= b; i ++) res = (LL)res * qmi(i, mod - 2, mod) % mod;
    
    res = (LL)res * qmi(n + 1, mod - 2, mod) % mod;
    
    cout << res << endl;
    
    return 0;
}

容斥原理

容斥原理初高中一定讲过，韦恩图，奇数个前面是加号，偶数个前面是减号

image-20250308103915534

时间复杂度 O(2^n) 理由：由实际含义出发可以得到 image-20250308104534071

证明：image-20250308104859050

证明如下：一个数既只在左边出现一次，又只在右边出现一次

image-20250308105143299

接下来来看一下应用：

image-20250308105255008

这种题一定要用容斥原理来算，用暴力一定会超时！

思路如下：

image-20250308105711112

容斥原理来算的话 时间复杂度O(2^m)

那么 SpS_p （1 到 n 中 p 的倍数的个数）该怎么求呢？ n / p 下取整

那么 Si∩SjS_i ∩ S_j 可以看作 SijS_{ij} ，就能按照上面方式来求

算每个集合的时间复杂度 O(k)

实现：枚举所有集合的情况，用位运算来枚举所有的选法，暴搜DFS也可以，但不推荐

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

using namespace std;
typedef long long LL;
const int N = 20;

int n, m;
int p[N];

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i ++) cin >> p[i];
    
    int res = 0;
    // 枚举集合
    // 把i看成二进制位，一共有n位二进制数，这一位上如果是1表示该集合被选了，如果是0表示没有选
    for(int i = 1; i < 1 << m; i ++){
        int t = 1, cnt = 0; // 用t来表示当前所有质数的乘积，用cnt来表示当前选法有几个集合
        // 枚举当前集合所表示二进制数每一位
        for(int j = 0; j < m; j ++){
            if(i >> j & 1){
                cnt ++;
                if ((LL)t * p[j] > n){
                    t = -1;
                    break;
                }
                t *= p[j];
            }
        }
        if(t != -1){
            if(cnt % 2) res += n / t;
            else res -= n / t; 
        }
    }
    cout << res << endl;
    return 0;
}

简单博弈论

Nim游戏

image-20250308135441520

先手必胜状态：先手以某种方式拿完后可以让剩下的状态变为 先手必败状态

先手必败状态：不管如何操作，剩下的状态都无法变为 先手必败状态

n 堆石子个数分别为 a1，a2，a3…，an，则有以下结论

image-20250308140352304

异或值是0对应必败态

异或值不是0，一定可以通过某种方式使得异或值变为0

异或值是0，不管怎么拿都无法转变为异或值仍为0

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

using namespace std;

int main(){
    int n;
    int res = 0;
    scanf("%d", &n);
    while(n --){
        int x;
        scanf("%d", &x);
        res ^= x;
    }
    if(res) puts("Yes");
    else puts("No");
    return 0;
}

台阶-Nim游戏

image-20250310181135996

我们只需要看奇数台阶上的石子，偶数台阶上的不需要看

奇数台阶上石子数量为 a1、a3…、an

image-20250308140352304

对手拿偶数台阶，则我们拿奇数台阶（顺次放到下一个台阶上），让奇数台阶上石子数量不变

对手拿奇数台阶，则我们也拿奇数台阶，让奇数台阶上石子数量一致

SG函数

SG函数 是用来解决博弈论问题的利器，首先定义Mex运算：

image-20250308143335991

SG(终点) = 0，SG(x) = mex{SG(y1), SG(y2), … ,SG(yk)}

image-20250308144723303

任何一个非0状态一定可以到0，任何一个0状态一定到不了0

SG = 0 必败 SG ≠ 0 则必胜

如果此时不止一个图，而是多个图，那么可以将多个图局面的SG值进行异或，有以下结论：

image-20250308145503703

image-20250308145805894

集合-Nim游戏

n 堆石子可以看作 n 个有向图，然后可以算每个有向图的 SG 的值

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 <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_set>

using namespace std;

const int N = 110, M = 10010; 

int n, m;
int s[N], f[M]; // s表示石子个数，f表示sg的值

int sg(int x){
    if(f[x] != -1) return f[x]; // 被算过，则不重复计算，直接返回
    
    unordered_set<int> S; // S存储所有能到达的状态
    for(int i = 0; i < m; i ++){ // 遍历取石子的方案
        int sum = s[i];
        if(x >= sum) S.insert(sg(x - sum));
    }
    
    for(int i = 0; ; i ++)
        if(!S.count(i))
            return f[x] = i;
}

int main(){
    cin >> m;
    for(int i = 0; i < m; i ++) cin >> s[i];
    cin >> n;
    memset(f, -1, sizeof f); // 记忆化搜索
    int res = 0;
    for(int i = 0; i < n; i ++){
        int x;
        cin >> x;
        res ^= sg(x);
    }
    if(res) puts("Yes");
    else puts("No");
    
    return 0;
}

拆分-Nim游戏

image-20250310184525440

一堆可能分成两堆，两堆局面的SG值一定等于两堆局面分别每一堆的值异或起来

image-20250310185222704

记忆化搜索来求SG

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 <algorithm>
#include <cstring>
#include <unordered_set>
using namespace std;

const int N = 110;
int f[N]; // 每一个值的SG值

int sg(int x){
    if(f[x] != -1) return f[x];
    
    unordered_set<int> S;
    for(int i = 0; i < x; i ++)
        for(int j = 0; j <= i; j ++)
            S.insert(sg(i) ^ sg(j));
    
    for(int i = 0; ; i ++)
        if(!S.count(i))
            return f[x] = i;
}

int main(){
    int n;
    cin >> n;
    memset(f, -1, sizeof f);
    int res = 0;
    for(int i = 0; i < n; i ++){
        int x;
        cin >> x;
        res ^= sg(x);
    }
    if(res) puts("Yes");
    else puts("No");
    return 0;
}

组合数学常用公式

Cn0+Cn2+Cn4+...+Cn2k=2n−1C_n^0+C_n^2+C_n^4+...+C_n^{2k}=2^{n-1}

Cn0+Cn1+Cn2+...+Cnn=2nC_n^0+C_n^1+C_n^2+...+C_n^n=2^n

第五讲——动态规划

为什么可以DP？无后效性！

① 常用模型：背包问题

② 线性DP、区间DP、状态压缩DP、计数类DP、数位统计DP

动态规划核心：状态表示和状态转移方程！

动态规划问题的时间复杂度：状态数量 * 转移的计算量（算每个状态需要的计算量）

动态规划为什么快？用一个状态来表示一堆方案的 最值/个数

DFS为什么慢？因为会遍历每个方案

背包问题

b站课程：背包九讲——AcWing编号最前12题

N个物品和容量是V的背包，物品有两个属性体积vi和价值wi，每件物品仅用一次（0/1 背包问题的特点：不能拆分物品）

总体积小于等于V的情况下，能选出来的最大总价值是多少？

0 / 1 背包问题（每件物品最多只用一次）

image-20250310204312247

y总个人认为最好理解动态规划的一种方式：

image-20250310210505990

DP优化一般就是对 代码 或 状态计算方程 作一个等价变形

先看朴素代码怎么写，再进行优化到一维

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 <algorithm>

using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
    // f[0][0 ~ m] = 0; 默认初始化都为0，可以不写
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= m; j ++){
            f[i][j] = f[i - 1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    cout << f[n][m] << endl;
    return 0;
}

f(i) 只用到了 f(i - 1)，j 的取值永远在单侧，不在两侧，所以可以优化

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

using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
    // f[0][0 ~ m] = 0; 默认初始化都为0，可以不写
    for(int i = 1; i <= n; i ++)
        for(int j = m; j >= v[i]; j --)
            f[j] = max(f[j], f[j - v[i]] + w[i]); // 滚动数组
    cout << f[m] << endl;
    return 0;
}

完全背包问题（每件物品有无限个）

image-20250311091604994

朴素做法如下：

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

using namespace std;

const int N = 1e3 + 10;
int n, m;
int v[N], w[N];
int f[N][N];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= m; j ++)
            for(int k = 0; k * v[i] <= j; k ++)
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
            
    cout << f[n][m] << endl;
}

优化思路如下：

image-20250311092546043

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 <algorithm>

using namespace std;

const int N = 1e3 + 10;
int n, m;
int v[N], w[N];
int f[N][N];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= m; j ++){
            f[i][j] = f[i - 1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }

    cout << f[n][m] << endl;
}

也可以优化到一维： 0/1 背包问题从大到小循环 完全背包问题从小到大循环！

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

using namespace std;

const int N = 1e3 + 10;
int n, m;
int v[N], w[N];
int f[N];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i ++)
        for(int j = v[i]; j <= m; j ++)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;
}

多重背包问题（每个物品个数不一样，最多有 SiS_i个）

image-20250311093921747

朴素版本 多重背包问题 代码如下：

多重背包问题I

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 <algorithm>

using namespace std;

const int N = 1e2 + 10;
int n, m;
int v[N], w[N], s[N];
int f[N][N];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i] >> s[i];
    
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= m; j ++)
            for(int k = 0; k <= s[i] && k * v[i] <= j; k ++)
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);

    cout << f[n][m] << endl;
    return 0;
}

下面来看如何优化：

与完全背包问题不同，多重背包问题不能直接替换式子，因此不能直接用完全背包问题的优化方式来优化本题

这里采用 二进制的优化方式

可以把若干个第 i 件物品打包成若干组，每组只能选一次，这样就能凑出来 0 ~ 1023 中的每一个数

把 O(n) 优化成 O(log n)

如果第i个物品是si个，就可以拆分成logsi个新的物品，拆分之后再对所有新的物品做一遍0/1背包问题就可以了

多重背包问题II

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

using namespace std;

const int N = 13000, M = 2010; // 1000 * log2000 ≈ 13000;
int n, m;
int v[N], w[N];
int f[N];

int main(){
    cin >> n >> m;
    int cnt = 0;
    for(int i = 1; i <= n; i ++){
        int a, b, s;
        cin >> a >> b >> s; // 读进来当前物品的 体积、价值和个数
        int k = 1; // 从 1 开始分
        while(k <= s){ // 每次把 k 个第 i 个物品打包在一起
            cnt ++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if(s > 0){
            cnt ++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    n = cnt;
    
    for(int i = 1; i <= n; i ++)
        for(int j = m; j >= v[i]; j --)
            f[j] = max(f[j], f[j - v[i]] + w[i]); // 滚动数组
    
    cout << f[m] << endl;
    return 0;
}

分组背包问题（物品有N组，每一组里面最多只能选一个物品，不一定要装满背包）

枚举第 i 组物品，选哪个？

image-20250311102853557

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 <algorithm>

using namespace std;

const int N = 1e2 + 10;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++){ // 处理数据输入
        cin >> s[i];
        for(int j = 0; j < s[i]; j ++)
            cin >> v[i][j] >> w[i][j];
    }
           
    
    for(int i = 1; i <= n; i ++)
        for(int j = m; j >= 0; j --)
            for(int k = 0; k < s[i]; k ++)
                if(v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

    cout << f[m] << endl;
    return 0;
}

线性DP

背包问题其实是二维的，把二维状态画出来是一个二维矩阵的形式

递推的顺序有个线性的顺序，这样的DP叫做线性DP

学DP最基础的一道题：

数字三角形

image-20250311142228952

问题是要找一条路径上所有数字之和最大的一条路径！

这里的状态表示：二维状态 f [ i, j ]，这里的集合：路径，这里的属性：所有路径之和的最大值

image-20250311143431656

计算时候涉及到 i - 1 这种下标，应该下标从 1 开始，而不是从 0 开始；反之可以从 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
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 510, INF = 1e9;

int n;
int a[N][N];
int f[N][N];

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= i; j ++)
            scanf("%d", &a[i][j]);
    
    // 为了不处理边界，我们先把所有的 f 置成负无穷
    for(int i = 0; i <= n; i ++)
        for(int j = 0; j <= i + 1; j ++)
            f[i][j] = -INF;
            
    f[1][1] = a[1][1];
    for(int i = 2; i <= n; i ++)
        for(int j = 1; j <= i; j ++)
            f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);
    
    int res = -INF;
    for(int i = 1; i <= n; i ++) res = max(res, f[n][i]);
    
    printf("%d\n", res);
    
    return 0;
}

最长上升子序列

image-20250311145043899

一维就可以表示状态了

image-20250311150511643

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

using namespace std;
const int N = 1e3 + 10;

int n;
int a[N], f[N];

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i ++){
        f[i] = 1; // 只有 a[i] 一个数
        for(int j = 1; j < i; j ++)
            if(a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    }
    
    int res = 0;
    for(int i = 1; i <= n; i ++) res = max(res, f[i]);
    
    printf("%d\n", res);
    return 0;
}

最长上升子序列 II

之前求的是以第 i 个数字结尾的最长上升子序列长度 f [ i ]，分类依据是倒数第二个数是哪个数

朴素版本 状态转移方程： image-20250313191236036

image-20250313203037504

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

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N];
int q[N]; // 存储所有不同长度的上升子序列结尾最小值

int main(){
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i];
    
    int len = 0; // 当前的最大长度
    q[0] = -2e9;
    for(int i = 0; i < n; i ++){
        int l = 0, r = len;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = a[i]; // q[r + 1] 一定大于等于 a[i]
    }
    cout << len << endl;
    
    return 0;
}

最长公共子序列

image-20250311154603802

f ( i, j ) 表示的是第一个序列的前 i 个字母，且在第二个序列的前 j 个字母中出现的子序列

划分是按照 a[ i ] 和 b[ j ] 是否被选择 分为四种情况

求最大值可以有重复，求数量一定不能有重复！

image-20250311160602846

image-20250311160749455

这里 11 这种情况 需要 a[ i ] = b[ j ]，才能满足题意

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 <algorithm>

using namespace std;
const int N = 1e3 + 10;
int n, m;
char a[N], b[N]; // 两个字符串
int f[N][N];

int main(){
    scanf("%d%d", &n, &m);
    scanf("%s%s", a + 1, b + 1);
    
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= m; j ++){
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if(a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }
    
    printf("%d\n", f[n][m]);
    return 0;
}

最短编辑距离

image-20250313203238487

这个题就是个 线性DP 问题

f [ i , j ] 表示 所有将 a [1 ~ i ] 变成 b [1 ~ j ] 的操作方式 分类方式一般是考虑：最后一步的选法（本题中是 最后一步对应三种操作方式）

image-20250313210433224

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

using namespace std;

const int N = 1e3 + 10;

int n, m;
char a[N], b[N];
int f[N][N];

int main(){
    scanf("%d%s", &n, a + 1);
    scanf("%d%s", &m, b + 1);
    
    for(int i = 0; i <= m; i ++) f[0][i] = i;
    for(int i = 0; i <= n; i ++) f[i][0] = i;
    
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++){
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            if(a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
        }
    
    printf("%d\n", f[n][m]);
    
    return 0;
}

编辑距离

image-20250313211221927

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
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

const int N = 15, M = 1e3 + 10; // 数据范围中最多有1000个字符串

int n, m;
int f[N][N];
char str[M][N]; 

int edit_distance(char a[], char b[]){
    int la = strlen(a + 1), lb = strlen(b + 1);
    
    for(int i = 0; i <= lb; i ++) f[0][i] = i;
    for(int i = 0; i <= la; i ++) f[i][0] = i;
    
    for(int i = 1; i <= la; i ++)
        for(int j = 1; j <= lb; j ++){
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
        }
    
    return f[la][lb];
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i ++) scanf("%s", str[i] + 1); // 涉及到 i - 1，因此下标从 1 开始较为方便
    
    while(m --){
        char s[N];
        int limit;
        scanf("%s%d", s + 1, &limit);
        
        int res = 0;
        for(int i = 0; i < n; i ++)
            if(edit_distance(str[i], s) <= limit)
                res ++;
        
        printf("%d\n", res);
    }
    
    return 0;
}

区间DP

石子合并 本题源自《算法竞赛进阶指南》

image-20250311162429213

不同的合并顺序需要的代价是不同的，要求输出最小代价

区间DP：状态表示是表示某一个区间

f [ i , j ] 表示 第 i 堆石子到第 j 堆石子的区间（合并的方式） 最终答案即 f [1, n ]

我们以最后一次合并的分界线所处的位置来分类

image-20250311163839207

image-20250311163728878

s [ j ] - s [ i - 1 ] 前缀和来求 从 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
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 3e2 + 10;

int n;
int s[N];
int f[N][N];

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) scanf("%d", &s[i]);
    for(int i = 1; i <= n; i ++) s[i] += s[i - 1];
    
    for(int len = 2; len <= n; len ++){ // 枚举区间长度
        for(int i = 1; i + len - 1 <= n; i ++){ // 枚举左右端点
            int l = i, r = i + len - 1;
            f[l][r] = 1e8;
            for(int k = l; k < r; k ++)
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
        }
    }
    
    printf("%d\n", f[1][n]);
    return 0;
}

计数类DP

整数划分

image-20250313214000267

该问题有很多种考虑方式，不同考虑方式可以得到不同的状态转移方程

完全背包问题解法

把整数 n 看成是一个容量是 n 的背包，一共有 n 个物品，物品的体积分别是 1 ~ n，求的是恰好装满背包的方案数

可以看作是 完全背包问题

image-20250313215342884

image-20250313220329622

以上为朴素做法，接下来进行优化：

image-20250313215641171

优化后的式子如下：

image-20250313215649274

跟完全背包一样，可以优化到一维：

image-20250313215721244

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 <algorithm>
#include <cstring>

using namespace std;

const int N = 1e3 + 10, mod = 1e9 + 7;

int n;
int f[N];

int main(){
    cin >> n;
    f[0] = 1; // 一个数都不选 是一种方案
    for(int i = 1; i <= n; i ++) // i是体积，j是容量
        for(int j = i; j <= n; j ++)
            f[j] = (f[j] + f[j - i]) % mod;
    
    cout << f[n] << endl;
    
    return 0;
}

其它解法

image-20250313221433051

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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e3 + 10, mod = 1e9 + 7;

int n;
int f[N][N];

int main(){
    cin >> n;
    f[0][0] = 1;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= i; j ++)
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;
    
    int res = 0;
    for(int i = 1; i <= n; i ++) res = (res + f[n][i]) % mod;
    
    cout << res << endl;
    
    return 0;
}

数位统计DP

计数问题 本题源自《算法竞赛进阶指南》

image-20250312155132172

像一个小学数奥问题，最重要的是分情况讨论：（数位DP尤其强调这点！）

实现函数 count(n , x)，意义是求 1 ~ n 中 x 出现的次数

求 a ~ b 中 x 出现的次数可以被转化为该式子：count(b, x) - count(a - 1, x)

image-20250312160623966

枚举 1 出现在最高位的时候，第一种情况是不存在的；

枚举数字 0 的时候，在第一种情况可能存在前导 0 的情况

image-20250313111030018

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

using namespace std;

int get(vector<int> num, int l, int r){ // 求l位到r位 组成的数字是多少
    int res = 0;
    for(int i = l; i >= r; i --)
        res = res * 10 + num[i];
    return res;
}

int power10(int x){ // 求10的x次方
    int res = 1;
    while(x --) res *= 10;
    return res;
}

int count(int n, int x){
    if(!n) return 0;
    vector<int> num; // 把 n 的每一位放入到 num 中
    while(n){
        num.push_back(n % 10);
        n /= 10;
    }
    
    n = num.size(); 
    
    int res = 0;
    for(int i = n - 1 - !x; i >= 0; i --){ // 当 x 取 0 时，应该从第二位开始枚举，所以减去一个 !x
        if(i < n - 1){
            res += get(num, n - 1, i + 1) * power10(i);
            if(!x) res -= power10(i);
        }
        
        if(num[i] == x) res += get(num, i - 1, 0) + 1;
        else if(num[i] > x) res += power10(i);
    }
    return res;
}

int main(){
    int a, b;
    while(cin >> a >> b, a || b){
        if(a > b) swap(a, b);
        for(int i = 0; i < 10; i ++)
            cout << count(b, i) - count(a - 1, i) << ' ';
        cout << endl;
    }
    return 0;
}

状态压缩DP

状态压缩DP 的核心思想：用一个整数来表示每一个状态，该整数可以看作是一个二进制数，每一位是0或是1表示两种不同情况

特征：状态个数不会很多，n 比较小，因为 1 << n 可能会溢出

蒙德里安的梦想 本题源自《算法竞赛进阶指南》

image-20250312162730460

本题堪称 状态压缩DP 的经典应用！

题意可以转化为在 N * M 的棋盘中能放多少个 1 * 2 的小方格

所有横向小方格摆好后，纵向的小方格只有一种方案，因此题意所求方案 转化为 横向小方格摆放的方案数

f [ i , j ] 表示所有摆到了 第 i 列 上一列伸出来的小方格 的行总共有 j 个的情况下 总共的方案数

状态虽然是整数，但要看成二进制数，二进制的每一位是 0 或 1 表示一种状态

① 不能冲突，（j & k) == 0

② j | k 不能存在连续奇数个 0

image-20250312215051871

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 <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 12, M = 1 << N; // N 和 M 分别为矩形的行数和列数

int n, m;
LL f[N][M];
bool st[N];

int main(){
    int n, m; // n 为行
    while(cin >> n >> m, n || m){
        memset(f, 0, sizeof f);
        
        // 采用单个的位 来表示状态
        for(int i = 0; i < 1 << n; i ++){
            st[i] = true;
            int cnt = 0; // 表示当前连续 0 的个数
            for(int j = 0; j < n; j ++)
                if(i >> j & 1){ // 如果当前该位是 1
                    if(cnt & 1) st[i] = false; // 奇数 不合法
                    cnt = 0;
                }
            	else cnt ++; // 如果该位为 0，cnt ++
            
            if(cnt & 1) st[i] = false;
        }
        
        // 以下为 DP 过程
        f[0][0] = 1;
        for(int i = 1; i <= m; i ++)
            for(int j = 0; j < 1 << n; j ++)
                for(int k = 0; k < 1 << n; k ++)
                    if((j & k) == 0 && st[j | k])
                        f[i][j] += f[i - 1][k];
        
        cout << f[m][0] << endl;
    }
    
    return 0;
}

最短Hamilton路径 本题源自《算法竞赛进阶指南》

image-20250313085412539

暴力做法不可取，可以用状态压缩DP来求，用整数来表示状态

f [ i , j ] 表示 所有从0到 j，走过的所有点存在 i 的所有路径 的集合

i 得看成一个二进制数，它的每一位分别表示当前这个点是否走过了

这里我们可以利用倒数第二个经过的点来分类，从 0 到 n - 1

image-20250313090245369

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 <algorithm>
#include <cstring>

using namespace std;

const int N = 20, M = 1 << N;

int n;
int w[N][N]; // w 数组存放图中两点之间的距离
int f[M][N]; // f 数组存的是状态

int main(){
    cin >> n;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            cin >> w[i][j];
            
    memset(f, 0x3f, sizeof f);
    
    f[1][0] = 0;
    
    for(int i = 0; i < 1 << n; i ++)
        for(int j = 0; j < n; j ++)
            if(i >> j & 1)
                for(int k = 0; k < n; k ++)
                    if((i - (1 << j)) >> k & 1) // i 减去 j 这个点仍然包含 k
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
    
    cout << f[(1 << n) - 1][n - 1] << endl;
    return 0;
}

树形DP

没有上司的舞会 本题源自《算法竞赛进阶指南》

image-20250313092339847

树形DP并没有那么难，但需要适应这种思维方式

image-20250313093621433

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 <algorithm>
#include <cstring>
using namespace std;

const int N = 6e3 + 10;

int n;
int happy[N];
int h[N], e[N], ne[N], idx;
int f[N][2];
bool has_father[N];

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u){
    f[u][1] = happy[u];
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        dfs(j);
        
        f[u][0] += max(f[j][0], f[j][1]);
        f[u][1] += f[j][0];
    }
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) scanf("%d", &happy[i]);
    
    memset(h, -1, sizeof h);
    
    for(int i = 0; i < n - 1; i ++){
        int a, b;
        scanf("%d%d", &a, &b); // b 是 a 的父节点
        has_father[a] = true;
        add(b, a);
    }
    
    int root = 1;
    while(has_father[root]) root ++;
    
    dfs(root);
    
    printf("%d\n", max(f[root][0], f[root][1]));
    
    return 0;
}

记忆化搜索

记忆化搜索 是动态规划的一种方式：递归求解每一个状态（而不是循环）

每一道动态规划问题都可以用递归的方式来写！

记忆化搜索：循环稍微慢些，可能会爆栈，但是代码复杂度低！

滑雪

image-20250313102041496

image-20250313103751800

DP问题能做的前提：拓扑图，图中不存在环！该题意已说明不可能存在环！

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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 3e2 + 10;

int n, m;
int h[N][N]; // 每个点存放的高度
int f[N][N];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dp(int x, int y){
    int &v = f[x][y]; // 所有写 v 的地方等价于写 f[x][y]
    if(v != -1) return v;
    
    v = 1; // v 表示路径：最小值为 1
    for(int i = 0; i < 4; i ++){
        int a = x + dx[i], b = y + dy[i];
        if(a >= 1 && a <= n && b >= 1 && b <= m && h[a][b] < h[x][y])
            v = max(v, dp(a, b) + 1);
    }
    return v;
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            scanf("%d", &h[i][j]);
    
    memset(f, -1, sizeof f);
    
    int res = 0;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            res = max(res, dp(i, j)); // 这里不能直接调用f[i][j]，因为没有求出来，dp(i, j)表示求出来的该状态
    
    printf("%d\n", res);
    
    return 0;
}

第六讲——贪心

贪心算法很难证明其正确性，没有常用的模板和套路（DP起码有套路），所以贪心非常难

对于一个贪心问题，先去试一些做法，试完后举一些例子，看一下自己的做法是不是对的，如果没有问题的话就尝试去证明自己的算法

贪心每次只是在当前的情况中找到最优解，以此类推在最后中找到最优解

区间问题

有关区间的贪心是一大类问题！一般区间问题都会先排序

区间选点

image-20250315101643680

《雷达设备》也是区间选点问题

  1. 将每个区间按照右端点从小到大排序
  2. 从前往后依次枚举每个区间 如果当前区间中已经包含点，则直接pass；否则，选择当前区间的右端点
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 <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n;
struct Range{
    int l, r;
    bool operator < (const Range &W)const{
        return r < W.r;
    }
}range[N];

int main(){
    cin >> n;
    for(int i = 0; i < n; i ++){
        int l, r;
        cin >> l >> r;
        range[i] = {l, r};
    }
    sort(range, range + n);
    int res = 0, ed = -2e9;
    for(int i = 0; i < n; i ++)
        if(range[i].l > ed){
            res ++;
            ed = range[i].r;
        }
    cout << res << endl;
    return 0;
}

最大不相交区间数量

image-20250315105206964
  1. 将每个区间按照右端点从小到大排序
  2. 从前往后依次枚举每个区间 如果当前区间中已经包含点，则直接pass；否则，选择当前区间的右端点
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 <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n;
struct Range{
    int l, r;
    bool operator < (const Range &W)const{
        return r < W.r;
    }
}range[N];

int main(){
    cin >> n;
    for(int i = 0; i < n; i ++){
        int l, r;
        cin >> l >> r;
        range[i] = {l, r};
    }
    sort(range, range + n);
    int res = 0, ed = -2e9;
    for(int i = 0; i < n; i ++)
        if(range[i].l > ed){
            res ++;
            ed = range[i].r;
        }
    cout << res << endl;
    return 0;
}

区间分组

image-20250315110702026

《畜栏预定》也是区间分组问题

两个区间之间有交集 就会 有矛盾，所以要分成若干组，使得每组内部的区间两两无矛盾

思路如下：

  1. 将所有区间按左端点从小到大排序
  2. 从前往后处理每个区间 判断能否将其放到某个现有的组中（L[ i ] > Max_r）：

​ a. 如果不存在这样的组，则开新组，然后再将其放进去

​ b. 如果存在这样的组，将其放进去，并更新当前组的Max_r

image-20250315112310071

这里可以用 堆 来维护每一个组的 Max_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
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1e5 + 10;

int n;
struct Range{
    int l, r;
    bool operator < (const Range &W)const {
        return l < W.l;
    }
}range[N];

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 0; i < n; i ++){
        int l, r;
        cin >> l >> r;
        range[i] = {l, r};
    }
    
    sort(range, range + n);
    
    priority_queue<int, vector<int>, greater<int>> heap;
    
    for(int i = 0; i < n; i ++){
        auto t = range[i];
        if(heap.empty() || heap.top() >= t.l) heap.push(t.r);
        else{
            int s = heap.top();
            heap.pop();
            heap.push(t.r);
        }
    }
    
    cout << heap.size() << endl;
    
    return 0;
}

区间覆盖

image-20250315140747737

思路如下：

  1. 先将所有区间按照左端点从小到大排序

  2. 从前往后依次枚举每个区间，在所有能覆盖 start 的区间中，选择右端点最大的区间

    然后将 start 更新成右端点的最大值

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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int n;
struct Range{
    int l, r;
    bool operator < (const Range &W)const{
        return l < W.l;
    }
}range[N];

int main(){
    int st, ed;
    cin >> st >> ed;
    
    cin >> n;
    for(int i = 0; i < n; i ++){
        int l, r;
        cin >> l >> r;
        range[i] = {l, r};
    }
    sort(range, range + n);
    
    int res = 0;
    bool success = false;
    for(int i = 0; i < n; i ++){
        int j = i, r = -2e9; // r表示当前的最大值
        while(j < n && range[j].l <= st){
            r = max(r, range[j].r);
            j ++;
        }
        if(r < st){
            res = -1;
            break;
        }
        res ++;
        if(r >= ed){
            success = true;
            break;
        }
        st = r;
        i = j - 1;
    }
    
    if(!success) res = -1;
    cout << res << endl;
    
    return 0;
}

Huffman树

合并果子 是一个非常经典的贪心问题

image-20250315143859977

这是一个经典的哈夫曼问题：哈夫曼树一定是一棵完全二叉树

答案就是哈夫曼树所有节点的总权重之和！

思路：每次贪心地挑出来最小的两堆进行合并，知道所有的数都被合并过！

求解的两个原则：

  1. 权值最小的两个点，深度 一定 最深，且 可以 互为兄弟节点
  2. n 个点的哈夫曼问题转化为 n - 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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

int main(){
    int n;
    cin >> n;
    
    priority_queue<int, vector<int>, greater<int>> heap;
    
    while(n --){
        int x;
        cin >> x;
        heap.push(x);
    }
    
    int res = 0;
    while(heap.size() > 1){
        int a = heap.top(); heap.pop();
        int b = heap.top(); heap.pop();
        res += a + b;
        heap.push(a + b);
    }
    
    cout << res << endl;
    return 0;
}

排序不等式

排队打水

image-20250315202120699 image-20250315202601830

核心思想：按照从小到大的顺序排队，总时间最小

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

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;
int t[N];
int n;

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> t[i];
    
    sort(t, t + n);
    LL res = 0;
    for(int i = 0; i < n; i ++) res += t[i] * (n - i - 1);
        
    cout << res << endl;
    return 0;
}

绝对值不等式

货仓选址

image-20250315204323119 image-20250315205233755

直觉上就是放中间最好，因此会先试用 中位数（奇数个则是中位数的位置，偶数个则是中间两个数的中间）

采用分组的概念：第一个和倒数第一个，第二个和倒数第二个… 为一组

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

using namespace std;

const int N = 1e5 + 10;

int a[N];
int n;

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i];
    sort(a, a + n);
    
    int res = 0;
    for(int i = 0; i < n; i ++) res += abs(a[i] - a[n / 2]);
    
    cout << res << endl;
    
    return 0;
}

推公式

耍杂技的牛

image-20250315211328890

将所有的牛按照 wi + si 从小到大的顺序排，最大的危险系数一定是最小的

image-20250315213658399

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

using namespace std;

const int N = 5e4 + 10;

typedef pair<int, int> PII;

int n;
PII cow[N];

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 0; i < n; i ++){
        int w, s;
        cin >> w >> s;
        cow[i] = {w + s, w};
    }
    sort(cow, cow + n);
    int res = -2e9, sum = 0;
    for(int i = 0; i < n; i ++){
        int w = cow[i].second, s = cow[i].first - w;
        res = max(res, sum - s);
        sum += w;
    }
    cout << res << endl;
    return 0;
}

第七讲——时空复杂度分析

时间分析

image-20250316085233929

如何分析代码时间复杂度？

  1. 纯循环
  2. 递归（主定理）

并查集 O(nlogn) 双指针 O(n) 堆删除添加操作 O(logn) 哈希表平均情况 O(1)

搜索问题的计算量如何算？ 算该函数执行多少次就行了 O( n * n ! )

图的深度优先遍历和宽度优先遍历 O(n + m)

image-20250303135342562

image-20250304213820432

image-20250304214029285

朴素筛法 O(n logn) 埃式筛法 O(n loglogn) 线性筛法 O(n)

辗转相除法 O(logn) 快速幂 O(logn)

动态规划问题的计算量 = 状态数量 * 状态转移的计算量

空间分析

网速的带宽 8M 指的是 8M bit = 1 MB

1
cout << sizeof f << endl; // 单位是字节(Byte)

只开不用一般来说不会MLE，用了就会MLE

递归也是需要空间的：快排没有开额外数组，但递归会需要系统栈，因此空间复杂度也是O(log n)

第八讲——高级数据结构

并查集

树状数组

树状数组是一个相对比较简单的数据结构，难点不在树状数组本身

数据结构典型代表：线段树、spley（平衡树）、块状链表

树状数组的两个应用：

  1. 快速求前缀和 O(log n)
  2. 修改某一个数 O(log n)

树状数组可以将两个操作进行折中，使得时间复杂度降低

image-20250325100150508

树状数组是基于二进制的想法来解决这个问题

将 [0 , x] 分为若干个区间：

image-20250325101607604

image-20250325102227591

不同 C 的形象表示

image-20250325102944000

下面来看一下 C 之间的具体关系：

image-20250325103926576

每一次去掉最后一个1，可以通过lowbit运算来求得

下面来看如何找到数字 x 的子节点呢？先是自己，然后每次去掉一个lowbit(x)

如何通过子节点来找父节点呢？（重要！对应修改操作）找的是直接影响的区间（唯一！），而不是间接影响的区间

p = x + lowbit(x)，迭代逐渐往上继续修改

1
2
3
4
5
6
7
// 树状数组基本操作：两个操作都是 O(log n)

// 修改操作：
for(int i = x; i <= n; i += lowbit(i)) tr[i] += C;

// 查询操作：
for(int i = x; i ; i -= lowbit(i)) tr[i] -= C;

线段树

可持久化数据结构

平衡树

AC自动机

stl用法

set 以及 unordered_set 都可以用 .insert().second 判断是否有重复元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<set>
using namespace std;
int main()
{
    set<char>a;
    a.insert('a');
    if(a.insert('a').second){
        printf("插入成功");
    }
    else{
        printf("插入失败");
    }
    return 0;
}

根据结果可知，向集合中插入重复元素时，set.insert().second的返回值为false

LCA算法：二叉树的最近公共祖先

字符和空格异或可以切换大小写

Donate
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2015-2025 wellkilo
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信