数据结构与算法
ZOU
 2021-12-22 11:24:08      23.1k 字  108 分钟  

数据范围反推复杂度及算法内容

一般ACM或者笔试题的时间限制是1秒或2秒。在这种情况下，C++代码中的操作次数控制在∼为最佳。

下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：

  1. ，指数级别。dfs+剪枝，状态压缩dp。
  2. ，。floyd，dp，高斯消元。
  3. ，，。dp，二分，朴素版Dijkstra，朴素版Prim，Bellman-Ford。
  4. ，。块状链表，分块，莫队。
  5. ，。各种sort，线段树，树状数组，set/map，heap，拓扑排序，dijkstra+heap，prim+heap，spfa，求凸包，求半平面交，二分，CDQ分治，整体二分。
  6. ，和常数较小的 。单调队列、 hash、双指针扫描、并查集，kmp、AC自动机。常数比较小的 的做法：sort、树状数组、heap、dijkstra、spfa。
  7. ，。双指针扫描、kmp、AC自动机、线性筛素数。
  8. ，。判断质数。
  9. ，。最大公约数，快速幂。
  10. ，。高精度加减乘除。
  11. ，。k表示位数，高精度加减，FFT/NTT。

作者：yxc
链接：https://www.acwing.com/blog/content/32/
来源：AcWing

1 基础算法

1.1 快速排序

在一次排序中找到一个位置，通过左右交换的方式使得该位置之前全部小于这个位置上的数（以升序为例），之后的数全部大于该位置上的数。由此确定序列中第一个数。然后以该位置为分界点分为左右两个序列，分别递归即可确定整个序列的排序。

因为二分且递归，平均时间复杂度为。

  1. 关于为什么i和j要取l-1和r+1：使用的是do while循环，每次先移动，再交换。do while和l-1，r+1的写法其实都有关边界，关于边界问题，建议直接背下来。
  2. 为什么x要选取中间点，选取左边界和右边界也是可以的，只是中间点更加不容易出现最坏情况，所以推荐采用这种写法。
1
2
3
4
5
6
7
8
9
10
11
void quickSort(int a[], int l, int r) {
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = a[l+r>>1];
    while (i < j) {
        do i++; while (a[i] < x);
        do j--; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }
    quickSort(a, l, j);
    quickSort(a, j+1, r);
}

1.2 归并排序

归并排序的思想是：将序列中排好序的归并，得到一个新的更长的排好序的序列。最开始的序列长度为1（长度为1的序列一定排好序），逐渐扩大为2，再4，以此类推。

因为序列长度由大到小，所以应该先递归，再进行其他操作。代码中的i表示的归并序列A的下标，j表示的是归并序列B的下标，k表示temp数组下标。temp数组的存在是必要的，用于存放归并好的A+B序列，并在结束归并后必须返还给原a数组，因为接下来的归并需要用到归并好的序列。

归并排序稳定，时间复杂度为。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int a[N], n, temp[N];

void mergeSort(int l, int r) {
    if (l >= r) return;
    int mid = l + r >> 1;
    mergeSort(l, mid);
    mergeSort(mid + 1, r);
    
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) temp[k++] = a[i++];
        else temp[k++] = a[j++];
    }
    while (i <= mid) temp[k++] = a[i++];
    while (j <= r) temp[k++] = a[j++];
    
    for (i = l, k = 0; i <= r; i++, k++) a[i] = temp[k];
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    mergeSort(0, n - 1);
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    
    return 0;
}

1.3 二分

二分有以下两种情况，两种情况的选择是先写check条件，根据条件判断r = mid或者r = mid + 1，再确定mid是否需要加1。

版本1

当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1，计算mid时不需要加1。

1
2
3
4
5
6
7
8
int bsearch_1(int l, int r) {
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

版本2

当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid，此时为了防止死循环，计算mid时需要加1。

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

对本题而言，一个包含重复元素的有序序列，要求输出某元素出现的起始位置和终止位置，找不到就输出-1 -1。

这里很明显需要求解两次二分，一次是某元素出现的起始位置，一次是终止位置，以下解法刚好演示了上述整数二分的两种可能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int n, q, a[N];

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    while (q--) {
        int x;
        scanf("%d", &x);
        
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (a[mid] >= x) r = mid;
            else l = mid + 1;
        }
        if (a[l] != x) printf("-1 -1\n");
        else {
            printf("%d ", l);
            int r = n - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (a[mid] <= x) l = mid;
                else r = mid - 1;
            }
            printf("%d\n", l);
        }
        
    }
    
    return 0;
}

1.4 高精度

高精度数据一般使用数组存储。

1.4.1 高精度加法

给定两个正整数（不含前导 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
#include <iostream>
#include <vector>
using namespace std;
vector<int> add(vector<int> &a, vector<int> &b) {
    if (a.size() < b.size()) return add(b, a);
    int t = 0;
    vector<int> res;
    for (int i = 0; i < a.size() || t; i++) {
        t += a[i];
        if (i < b.size()) t += b[i];
        res.push_back(t % 10);
        t /= 10;
    }
    while (res.size() > 1 && res.back() == 0)
        res.pop_back();
    return res;
}
int main() {
    vector<int> a, b, res;
    string s1, s2;
    cin >> s1 >> s2;
    for (int i = s1.length() - 1; i >=0; i--)
        a.push_back(s1[i] - '0');
    for (int i = s2.length() - 1; i >=0; i--)
        b.push_back(s2[i] - '0');
    res = add(a, b);
    for (int i = res.size() - 1; i >= 0; i--)
        cout << res[i];
    return 0;
}

1.4.2 高精度减法

给定两个正整数（不含前导 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
#include <iostream>
#include <vector>
using namespace std;
vector<int> sub(vector<int> &a, vector<int> &b) {
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); i++) {
        t = a[i] - t;
        if (i < b.size()) t -= b[i];
        c.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}
int main() {
    bool flag = true;   //是否a>b
    vector<int> a, b;
    string s1 = "", s2 = "";
    cin >> s1 >> s2;
    for (int i = s1.length() - 1; i >= 0; i--) 
        a.push_back(s1[i] - '0');
    for (int i = s2.length() - 1; i >= 0; i--) 
        b.push_back(s2[i] - '0');
    if (a.size() < b.size()) {
        flag = false;
    } else if (a.size() == b.size()) {
        for (int i = a.size() - 1; i >= 0; i--) {
            if (a[i] < b[i]) {
                flag = false;
                break;
            } else if (a[i] > b[i]) break;
        }
    }
    vector<int> res;
    if (flag) {
        res = sub(a, b);
    } else {
        res = sub(b, a);
        cout << "-";
    }
    for (int i = res.size() - 1; i >= 0; i--)
        cout << res[i];
    return 0;
}

1.4.3 高精度乘法

给定两个非负整数（不含前导 0）A和B，请你计算A×B的值。

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 <vector>
using namespace std;
vector<int> mul(vector<int>& A, int b) {
    vector<int> res;
    int t = 0;
    for (int i = 0; i < A.size() || t; i++) {
        if (i < A.size()) t += b * A[i];
        res.push_back(t % 10);
        t /= 10;
    }
    while (res.size() > 1 && res.back() == 0)
        res.pop_back();
    return res;
}
int main() {
    string s;
    int b;
    vector<int> A, res;
    cin >> s >> b;
    for (int i = s.length() - 1; i >= 0; i--) 
        A.push_back(s[i] - '0');
    res = mul(A, b);
    for (int i = res.size() - 1; i >= 0; i--) 
        cout << res[i];
    return 0;
}

1.4.4 高精度除法

给定两个非负整数（不含前导0）A和B，请你计算A/B的商和余数。

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 <vector>
#include <algorithm>
using namespace std;
vector<int> div(vector<int> &A, int b, int &r) {
    r = 0;
    vector<int> res;
    for (int i = A.size() - 1; i >= 0; i--) {
        r = r * 10 + A[i];
        res.push_back(r / b);
        r %= b;
    }
    reverse(res.begin(), res.end());
    while (res.size() > 1 && res.back() == 0)
        res.pop_back();
    return res;
}
int main() {
    string s;
    int b, r;
    vector<int> A, res;
    cin >> s >> b;
    for (int i = s.length() - 1; i >= 0; i--)
        A.push_back(s[i] - '0');
    res = div(A, b, r);
    for (int i = res.size() - 1; i >= 0; i--)
        cout << res[i];
    cout << endl << r << endl;
    return 0;
}

1.5 前缀和

1.5.1 一维前缀和

输入一个长度为 n 的整数序列。接下来再输入 m 个询问，每个询问输入一对 l, r。对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。n，m可能比较大。

适用于需要大量计算序列中某一部分和的情况。

维护一个 s数组，其中s[i]表示的含义是前 i 个数据的和。求第 l 到第 r 个数的和时，只需要S[r] - s[l - 1]即可。

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 maxn = 1e5 + 10;
int a[maxn], s[maxn];
int main() {
    int n, m, l, r;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        s[i] = s[i-1] + a[i];
    }
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &l, &r);
        int res = s[r] - s[l-1];
        printf("%d\n", res);
    }
    return 0;
}

1.5.2 二维前缀和

输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1, y1, x2, y2 表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。

s[i][j]表示的是从 0, 0 到 i, j 的矩形中所有数的和。

输入时s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];。

输出时int res = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
int a[1010][1010], s[1010][1010];
int main() {
    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
        }
    }
    for (int i = 0; i < q; i++) {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        int res = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
        printf("%d\n", res);
    }
    return 0;
}

1.6 差分

1.6.1 一维差分

输入一个长度为 n 的整数序列。接下来输入 m 个操作，每个操作包含三个整数 l, r, c, 表示将序列中 [l, r] 之间的每个数加上 c。请你输出进行完所有操作后的序列。n, m可能会很大。

定义一个b数组，。理所应当b[1] = a[1]。

由差分数组的定义可知，当批量修改某些连续的a[i]值时，只需对 b 数组两个数做修改，假设修改区间为[l, r]，那么只需要修改b[l]和b[r+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 <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int a[N], b[N];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        b[i] = a[i] - a[i-1];
    }
    while (m--) {
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        b[l] += c;
        b[r+1] -= c;
    }
    for (int i = 1; i <= n; i++) {
        a[i] = a[i-1] + b[i];
        printf("%d ", a[i]);
    }
    
    return 0;
}

1.6.2 差分矩阵

输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1, y1, x2, y2, c，其中 (x1, y1) 和 (x2, y2) 表示一个子矩阵的左上角坐标和右下角坐标。每个操作都要将选中的子矩阵中的每个元素的值加上 c。请你将进行完所有操作后的矩阵输出。

可以看成二维前缀和的逆运算，a[i][j] 等于b数组中从(0, 0)到(i, j)的和。b 数组的影响范围是其右下角。

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

1.7 位运算

1
2
3
if (k & 1)表示k二进制的最后一位是否是1，是的话返回true。
求n二进制的第k位数字：n >> k & 1 
返回n的最后一位二进制1(十进制)：n & -n 或者直接用 lowbit(n)

1.8 离散化

离散化问题解决区间庞大但是实际使用的数不多的情况。思路是将使用到的区间点进行映射储存起来，使用时再查找。

该代码涉及到的知识点包括二分，前缀和，离散化，比较综合，可以多看。

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>
#include <algorithm>  
using namespace std;
typedef pair<int, int> PII;
const int N = 3e5 + 10;
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;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        int x, c;
        scanf("%d%d", &x, &c);
        alls.push_back(x);
        add.push_back({x, c});
    }
    for (int i = 0; i < m; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        alls.push_back(l);
        alls.push_back(r);
        query.push_back({l, 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);
        int r = find(item.second);
        int res = s[r] - s[l-1];
        printf("%d\n", res);
    }
    return 0;
}

1.9 区间合并

v[i].second = max(v[i].second, v[i-1].second);
要用整个区间的最靠右的数值进行比较，以[1,9]，[2,3]，[4,5]来举例子，实际上这是一个区间，但是两两比较答案为2。

pair的默认sort排序规则是按从小到大顺序先排first，相等时再排second，这里正符合我们的预期。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;

int main() {
    int n;
    scanf("%d", &n);
    vector<pii> v;
    for (int i = 0; i < n ; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        v.push_back({l, r});
    }
    
    sort(v.begin(), v.end());
    
    int res = n;
    
    for (int i = 1; i < n; i++) {
        if (v[i].first <= v[i-1].second) {
            res--;
            v[i].second = max(v[i].second, v[i-1].second);
        }
    }
    
    cout << res;
    
    return 0;
}

2 数据结构

2.1 单链表

2.1.1 指针 + 结构体

此处为含头指针的单向链表，实现了插入，删除，查找操作。

做算法题目时不推荐用这种方法，因为要用到new字符，十分花时间，有很大可能会TLE，推荐用下面的数组方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct node {
    int data;
    node* next;
};
node *head = new node;

void insert(int pos, int x) {
    node *p = head;
    for (int i = 0; i < pos; i++) {
        p = p->next;   
    }
    node *q = new node;
    q->data = x;
    q->next = p->next;
    p->next = q;
}

void del(int pos) {
    node *p = head;
    for (int i = 0; i < pos; i++) {
        p = p->next;
    }
    p->next = p->next->next;
}

2.1.2 数组

数组维护单链表的关键在于要存储每个节点的下标的值，ne[N]的作用就在此。此外head是一个头节点，本身并不存储任何数值，但是指向第一个存储数值的节点，head值为-1，第一个值节点下标为0。

关于idx的必要性：idx表示现在插入了多少个数值，即使删除了部分节点，其idx依然可以表示它插入的顺序，这在某些题目中很有用。

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
// head表示头节点下标，idx表示当前节点下标，e是当前的值，ne是下一个的下标
const int N = 1e5 + 10;
int e[N], ne[N], idx, head;

// 初始化，无节点所以head指向-1，如果当前要插入节点，其下标应该为0
// 所以idx为0
void init() {
    head = -1;
    idx = 0;
}

// head储存第一个节点下标
void insertHead(int x) {
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
}

void insert(int k, int x) {
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

void del(int k) {
    ne[k] = ne[ne[k]];
}

2.2 双链表

对于任何链表题目来说，都建议首先划出图形辅助理解。双链表的难点在于插入操作，插入操作需要操作四条线，别忘记了操作完成之后idx++。

谨记访问上下节点是l[k]和r[k]，不是k-1或者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
55
56
57
58
59
60
61
#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int e[N], l[N], r[N], idx;

// 不定义头节点和尾节点，0表示左节点，1表示右节点
void init() {
    l[1] = 0, r[0] = 1;
    idx = 2;
}

// 在下标是k的节点的右边，插入x
void insert(int k, int x) {
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx; // 这两行不可以调换位置
    r[k] = idx;
    idx++;
}

// 删除下标为k的节点
void del(int k) {
    l[r[k]] = l[k];
    r[l[k]] = r[k];
}


int main() {
    init();
    
    int m, k, x;
    cin >> m;
    for (int i = 0; i < m; i++) {
        string op;
        cin >> op;
        // 记住下标是从2开始的，所以要加1
        if (op == "L") {
            cin >> x;
            insert(0, x);
        } else if (op == "R") {
            cin >> x;
            insert(l[1], x);
        } else if (op == "D") {
            cin >> k;
            del(k + 1);
        } else if (op == "IL") {
            cin >> k >> x;
            insert(l[k + 1], x);
        } else {
            cin >> k >> x;
            insert(k + 1, x);
        }
    }
    
    for (int i = r[0]; i != 1; i = r[i])
        cout << e[i] << " ";
    
    return 0;
}

2.3 栈模拟计算器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<iostream>
#include<unordered_map>
#include<stack>
using namespace std;

//存储运算数 运算符
stack<int> num;
stack<char> op;
//建立映射来判断运算优先级
unordered_map<char, int> pr = {
    {'+', 1}, {'-', 1} , {'*', 2}, {'/', 2}
};
//模拟一次算术操作
void eval(){
    int b = num.top(); num.pop();
    int a = num.top(); num.pop();
    char opt = op.top(); op.pop();
    
    int x;
    if (opt == '+') x = a + b;
    else if (opt == '-') x = a - b;
    else if (opt == '*') x = a * b;
    else if (opt == '/') x = a / b;
    
    num.push(x);
}

int main(){
    string str;
    cin >> str;

    for(int i = 0; i < str.size(); i++){
        char c = str[i];
        //读入运算数
        if(isdigit(c)){
            int j = i, x = 0;
            while(j < str.size() && isdigit(str[j])){
                //j++ 迭代不能忘 
                x = x * 10 + str[j++] - '0';
            }
            num.push(x);
            //由于每轮循环有i++,我们需要倒指向最后一个数字
            i = j - 1;
        } else if( c == '(' ){
            //标记一下，括号内数据
            op.push(c);
        } else if( c == ')' ){
            //括号的优先级，先算括号
            while( op.size() && op.top() != '(' ) eval();
            //左括号可以弹出
            op.pop();
        } else{
            //得先把乘除法算了再算加减
            //这里必须得带等于号 我们这题都是正整数计算
            // 0 - 5 + 3 
            //如果不算，上式会被错误计算成 -8
            while( op.size() && pr[op.top()] >= pr[c]) eval();
            //压入新运算符
            op.push(c);
        }
    }
    //清理低优先级操作
    while(op.size()) eval();
    cout << num.top() << endl;
    
    return 0;
}

2.4 单调栈

最常见的情况就是求解序列中每个数左边最靠近它且最小的数。

答案要求是尽可能靠近并且小于它，对于任意其左边某个值x，x左边所有大于等于x的值都没有意义，所以维护的栈必定时刻单调递增。

只需不断将栈顶元素与当前值比较即可，st.top() >= temp就弹出。

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

int main() {
    stack<int> st;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        while (!st.empty() && st.top() >= temp) st.pop();
        if (st.empty()) cout << -1 << " ";
        else cout << st.top() << " ";
        st.push(temp);
    }
    
    return 0;
}

2.5 单调队列

最常见问题就是求滑动窗口的最大最小值，以下即为滑动窗口问题。

推荐使用数组写法，因为数组写法既可以操控队列头，还可以操纵队列尾，这道题目中二者都要用。所以stl中的queue是无法胜任的。不会数组写法的话也可以用deque。

假设要访问一个滑动窗口的最小值，那么对于某个值来说，假设它更小一些，那么在它之前的所有比它大的值都没有意义，因为它们更加早出窗口，而且更大。所以可以时刻维持一个单调递增的队列，最大值镜像即可。

if (!minq.empty() && minq.front() < i - k + 1) minq.pop_front();这句代码不可省略，作用是维系滑动窗口的大小。

while循环处即是在维护队列的单调性，注意到此处用上了pop_bcak()，queue容器是没有该操作的。

还有至关重要的一点是，队列中存储的是最小值or最大值的下标。

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

const int N = 1e6 + 10;
int a[N];
deque<int> minq, maxq;

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < n; i++) {
        if (!minq.empty() && minq.front() < i - k + 1) 
            minq.pop_front();
        while (!minq.empty() && a[i] <= a[minq.back()]) 
            minq.pop_back();
        minq.push_back(i);
        if (i >= k - 1) printf("%d ", a[minq.front()]);
    }
    cout << endl;
    for (int i = 0; i < n; i++) {
        if (!maxq.empty() && maxq.front() < i - k + 1) 
            maxq.pop_front();
        while (!maxq.empty() && a[i] >= a[maxq.back()]) 
            maxq.pop_back();
        maxq.push_back(i);
        if (i >= k - 1) printf("%d ", a[maxq.front()]);
    }
    
    return 0;
}

2.6 KMP

KMP很难，最好天天练习，达到任何时候3分钟之内能将以下模版默写出来就算过关。

ne[i]表示p[i]之前的字符串的最长公共前后缀。

为什么要求这个ne数组呢？因为KMP算法优化的原理就是当匹配到不相等的那一位时，通过已经得到的长串的后缀和短串的前缀匹配成功的最长长度，来确定短串的移动位置，而不是傻傻地让长串向下移动一个字符并让短串从头开始匹配。

KMP的重点在于求ne数组，ne数组可以通过递推的方式求：如果p[ne[i-1]] = p[i - 1]，则说明ne[i] = ne[i - 1] + 1，别忘记了ne表示的是最长公共前后缀。如果不相等，则不断使j = ne[j]，直到相等为止。如果直到j = 0为止还是不相等，则判断p[0]和p[i - 1]的是否相等来决定ne[i]是0或1。

为什么可以用上述求法，原理很复杂，来看这个解析。

得到的ne虽然表示的是p字符串的最长前后缀匹配长度，但是因为这一段长度实际也是p和s匹配上的子字符串，所以具有传递性，也就是说，ne[i]实际可以表示最长的p字符串前缀和s字符串后缀相等的长度。

ne[0] = ne[1] = 0;这句代码是固定的，任何情况下都对，别忘记写。

while循环中为什么要判断j是否为0？因为当j = 0时，ne[j] = 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>
using namespace std;

const int N = 1e5 + 10;
string s, p;    // s是长串，p是短串
int n, m;
int ne[N];  // ne[i]表示p字符串的最长公共前后缀

int main() {
    cin >> n >> p >> m >> s;
    ne[0] = 0;
    ne[1] = 0; // 前后缀长度要小于字符串长度
    for (int i = 2; i < n + 1; i++) {
        int j = ne[i - 1];
        while (j && p[j] != p[i - 1]) j = ne[j];
        if (j != 0) ne[i] = j + 1;
        else {
            if (p[j] == p[i - 1]) ne[i] = 1;
            else ne[i] = 0;
        }
    }
    for (int i = 0, j = 0; i < m; i++) {
        while (j && s[i] != p[j]) j = ne[j];
        if (s[i] == p[j]) j++;
        if (j == n) {
            cout << i - j + 1 << " ";
        }
    }
    
    return 0;
}

2.7 并查集

2.7.1 并查集

现在有n个数，要进行m个操作，操作有两种，分别是M a b，将编号a和b的两个数合并入一个集合。Q a b，查询编号a和b的两个数是否在一个集合内。对于每一个Q查询，返回一个查询结果，YES或者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
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int n, m, father[N];

int find(int a) {   // 路径压缩
    int x = a;
    while (a != father[a]) a = father[a];
    while (x != father[x]) {
        int z = x;
        x = father[x];
        father[x] = a;
    }
    return a;
}

void merge(int a, int b) {
    int fa = find(a), fb = find(b);
    if (fa != fb) father[fa] = fb;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        father[i] = i;
    }
    while (m--) {
        char c;
        int a, b;
        cin >> c >> a >> b;
        if (c == 'M') merge(a, b);
        else {
            if (find(a) == find(b)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
    
    return 0;
}

2.7.2 带权并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
using namespace std;

const int N = 5e4 + 10;
int p[N], d[N];  

int find(int x) {
    if (p[x] != x) {
        int u = find(p[x]); // u是祖宗，在d[x]更新前，p[x]还不能变成祖宗
        d[x] += d[p[x]];
        p[x] = u;
    }
    return p[x];
}

int main() {
    int n, k, cnt = 0;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        p[i] = i;
        d[i] = 0;
    }
    while (k--) {
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);
        if (x > n || y > n) cnt++;
        else {
            int px = find(x), py = find(y);
            if (t == 1) {
                if (px == py && (d[x] - d[y]) % 3) cnt++;
                else if (px != py) {
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }
            } else {
                if (px == py && (d[x] - d[y] - 1) % 3) cnt++;
                else if (px != py) {
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }
    cout << cnt << endl;
    
    return 0;
}

2.8 堆

2.8.1 模拟堆

堆是完全二叉树，完全二叉树有个很棒的性质：假设某个根节点下标为x，那么其左子树下标为2x，右子树为2x + 1。这样用数组来储存读取起来很方便。

模拟堆主要实现五个操作（以小根堆为例）：

  • 插入一个数
  • 求集合当中的最小值
  • 删除最小值
  • 删除任意一个元素
  • 修改任意一个元素

这五个操作都可以用up和down两个方法来实现。down函数的作用是将某个不符合堆定义的节点不断下沉，直到其到达合适的位置，up同理。时间复杂度为。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void down(int u) {
    int t = u;
    if (u * 2 <= cur_size && h[t] > h[u * 2])
        t = u * 2;
    if (u * 2 + 1 <= cur_size && h[t] > h[u * 2 + 1])
        t = u * 2 + 1;
    if (u != t) {
        swap(h[u], h[t]);
        down(t);
    }
}
void up(int u) {
    if (u / 2 > 0 && h[u] < h[u / 2]) {
        swap(h[u], h[u / 2]);
        up(u / 2);
    }
}

2.9 哈希表

2.9.1 模拟散列表

核心思路是将庞大的区间离散然后解决冲突问题，之前的离散化过程可以看作哈希的一种特殊情况——保序的离散化。

根据解决冲突方式的不同分为开放寻址法和拉链法，下面代码为拉链法。拉链法原理是采用邻接表，每一个vector储存所有产生的值，例如说1e5 + 4和2e5 + 7离散值相同，都为1，则共同存放在v[1]中。

为什么N取1e5 + 3而不是从前的1e5 + 10。1e5 + 3是大于1e5的最小质数，选择质数能使冲突的次数尽可能少，降低时间复杂度。

int k = (x % N + N) % N这句代码是为了解决cpp中负数取模的问题。在数学上任何数取模都为正数，但是cpp中是负数。这句代码具有通用性，建议记下来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <vector>
using namespace std;

const int N = 1e5 + 3;
vector<int> v[N];

void insert(int x) {
    int k = (x % N + N) % N;
    v[k].push_back(x);
}

bool find(int x) {
    int k = (x % N + N) % N;
    for (int i = 0; i < v[k].size(); i++) {
        if (x == v[k][i]) return true;
    }
    return false;
}

int main() {
    int n, x;
    cin >> n;
    while (n--) {
        char c;
        cin >> c >> x;
        if (c == 'I') {
            insert(x);
        } else {
            if (find(x)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
    
    return 0;
}

2.9.2 字符串哈希

字符串哈希功能十分强大，甚至有时候比KMP更强。

主要思路是将字符转化成P进制的数字，经验表明当P取131或13331时冲突的概率十分十分小，所以可以将转换前后看作一一对应。

转换后的数字可能非常大，要用unsigned long long存储，使用ull依然可能溢出，但是不用担心，溢出后会自动取余。

p[N]用来存储P的次方，因为cpp中写次方稍微麻烦一点，这种写法可以学习一下。

h[r] - h[l - 1] * p[r - l + 1]这句话像前缀和的写法，其中r - l + 1是长度差。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
using namespace std;

typedef unsigned long long ull;

const int N = 1e5 + 10; 
const int P = 131;  // 131为经验值，记住
// 溢出就可取余
ull h[N], p[N]; // h[N]存储转换后的数，p[N]存储P的n次方

ull get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
    int n, m;
    string str;
    cin >> n >> m >> str;
    
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + str[i-1];   // 自动获取字符的ascii值
    }
    
    while (m--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if (get(l1, r1) == get(l2, r2)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    
    return 0;
}

2.10 Trie

Trie树是用来高效地存储和查找字符串集合的数据结构。

题目描述：维护一个字符串集合，支持两种操作：I x向集合中插入一个字符串x；Q x询问一个字符串在集合中出现了多少次。

Trie树中有个二维数组son[N][26]，表示当前结点的儿子，如果没有的话，可以等于++idx。Trie树本质上是一颗多叉树，对于字母而言最多有26个子结点。所以这个数组包含了两条信息。比如：son[1][0] = 2表示1结点的一个值为a的子结点为结点2。如果son[1][0] = 0，则意味着没有值为a子结点。这里的son[N][26]相当于链表中的ne[N]。

从y总给出的代码可以看出，idx的操作总是idx++，这就保证了不同的idx值对应不同的结点。因此可以利用idx把结构体内两个属性联系在一起了。因此，idx可以理解为结点。

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

const int N = 1e5 + 10;
int son[N][26], cnt[N], idx; // son[1][0] = 2表示第一条子树的a下一个节点为2

void insert(string s) {
    int p = 0;
    for (int i = 0; i < s.size(); i++) {
        int u = s[i] - 'a';
        if (!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;
}

int query(string s) {
    int p = 0;
    for (int i = 0; i < s.size(); i++) {
        int u = s[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        string c, s;
        cin >> c >> s;
        if (c == "I") insert(s);
        else cout << query(s) << endl;
    }
    
    return 0;
}

3 贪心

3.1 区间贪心

3.1.1 区间不相交

记住是按右端点从小到大排序（也可以按左端点从大到小排序）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;

bool cmp(pii a, pii b) {
    return a.second < b.second;
}

int main() {
    int n, res = 1;
    cin >> n;
    vector<pii> vp;
    for (int i = 0; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        vp.push_back({x, y});
    }
    sort(vp.begin(), vp.end(), cmp);
    int end = vp[0].second;
    for (int i = 1; i < n; i++) {
        if (end < vp[i].first) {
            res++;
            end = vp[i].second;
        }
    }
    cout << res;

    return 0;
}

3.1.2 区间选点

同上，如果都是闭区间问题的话代码完全相同。

3.1.3 区间分组

heap用来维护所有组的最大右端点，top()值表示的是所有最大右端点中最小的值，如果某个区间的左端点甚至小于等于这个最小值，那么说明它一定不能放进该组内，必须开一个新组heap.push(el.second);。

如果一个区间的左端点比最小组的右端点要大，则放在该组中。heap.pop(), heap.push(el.second);。

每组去除右端点最小的区间，只保留一个右端点较大的区间，这样heap有多少区间，就有多少组。

时间复杂度是。

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

typedef pair<int, int> pii;
vector<pii> vp;
priority_queue<int, vector<int>, greater<int>> heap;

bool cmp(pii a, pii b) {
    return a.first < b.first;
}

int main() {
    int n, x, y;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &x, &y);
        vp.push_back({x, y});
    }
    sort(vp.begin(), vp.end(), cmp);
    for (int i = 0; i < n; i++) {
        pii el = vp[i];
        if (heap.empty() || heap.top() >= el.first)
            heap.push(el.second);
        else {
            heap.pop();
            heap.push(el.second);
        }
    }
    cout << heap.size();
    
    return 0;
}

3.1.4 区间覆盖

区间覆盖问题是指给定一个若干个闭区间区间，问其中至少选择多少个才能将某个给定的闭区间覆盖。

核心思路是：

  1. 按左端点从小到大排序（我们期望找到的区间应该是重叠长度尽可能少的，按这种排序方式符合我们的要求，甚至找到正好重叠的，极度满足强迫症）
  2. 从前往后枚举找到左端点小于start并且end最大的区间
  3. 用end更新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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
vector<pii> vp;

bool cmp(pii a, pii b) {
    return a.first < b.first;
}

int main() {
    int st, ed, n, res = 0;
    scanf("%d%d%d", &st, &ed, &n);
    for (int i = 0; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        vp.push_back({x, y});
    }
    sort(vp.begin(), vp.end(), cmp);
    bool flag = false;
    for (int i = 0; i < n; i++) {
        int j = i, r = -2e9;
        while (j < n && vp[j].first <= st) {
            r = max(r, vp[j].second);
            j++;
        }
        if (r < st) {   // 出现断层或者所有区间小于st
            flag = false;
            break;
        }
        res++;
        if (r >= ed) {
            flag = true;
            break;
        }
        i = j - 1;  // 那些end没有vp[j]大的都无用
        st = r;
    }
    if (!flag) cout << -1 << endl;
    else cout << res << endl;
    
    return 0;
}

这里再来谈一个容易错的地方，一开始r < st的判断我是这样写的：

1
2
3
4
if (r < st) {
    cout << -1 << endl;
    return 0;
}

这样写是会报错的，无法通过以下用例

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

后来改成以下代码就成功通过了，原因是成功的判断条件只有一个，那就是r >= ed，哪怕是正常结束循环也可能无法覆盖，所以需要添加一个flag来判断成功与否。

1
2
3
4
if (r < st) {
    flag = false;
    break;
}

3.2 推公式

N只奶牛决定叠罗汉。表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。这 N 头奶牛中的每一头都有着自己的重量 Wi 以及自己的强壮程度 Si。一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。

这道题的贪心衡量指标是w + s，w + s小的要放在更上面。

证明方法是将中间任意两头牛进行交换，得到交换前后的最大风险值，可以发现当w + s更小值在上时，得到的最大风险值更小。

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 <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
vector<pii> v;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int w, s;
        cin >> w >> s;
        v.push_back({w + s, s});
    }
    sort(v.begin(), v.end());
    int res = -2e9, sum = 0;
    for (int i = 0; i < n; i++) {
        int s = v[i].second, w = v[i].first - s;
        res = max(res, sum - s);
        sum += w;
    }
    cout << res << endl;
    
    return 0;
}

4 搜索

4.1 DFS

DFS可以用来暴力求解动态规划问题，如果实在想不到动态规划问题该怎么写，可以先用DFS偷一点分。时间复杂度一般为指数级别。DFS可以用递归或者递推实现，下面的代码使用递归。

4.1.1 背包问题

有n件物品，每件物品重量为w[i]，价值为c[i]。如果需要选出若干物品放入一个容量为v的背包中，问如何放才能在重量不超过v的基础上使得总价值最大。

  • 常规递归解法
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 maxn = 30;
int n, v, maxValue = 0, w[maxn], c[maxn];

void DFS(int index, int sumW, int sumC) {
    if (index == n) {
        if (sumW <= v && sumC > maxValue) maxValue = sumC;
        return;
    }
    DFS(index + 1, sumW, sumC);     // 不选该物品的分支
    DFS(index + 1, sumW + w[index], sumC + c[index]);   // 选的分支
}

int main() {
    scanf(“%d %d”, &n, &v);
    for (int i = 0; i < n; i++) scanf(“%d”, &w[i]);
    for (int i = 0; i < n; i++) scanf(“%d”, &c[i]);
    DFS(0, 0, 0);   // 初始index，sumW和sumC都是0
    printf(“%d”, maxValue);
}
  • 剪枝改进
1
2
3
4
5
6
7
8
void DFS(int index, int sumW, int sumC) {
    if (index == n) return;
    DFS(index + 1, sumW, sumC);
    if (sumW + w[index] <= v) {
        if (sumC + c[index] > maxValue) maxValue = sumC + c[index];
        DFS(index + 1, sumW + w[index], sumC + v[index]);
    }
}

4.1.2 求子序列

该一类问题描述给定一个序列，枚举这个序列的所有子序列（可以不连续），以下给出一个具体案例：

给定n个整数（可能为负），从中选择k个数，使得这k个数之和恰好等一给定的一个整数x，如果有多种方案，则从其中选择平方和最大的一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// maxSumSqu为最大平方和
int n, k, x, maxSumSqu = -1, a[maxn];
// temp存放临时方案，ans存放平方和最大的方案
vector<int> temp, ans;

void DFS(int index, int tempK, int sum, int sumSqu) {
    if (tempK = k && sum == x) {
        if (sumSqu > maxSumSqu) {
            maxSumSqu = sumSqu;
            ans = temp;
        }
        return;
    }
    if (tempK > k || index == n || sum > x) return;
    temp.push_back(a[index]);
    DFS(index + 1, tempK + 1, sum + a[index], sumSqu + a[index] * a[index]);
    temp.pop_back();
    DFS(index + 1, tempK, sum, sumSqu);
}

4.2 BFS

4.2.1 BFS模版

一般使用队列实现：

1
2
3
4
5
6
7
8
9
10
void BFS(int s) {
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        取出队首元素top;
        访问队首元素top（例如print）;
        将队首元素出队;
        将top的下一层结点中未曾入队的结点全部入队，并设置为已入队;
    }
}

4.2.2 迷宫找出口

给定一个n * m大小的迷宫，其中*代表不可通过的墙壁，而“.”代表平地，s表示起点，t表示终点。移动过程中，如果当前位置时（x, y）（下标从0开始），且每次只能往上下左右移动，求从起点s到终点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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <queue>
using namespace std;

const int maxn = 100;

struct Node {
    int x, y;
    int step;   // 表示步长
} s, t, node;

int n, m;
char maze[maxn][maxn];
bool inq[maxn][maxn] = {false};
int x[4] = {0, 0, 1, -1};
int y[4] = {1, -1, 0, 0};

// 检测位置是否有效
bool test(int x, int y) {
    if (x >= n || x < 0 || y >= m || y < 0) return false;
    if (maze[x][y] == ‘*’) return false;
    if (inq[x][y] == true) return false;
    return true;
}

int BFS() {
    queue<Node> q;
    q.push(s);
    while (!q.empty()) {
        Node top = q.front();
        q.pop();
        if (top.x = t.x && top.y == t.y) return top.step;
        for (int i = 0; i < 4; i++) {
            int newx = top.x + x[i];
            int newy = top.y + y[i];
            if (test(newx, newy)) {
                node.x = newx;
                node.y = newy;
                node.step = top.step + 1;
                q.push(node);
                inq[newx][newy] = true;
            }
        }
        return -1;
    }
}

int main() {
    scanf(“%d%d”, &n, &m);
    for (int i = 0; i < n; i++) {
        getchar();
        for (int j = 0; j < m; j++) {
            maze[x][y] = getchar();
        }
        maze[x][m+1] = ‘\0’;
    }
    scanf(“%d%d%d%d”, &s.x, &s.y, &t.x, &t.y);
    s.step = 0;
    printf(“%d”, BFS());
    
    return 0;
}

5 图

5.1 图的储存方法

通常采用邻接矩阵和邻接表储存，邻接矩阵采用二维数组，下标表示端点，值表示权值；邻接表一般使用链表储存，也可以用动态数组vector，更易理解。

5.1.1 邻接表

1
2
3
4
5
6
7
8
9
10
11
struct Node {   // v是端点编号，w是权值
    int v, w;
    Node (int _v, _w) {     // 添加构造函数方便添加结点
        v = _v;
        w = _w;
    }
};
vector<Node> adj[100];
// 添加一条从1号到3号顶点的无向边，权值为4
adj[1].push_back(Node(3,4));
adj[3].push_back(Node(1,4));

5.2 图的遍历序列

以下解法都是针对图的通解（不针对联通分量），如果确定图是联通分量或强联通分量，则只需依次DFS即可。

5.2.1 邻接矩阵(DFS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int maxn = 1000;
const int inf = 1000000000;
int n, g[maxn][maxn];
bool vis[maxn] = {false};
void DFS(int v, int depth) {
    vis[v] = true;
    // 如果要对v进行一些操作，可以在这里进行
    // 下面对所有从u出发能达到的分支顶点进行枚举
    for (int i = 0; i < n; i++) {
        if (vis[i] == false && g[v][i] != inf) {
            DFS(i, depth+1);
        }
    }
}
void DFSTrave() {
    for (int i = 0; i < n; i++) {
        if (vis[i] == false) {
            DFS(i, 1);
        }
    }
}

5.2.2 邻接表(DFS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int maxn = 1000;
int n;  // 表示端点数
vector<int> adj[maxn];
bool vis[maxn] = {false};
void DFS(int v, int depth) {
    vis[v] = true;
    // 如果要对v进行一些操作，可以在这里进行
    // 下面对所有从u出发能达到的分支顶点进行枚举
    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i];
        if (vis[u] == false) {
            DFS(u, depth+1);
        }
    }
}
void DFSTrave() {
    for (int i = 0; i < n; i++) {
        if (vis[i] == false) {
            DFS(i, 1);
        }
    }
}

5.3 拓扑排序

首先说明一下，拓扑排序和快排，归并排序，堆排序这样对一个序列的排序是不同的。拓扑排序是对图的排序，简而言之一句话就是如果我是你的父节点，我就一定出现在你前面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, m, d[N];
vector<int> v[N], res;
queue<int> q;

bool topoSort() {
    for (int i = 1; i <= n; i++) {
        if (d[i] == 0) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        res.push_back(u);
        for (int i = 0; i < v[u].size(); i++) {
            int j = v[u][i];
            d[j]--;
            if (d[j] == 0) {
                q.push(j);
            }
        }
    }
    if (res.size() == n) return true;
    else return false;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
        d[b]++;
    }
    if (topoSort()) {
        for (int i = 0; i < n; i++) {
            cout << res[i] << " ";
        }   
    } else cout << -1;

    return 0;
}

5.4 朴素Dijkstra

结构体写法可以换成pair，可以加快一些运行速度。

其中最不好理解的一部分大概就是求解未到达点中距离最小的一个点。事实上，这也是时间复杂度的原因。朴素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
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int N = 1e5 + 10, INF = 0x3fffffff;
int n, m, d[N];
vector<pii> g[N];
bool vis[N];

void Dijkstra(int s) {
    fill(d, d + N, INF);
    d[s] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1, minn = INF;
        for (int j = 0; j < n; j++) {
            if (!vis[j] && minn > d[j]) {
                minn = d[j];
                u = j;
            }
        }
        if (u == -1) return;
        vis[u] = true;
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i].first;
            int dis = g[u][i].second;
            if (!vis[v] && d[v] > d[u] + dis) {
                d[v] = d[u] + dis;
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    while (m--) {
        int a, v ,dis;
        scanf("%d%d%d", &a, &v, &dis);
        g[a].push_back({v, dis});
    }
    Dijkstra(1);
    int res = d[n] == INF ? -1 : d[n];
    printf("%d", res);

    return 0;
}

5.5 堆优化Dijkstra

堆优化Dijkstra优化了求解最小距离的部分，时间复杂度降低到了。既可以处理稀疏图，也可以处理稠密图。

堆优化当然更好，考试时优先写堆优化的Dijkstra。

用邻接表来存储图的话，不用care自环，反正根据算法必定会求得一个最短路径。

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 <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

const int N = 1e5 + 10, INF = 0x3fffffff;
int n, m, d[N];
vector<pii> g[N];
priority_queue<pii, vector<pii>, greater<pii>> heap;
bool vis[N];

void Dijkstra_Heap(int s) {
    fill(d, d + N, INF);
    d[s] = 0;
    heap.push({0, s});
    while (!heap.empty()) {
        pii p = heap.top(); heap.pop();
        int u = p.second;
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i].first;
            int dis = g[u][i].second;
            if (!vis[v] && d[v] > d[u] + dis) {
                d[v] = d[u] + dis;
                heap.push({d[v], v});
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    while (m--) {
        int a, v, dis;
        scanf("%d%d%d", &a, &v, &dis);
        g[a].push_back({v, dis});
    }
    Dijkstra_Heap(1);
    int res = d[n] == INF ? -1 : d[n];
    printf("%d", res);
    
    return 0;
}

5.6 Bellman-Ford

Bellman-Ford算法可以求负环，请注意，当有负环而且最短路径可以经过负环时，最短路径是不存在的，因为当不限定次数的时候，可以无限经过该负环使最短路径降低为负无穷。

Bellman算法的原理是首先遍历所有点，每一次遍历都可以确定最短路径树某一层的最短路径。到第n-1次时即可确定整个n层的树的最短。（可以证明，最短路径树一定不超过n层）。这个时候再判断，如果还能修改最短路径，那一定存在负环。

Bellman算法的时间复杂度是。时间复杂度很高，一般不用。

时间复杂度高是因为内层不知道哪一条边可以松弛，所以傻傻地遍历所有边，实际上可以判断出一定是某一条刚刚更新过的，确定了最短路径的边才会更新新的边。这种改进就是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
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

const int N = 510, M = 1e4 + 10, INF = 0x3fffffff;
int n, m, k;
int d[N], backup[N];
vector<pii> g[M];

int Bellman(int s) {
    memset(d, 0x3f3f3f3f, sizeof d);
    d[s] = 0;
    for (int i = 0; i < k; i++) {
        memcpy(backup, d, sizeof d);
        for (int u = 1; u <= n; u++) {
            for (int j = 0; j < g[u].size(); j++) {
                int v = g[u][j].first;
                int dis = g[u][j].second;
                d[v] = min(d[v], backup[u] + dis);
            }
        }
    }
    if (d[n] > 0x3f3f3f3f / 2) return -1;
    else return d[n];
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; i++) {
        int a, v, dis;
        scanf("%d%d%d", &a, &v, &dis);
        g[a].push_back({v, dis});
    }
    int t = Bellman(1);
    if (t == -1) cout << "impossible";
    else cout << t;

    return 0;
}

5.7 SPFA

5.7.1 SPFA求最短路径

st数组的作用是判断哪些点在队列中，一个点不需要重复加入队列，更新新值即可。虽然不用判断也可以，但是加上st数组可以加快速度。

平均时间复杂度是，最坏时间复杂度是。

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 <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int n, m, d[N];
vector<pii> g[N];
bool st[N];
queue<int> q;

int spfa(int s) {
    fill(d, d + N, INF);
    d[s] = 0;
    q.push(s);
    st[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        st[u] = false;
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i].first;
            int dis = g[u][i].second;
            if (d[v] > d[u] + dis) {
                d[v] = d[u] + dis;
                if (!st[v]) {
                    q.push(v);
                    st[v] = true;
                }
            }
        }
    }
    if (d[n] == INF) return -1;
    else return d[n];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, v, dis;
        scanf("%d%d%d", &a, &v, &dis);
        g[a].push_back({v, dis});
    }
    int t = spfa(1);
    if (t == -1) cout << "impossible" << endl;
    else cout << t << endl;

    return 0;
}

5.7.2 SPFA判断负环

几乎没有变化，但是注意初始时不再是将1加入队列，而是要将所有点加入队列，因为有时候负环存在但是从1开始到达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
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int n, m, d[N], cnt[N];
vector<pii> g[N];
bool st[N];
queue<int> q;

bool spfa() {
    fill(d, d + N, INF);
    for (int i = 1; i <= n; i++) {
        q.push(i);
        st[i] = true;
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        st[u] = false;
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i].first;
            int dis = g[u][i].second;
            if (d[v] > d[u] + dis) {
                cnt[v] = cnt[u] + 1;
                if (cnt[v] >= n) return true;
                d[v] = d[u] + dis;
                if (!st[v]) {
                    q.push(v);
                    st[v] = true;
                }
            }
        }
    }
    return false;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, v, dis;
        scanf("%d%d%d", &a, &v, &dis);
        g[a].push_back({v, dis});
    }
    if (spfa()) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

5.8 Floyd

求解全源最短路径，原理是简单动态规划，最外层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
#include <bits/stdc++.h>
using namespace std;

const int N = 210, INF = 0x3fffffff;
int d[N][N];
int n, m, q;

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() {
    scanf("%d%d%d", &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, dis;
        scanf("%d%d%d", &a, &b, &dis);
        d[a][b] = min(d[a][b], dis);
    }
    floyd();
    while (q--) {
        int a, b;
        scanf("%d%d", &a, &b);
        if (d[a][b] > INF / 2) cout << "impossible" << endl;
        else cout << d[a][b] << endl;
    }
    
    return 0;
}

5.9 最小生成树

5.9.1 Prim

Prim算法步骤和Dijkstra十分相似。

prim算法步骤如下：

  1. 遍历n次，每次遍历首先找到集合外距离最近的点t。
  2. 用t更新其他点到集合的距离。（这是和Dijkstra不同的地方，到集合的距离是指到集合中的点的最小距离）

这一段代码和Dijkstra算法唯一不同的地方就在于d[]表示的含义不同，这里是表示到集合的距离。

和Dijkstra一样，时间复杂度是，如果使用heap优化的话可以降低到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

const int N = 510, INF = 0x3f3f3f3f;
int n, m, d[N];
vector<PII> g[N];
bool vis[N];

int prim() {
    int res = 0;
    fill(d, d + N, INF);
    d[1] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1, minn = INF;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && d[j] < minn) {
                minn = d[j];
                u = j;
            }
        }
        vis[u] = true;
        if (u == -1) return INF;
        res += d[u];
        for (int j = 0; j < g[u].size(); j++) {
            int v = g[u][j].first;
            int dis = g[u][j].second;
            if (!vis[v] && d[v] > dis) {    //唯一不同的地方
                d[v] = dis;
            }
        }
    }
    return res;
}

int main() {
    cin >> n >> m;
    while (m--) {
        int a, b, dis;
        cin >> a >> b >> dis;
        g[a].push_back({b, dis});
        g[b].push_back({a, dis});
    }
    int t = prim();
    if (t == INF) cout << "impossible" << endl;
    else cout << t << endl;
    
    return 0;
}

5.9.2 Kruskal

kruskal算法采用边贪心的策略，初始时隐去图中所有边，这样图中每个顶点都自成一个联通块。之后执行下面的步骤：

  1. 对所有边按边权从小到大进行排序。
  2. 按边权从小到大测试所有边，如果当前测试边所连接的两个顶点不在同一个联通块中，则把这条测试边加入当前最小生成树中，否则舍弃。
  3. 重复执行2，直到最小生成树中的边数等于总顶点数减1或是所有边测试完。结束时如果最小生成树边数小于总顶点数减1，说明该图不连通。

排序保证最小，两个顶点非同一连通块才合并保证不会成图。合并过程需要用到并查集。

时间复杂度是。可见kruskal算法适用于稀疏图。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, M = 2 * N, INF = 0x3f3f3f3f;
int n, m;
int father[N];
struct edge {
    int a, b, dis;  
} e[M];

bool cmp(edge a, edge b) {
    return a.dis < b.dis;
}

int find(int a) {
    int x = a;
    while (a != father[a]) {
        a = father[a];
    }
    while (x != father[x]) {
        x = father[x];
        father[x] = a;
    }
    return a;
}

int kruskal() {
    sort(e, e + m, cmp);
    for (int i = 1; i <= n; i++) {
        father[i] = i;
    }
    int res = 0, num = 0;
    for (int i = 0; i < m; i++) {
        int fa = find(e[i].a), fb = find(e[i].b);
        if (fa != fb) {
            father[fa] = fb;
            res += e[i].dis;
            num++;
            if (num == n - 1) break;
        }
    }
    if (num < n - 1) return INF;
    else return res;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, dis;
        cin >> a >> b >> dis;
        e[i] = {a, b, dis};
    }
    int res = kruskal();
    if (res == INF) cout << "impossible" << endl;
    else cout << res << endl;
    
    return 0;
}

6 树与二叉树

6.1 二叉树的储存和操作

6.1.1 储存

通常采用二叉链表来储存二叉树，二叉链表有以下好处：

  1. 结构体中存放指针，占用空间小
  2. 删除方便，只需要将指针置空就行
  3. 可以实时控制新生成结点的个数
1
2
3
4
5
6
7
8
9
10
11
struct node {
    typename data;
    node* left;
    node* right;
};
node* newNode(int v) {
    node* node = new node;
    node->data = v;
    node->left = node->right = NULL;
    return node;
}

6.1.2 查找和修改

1
2
3
4
5
6
void search(node* root, int x, int newdata) {
    if (root == NULL) return;
    if (root->data == x) root->data = newdata;
    search(root->left, x, newdata);
    search(root->right, x, newdata); 
}

6.1.3 结点插入

1
2
3
4
5
6
7
8
9
10
// insert函数将在二叉树中插入一个数据域为x的新结点（参数root要加引用）
void insert(node* &root, int x) {
    if (root == NULL) {     // 空树，说明查找失败，也即插入位置
        root = newNode(x);  //根root也已修改，因为传了引用
        return;
    }
    if (root->data == x) return;    // 说明已经存在
    else if (x < root->data) insert(root->left, x);
    else insert(root->right, x);
}

6.1.4 建立

1
2
3
4
5
6
7
node* create(int data[], int n) {
    node* root = NULL;
    for (int i = 0; i < n; i++) {
        insert(root, data[i]);
    }
    return root;
}

6.2 二叉树遍历

6.2.1 先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 定义二叉树节点的结构体
struct Node {
    Node left;
    int data;
    Node right;
};
// 先序遍历函数
void PreOrder(Node a) {
    if(a) {
        printf(“%d”, a.data);
        PreOrder(a.left);
        PreOrder(a.right);
    }
}

中序和后序遍历只需要调换printf语句和递归的顺序即可

6.2.2 中序遍历（栈）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void InOrder(Node a) {
    Node b = a;
    stack<Node> s;
    while (b || !empty(s)) {
        while (b) {
            s.push(b);
            b = b.left;
        }
        if (!empty(s)) {
            b = s.top();
            printf(“%d”, b.data);
            s.pop();
            b = b.right;
        }
    }
}

前序实现：

将printf语句放在s.push(b)这一句之前即可，表示第一次遇见这个结点就打印

6.2.3 层序遍历（队）

1
2
3
4
5
6
7
8
9
10
11
void LayerOrder(Node a) {
    queue<Node> q;
    Node b = a;
    if (!b) return;  // 如果结点空了则返回
    q.push(b);
    if (!empty(q)) {
        printf(“%d”, b.data);
        if (b.left) q.push(b.left);
        if (b.right) q.push(b.right);
    }
}

6.2.4 重建二叉树

给出先序序列和中序序列，要求重建这棵二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
13
node* create(int preL, int preR, int inL, int inR) {
    if (preL > preR) return NULL;
    int k;
    node* root = new node;
    root->data = pre[preL];
    for (k = 0; k < inR; k++) {
        if (pre[preL] == in[k]) break;
    }
    int numLeft = k - inL;  // 注意是减中序的左结点
    root->left = create(preL + 1, pre + numLeft, inL, k - 1);
    root->right = create(pre + numLeft + 1, preR, k + 1, inR);
    return root;
}

6.3 树的遍历

6.3.1 树的静态写法

1
2
3
4
struct node {
    int data;
    vector<int> child;  // 动态数组防止子结点过多空间超限
} Node[maxn];

6.3.2 先根遍历

1
2
3
4
5
6
void PreOrder(int root) {
    printf(“%d”, &Node[root].data);
    for (int i = 0; i < Node[root].child.size(); i++) {
        PreOrder(Node[root].child[i]);
    }
}

后根遍历只需要将printf语句下放即可。

6.3.3 层序遍历（记录层号）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct node {
    int data;
    int layer;  // 记录层号
    vector<int> child;
} Node[maxn];
void LayerOrder(int root) {
    queue<node> q;
    Node[root].layer = 0;
    q.push(Node[root]);
    while (!q.empty()) {
        int front = q.front();
        q.pop();
        printf(“%d”, Node[front].data);
        for (int i = 0; i < Node[front].child.size(); i++) {
            int child = Node[front].child[i];
            child.layer = Node[front].layer + 1;
            q.push(child);
        }
    }
}

6.4 二叉查找树（BST）

  1. 要么二叉查找树是一棵空树。
  2. 要么二叉查找树由根结点、左子树、右子树组成，其中左子树和右子树都是二叉查找树，且左子树上所有结点的数据域均小于或等于根结点的数据域，右子树上所有的结点数据域均大于根结点的数据域（其中可以得到一个规律：二叉查找树的中序遍历必然是非递减序列）。

6.4.1 查找操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// search函数查找二叉查找树中数据域为x的结点
void search(node* root, int x) {
    if (root == NULL) {
        printf(“search failed”);
        return;
    }
    if (x == root->data) {
        printf(“%d”, root->data);
    } else if (x < root->data) {
        search(root->left, x);
    } else {
        search(root->right, x);
    }
}

6.4.2 插入操作

1
2
3
4
5
6
7
8
9
10
// insert函数将在二叉树中插入一个数据域为x的新结点（参数root要加引用）
void insert(node* &root, int x) {
    if (root == NULL) {     // 空树，说明查找失败，也即插入位置
        root = newNode(x);
        return;
    }
    if (root->data == x) return;    // 说明已经存在
    else if (x < root->data) insert(root->left, x);
    else insert(root->right, x);
}

6.4.3 二叉查找树的建立

1
2
3
4
5
6
7
node* create(int data[], int n) {
    node* root = NULL;
    for (int i = 0; i < n; i++) {
        insert(root, data[i]);
    }
    return root;
}

6.4.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
// 寻找以root为根结点的树中的最大权值结点
node* findMax(node* root) {
    while (root->right != NULL) {
        root = root->right;
    }
    return root;
}
// 寻找以root为根结点的树中的最小权值结点
node* findMin(node* root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}
// 删除以root为根结点的树中权值为x的结点
void delete(node* &root, int x) {
    if (root == NULL) return;
    if (root->data == x) {
        if (root->right == NULL && root->left == NULL) {
            root = NULL;    // 如果是叶子结点直接置空
        } else if (root->left != NULL) {
            node* pre = findMax(root->left);
            root->data = pre->data;
            delete(root->left, pre->data);
        } else if (root->right != NULL) {
            node* next = findMin(root->right);
            root->data = next->data;
            delete(root->right, next->data);
        }
    } else if (root->data > x) {
        delete(root->left, x);
    } else {
        delete(root->right, x);
    }
}

7 数学

7.1 素数

7.1.1 试除法判断素数

for循环中条件写i <= n / i而不是i * i <= n主要是为了防止溢出。对了，记住一定是<=而不是<，可以举一个反例比如说49。

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

7.1.2 试除法分解质因数

给出一个数x，求得该数的所有质因数的底数和指数。

如何分解一个数a的质因数呢？依然可以用试除法来解决。从第一个质数开始枚举，如果这个质数是因数的话，那么就不断用 a 除以这个素数，得到其指数。

可以证明，所有使if (x % i == 0)条件成立时的数一定是质数。用假设法，如果不是质数，那么一定可以表示为一个比它小的质数乘另一个数，那么比它小的质数也一定是因数，一定在这之前被枚举过，因此被枚举的因数一定是质数。

一个数x的所有因数中，最多只存在一个大于sqrt(x)的数，所以单独判断就好，这样可以大幅减少计算。时间复杂度为。

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

7.1.3 埃氏筛求素数个数

给出一个数n，求1—n之间素数个数。

筛法一般用来判断一大堆数是不是质数。例如说判断之间素数的个数，如果采用试除法，那么时间复杂度为，会超时。

我们可以选择一种方法，当一些条件成立时将明显非质数的数筛去，这样可以节省大量时间。其中埃氏筛法是比较好理解的一种筛法，它筛选素数的倍数。时间复杂度为。

代码中的st数组可以将其理解为是否被筛去，不要将其理解为是否是素数，否则会和直觉相反。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const int N = 1e6 + 10;
int primes[N], cnt;
bool st[N];

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

7.1.4 线性筛求素数个数

线性筛的筛法为将合数通过其最小质因子筛去，一个合数的最小质因子有且只有一个，因此是线性的。

在代码中if (i % primes[j] == 0) 成立时 primes[j] 一定是 i 的最小质因子。因为我们从小到大枚举所有已经得到的质数，并且当第一次判断成立时 break。

任何合数，一定会被其最小质因子筛去，证明如下：

  • i % pj == 0，说明 pj 是 i 的最小质因子，pj 也一定是 pj * i 的最小质因子。
  • i % pj != 0，pj 一定小于 i 的所有质因子，pj 也一定是 pj * i 的最小质因子

时间复杂度为。

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

void getPrimes(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的最小质因子
        }
    }
}

7.2 约数

如果
约数个数：
约数之和：

7.2.1 试除法求约数

按照从小到大的顺序输出一个数的所有约数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    while (n--) {
        int a;
        vector<int> v;
        cin >> a;
        for (int i = 1; i <= a / i; i++) {
            if (a % i == 0) {
                v.push_back(i);
                v.push_back(a / i);
                if (i == a / i) v.pop_back();
            }
        }
        sort(v.begin(), v.end());
        for (int i = 0; i < v.size(); i++) {
            cout << v[i] << " ";
        }
        cout << endl;
    }
    
    return 0;
}

7.2.2 约数的个数

给定n个正整数ai，请你输出这些数的乘积的约数的个数，答案对1e9+7取模。

用哈希表存储质因数的个数，res * (prime.second + 1)过程可能爆 int 所以要用 long long。

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 <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
typedef long long LL;
unordered_map<int, int> primes;

int main() {
    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        for (int i = 2; i <= x / i; i++) {
            if (x % i == 0) {
                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;
}

7.2.3 约数之和

给定n个正整数ai，请你输出这些数的乘积的约数之和，答案对1e9+7取模。

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

unordered_map<int, int> primes;
typedef long long LL;
const int mod = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    while (n--) {   //求质因数
        int c;
        cin >> c;
        for (int i = 2; i <= c / i; i++) {
            if (c % i == 0) {
                while (c % i == 0) {
                    c /= i;
                    primes[i]++;
                }
            }
        }
        if (c > 1) primes[c]++;
    }
    LL res = 1;
    for (auto prime : primes) { //套公式
        int p = prime.first, mi = prime.second;
        LL t = 1;
        while (mi--) {
            t = (t * p + 1) % mod;
        }
        res = res * t % mod;
    }
    cout << res << endl;
    
    return 0;
}

7.2.4 最大公约数 & 最小公倍数

我们将使用辗转相除法来求解两个数 a 和 b 的最大公约数。

首先给出一个定理：0 和一个整数 a 的最大公约数是 a（不是0）。

然后给出一个等式gcd(a, b) = gcd(b, a % b)，其中 gcd 表示两个数的最大公约数，下面证明这个等式：

将 a 写作 a = kb + r，其中 k 为 a 整除 b 得到的商，r 为余数。设 d 为 a 和 b 的任意一个约数。r = a - kb，因此毫无疑问 d 也是 r 的一个约数。也就是说，a 和 b 的任意一个约数，也是 b 和 a % b 的一个约数。同理可以得到 b 和 a % b 的任意一个约数，也是a 和 b 的一个约数。当集合 A 包括集合 B，集合 B 包括集合 A 时，可以得到两个集合相等，因此 a 和 b 的最大公约数，也一定是 b 和 a % b 的最大公约数。

观察等式可以发现如果 a < b 的话，等式会将 a 和 b 交换。

辗转相除法求最大公约数下降得非常快，是级别的下降速度。

最小公倍数为 a * b / d，可以从集合的角度来理解，a 和 b 的最小公倍数为二者相乘除以最大重叠的那一部分，即为最大公约数。实际中为了防溢出常写成 a / d * b。

1
2
3
4
int gcd(int a, int b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

7.2.5 筛法求欧拉函数

1 ∼ N中与N互质的数的个数被称为欧拉函数，记为ϕ(N)。若在算数基本定理中，，则：。此题给定一个数 n，求1 ～ n之间所有整数的欧拉函数之和。

欧拉函数的求解公式可以用容斥原理简单证明一下：

  • 从1 - N中去掉所有 p1，p2，… ，pk 的倍数

  • 加上所有 pi * pj 的倍数

  • 减去所有 pi * pj * pk 的倍数（减了3次，又加了3次，相当于不加不减，实际上它应该被减去1次）

  • 以此类推，最后得到的式子可以化简为上述公式形式

由欧拉函数的定义我们可以很轻松地推导出来，如果一个数 i 是质数的话，那么其欧拉函数为 i - 1（除了 i 之外都与其互质）。

同时，结合公式和 N 的形式，我们可以得到，如果i % pj == 0，其中 pj 为质数，用 phi 来表示其欧拉函数，则phi[i * pj] = phi[i] * pj。这是因为 pj 是 i 的一个质因子，相当于 N 中对应 pj 的次数加一，，这对于公式后面没有影响，只是将 N 扩大了 pj 倍而已。

相应的，如果i % pj != 0，则说明 N 的形式中多了一项 pj ，欧拉函数后面需要添加一项 ，与前面的N中约去一个 pj 之后，可以得到phi[i * pj] = phi[i] * (pj - 1);

为什么这道题目中要用线性筛法求欧拉函数之和呢？

我们之前说过，线性筛会保证一件事：如果一个数会被筛去那么一定会而且只会被其最小质因子筛去，我们利用这个性质保证其没有遗漏，并且可以将时间复杂度降低为。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
LL getEulur(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) {
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }
            phi[i * primes[j]] = phi[i] * (primes[j] - 1);
        }
    }
    LL res = 0;
    for (int i = 1; i <= n; i++) {
        res += phi[i];
    }
    return res;
}

7.3 快速幂

7.3.1 快速幂模板

快速幂用于求解指数位非常非常大的情况。对于一个数，如果 b 十分大，假设是 数量级，用暴力做法一个数一个数相乘，需要运算次，属于级别，对于一般设置时长为 1s 的算法题来说会超时。

我们可以将指数位 b 分解为二进制数，分别求解其每一位二进制数，然后相乘。例如说，（以上指数位的数皆为二进制）。这样，我们就可以在其二进制位数个次数内求得该数，将算法优化为级别。

计算出来的数十分的庞大，一般都会输出对于某个数的模，以下代码中 p 即为模数。

1
2
3
4
5
6
7
8
9
LL quickMi(int a, int b, int p) {
    LL res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        b >>= 1;
        a = (LL)a * a % p;
    }
    return res;
}

7.3.2 快速幂求逆元

首先解释一下什么是逆元。通俗的来说，如果两个整数的乘积模m后等于1，那么就称它们互为m的逆元。写作或者。

逆元有什么用处？对乘法来说有成立，但是对除法来说：

举个例子，12 / 4 对 2 取模，答案为 1 而不是 0。

因此，逆元的一大意义就在于将除法取模转化为乘法取模。

可能有一些人有疑问了，虽然上面的两个式子不成立，我为什么不先计算a / b的值然后取模呢？是的，大部分情况下先计算 a / b 都是没有问题的，但是考虑这种情况：计算数值巨大的组合数， 对 1e9 + 7 取模的值，这个数的分子和分母都十分庞大。在每一步的运算过程中都应该对 1e9 + 7 取模，否则甚至会爆long long。所以将除法取模转化为乘法取模十分有必要。

一个数 b 存在逆元的充要条件是 b 与模数 m 互质。特别的，如果 m 是素数，且 a 不是 m 的倍数，则 a 模 m 的逆元为。这个公式可以由费马小定理推导而来。

费马小定理的公式：。

7.4 拓展欧几里得

欧几里得算法是我们之前辗转相除求最大公约数的算法。而拓展欧几里得所要解决的一个问题是：给定两个非零整数 a 和 b ，求一组整数解 (x, y)，使得 ax + by = gcd(a, b) 成立。其中gcd为最大公约数。

理解拓展欧几里得的核心在于理解gcd(a, b) = gcd(b, a % b)这个公式。这个公式在之前欧几里得算法求最大公约数那一节介绍过了。

我们知道在欧几里得算法递归结束时能得到一个式子a * 1 + b * 0 = gcd(a, b)，这是否就可以理解为 x 和 y 在递归的过程中最后变化成了 1 和 0 呢？是的。我们希望能通过gcd(a, b) = gcd(b, a % b)这个公式，逆推出 x 和 y 初始的值。我们用 x1 和 y1 表示递归上层的 x 和 y 的值，用 x2 和 y2 表示下层的 x 和 y 的值，下面是推导过程：

当计算 gcd(a, b) 时，有 a * x1 + b * y1 = gcd 成立，在下一步计算 gcd(b, a % b) 中，有 b * x2 + (a % b) * y2 = gcd 成立。于是得到 a * x1 + b * y1 = b * x2 + (a % b) * y2。而 a % b = a - (a / b) * b，所以最后的式子可以写成 a * x1 + b * y1 = a * y2 + b * (x2 - (a / b) * y2)。对比左右两边很快可以得到下面的递推公式：

于是我们就得到了递推公式。细心的你通过上面的证明可能发现了，ax + by = gcd(a, b) 不知有一组解。是的，我们通过拓展欧几里得求出来的其中的一组解。

观察公式我们可以发现一个有趣的现象：如果在传递 x 和 y 时翻转，那么就不用多余的代码更新 x 的值了，这对于简化代码有一些帮助。同时因为我们希望保留低层递归对 x 和 y 的修改，所以需要传引用。

1
2
3
4
5
6
7
8
9
int exGcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int d = exGcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

如果不翻转x和y的话，那么拓展欧几里得的代码为：

1
2
3
4
5
6
7
8
9
10
11
int exGcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int d = exGcd(b, a % b, x, y);
    int temp = x;
    x = y;
    y = temp - a / b * y;
    return d;
}

7.5 组合数

一个组合数，我们会根据 a 和 b 的取值范围的不同来选取不同的方法计算，保证不超时。组合数很大， 所以一般来说都会要求组合数对一个数取模的值。在接下来的讲解中，这个取模的数都是素数。

7.5.1 组合数（递推公式）

。适用于 n 与 m 较小的情况（当 n 和 m 超过 10000 时就很危险了）。时间复杂度是。递推公式的好处是求出了一张表保存了所有要求的组合数，所以适用于多次查询的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;

const int N = 2e3 + 10;
const int 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() {
    int n, a, b;
    cin >> n;
    init();
    while (n--) {
        cin >> a >> b;
        cout << c[a][b] << endl;
    }
    
    return 0;
}

7.5.2 组合数（定义）

当时，递推公式明显会超时，我们可以采用定义法：

因为

所以需要求阶乘的乘法逆元（注意这里需要 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
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int fact[N], infact[N]; //表示阶乘和阶乘的逆元

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

void getFact() {
    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] * quickMi(i, mod - 2, mod) % mod;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    getFact();
    while (n--) {
        int a, b;
        scanf("%d%d", &a, &b);
        int res = (LL)fact[a] * infact[a-b] % mod * infact[b] % mod;
        printf("%d\n", res);
    }
    
    return 0;
}

7.5.3 组合数（Lucas）

我们来考虑的极端情况。如此庞大的数字

首先介绍我们的解决方案，Lucas定理：

如果 p 是素数，将 m 和 n 表示为 p 进制：

那么 Lucas 定理告诉我们：

举个例子来说，对于来说，m = 3， n = 8，将 m 和 n 表示成五进制形式：

于是有。

这意味着我们可以在组合数的表示中将 n 和 m 两个十分庞大的数分解为多个小组合数相乘，其中 a 和 b 都小于 p。当 时都在我们的求解范围内，唯一的要求就是 p 要为素数。

将 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
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
int p;

int quickMi(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = (LL)res * a % p;
        b >>= 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 * quickMi(i, p - 2) % p;
    }
    return res;
}

int Lucas(LL a, LL b) {
    if (a < p && b < p) return C(a, b);
    else 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;
}

8 动态规划

什么是动态规划

动态规划（Dynamic Programming）是一种用来解决一类最优化问题的算法思想。简单来说，动态规划将一个复杂的问题分解成若干个问题，通过综合子问题的最优解来得到原问题最优解的过程。十分灵活，无固定写法。有以下几个特性：

  1. 一个问题必须要有重叠子问题和最优子结构才能用动态规划求解
  2. 与分治的区别：分治不拥有重叠子问题
  3. 与贪心的区别：贪心“自顶向下”，只考虑子问题中最优的一个解。动态规划会考虑所有子问题，并选择继承能得到最优结果的那一个
  4. 设计状态转移方程是动态规划的核心，也是动态规划最难的地方。动态转移方程必须满足状态的无后效性

8.1 背包问题

8.1.1 0-1背包问题

有 n 件物品和一个容量是 m 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi ，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

以下是二维数组的解法，dp[i][j]表示选取 1 ～ i 件物品且背包容量最大为 j 时的最优解。在循环中会逐渐增加能选取的物品数量和背包容量。最终答案就是dp[n][m]。

为什么扩大背包容量一定能增加总价值？因为当 i 固定时，j 逐渐变大过程中只做加法而不做减法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int dp[N][N], v[N], w[N];

int main() {
    int n, m;
    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++) {
            dp[i][j] = dp[i-1][j];
            if (j >= v[i]) dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);
        }
    }
    cout << dp[n][m] << endl;
    
    return 0;
}

考虑到dp[i]只使用了dp[i-1]的结论，所以可以将二维数组优化成一维，最大的改动如下。需要将背包容量从后向前枚举，否则就不是使用dp[i-1]而是dp[i]的结论了。

1
2
3
4
5
for (int i = 1; i <= n; i++) {
    for (int j = m; j >= v[i]; j--) {
        dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
    }
}

8.1.2 完全背包问题

问题在0-1背包问题的基础上修改为每件物品可以无限次使用。

只需将

1
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);

修改为

1
dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i]);

为什么是dp[i]而不是dp[i-1]？因为dp[i][j] >= dp[i-1][j]一定成立，如今第 i 件物品可以无限选择，那么就一定选择更大的那个。也因为这个道理，所以一维优化不需要再从后向前枚举。

1
2
3
4
5
for (int i = 1; i <= n; i++) {
    for (int j = w[i]; j <= m; j++) {
        dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
    }
}

8.1.3 多重背包问题

问题在完全背包问题基础上修改，每件物品可以使用s[i]次而不是无限次。

既然可以使用的次数有限，那就逐个枚举，让 DP 算法自己判断选取多少个更合适。时间复杂度是。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

const int N = 110;
int dp[N][N], w[N], v[N], s[N];

int main() {
    int n, m;
    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++) {
                dp[i][j] = max(dp[i][j], dp[i-1][j - v[i] * k] +  w[i] * k);
            }
        }
    }
    cout << dp[n][m] << endl;
    
    return 0;
}

8.1.4 多重背包问题（二进制优化）

可以将时间复杂度优化为。适用于N，V或者S比较大的情况。

思路是将每个每个物品的个数拆成其二进制数和某个数的和（如果这个数存在的话），例如将200拆分成 200 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 73。于是这个物品就可以转化成多个物品，然后整个问题变成了 0-1 背包问题。

体积变成 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
#include <bits/stdc++.h>
using namespace std;

const int N = 13000;
int v[N], w[N];
int dp[N];

int main() {
    int n, m, cnt = 0;  // cnt表示转化后的总物品数
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;  // k为二进制倍数
        while (k <= s) {
            cnt++;
            v[cnt] = k * a;
            w[cnt] = k * b;
            s -= k;
            k *= 2;
        }
        if (s > 0) {
            cnt++;
            v[cnt] = s * a;
            w[cnt] = s * b;
        }
    }
    n = cnt;
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--) {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout << dp[m] << endl;
    
    return 0;
}

8.1.5 分组背包问题

有N组物品和容量为V的背包，每组物品有若干个，同一组物品最多选一个，求如何选取总价值最大。

多重背包问题是枚举第 i 个物品选多少个，分组背包问题是枚举第 i 组物品选哪一个。二者的代码有一定相似之处。

一维状态转移如何判断正向枚举还是逆向枚举？只需要观察本层状态的更新是否使用上一层的结论即可。如果使用上一层的结论，那么就需要逆向枚举；如果仅使用本层的结论，那么就正向枚举。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

const int N = 110;
int dp[N], s[N], v[N][N], w[N][N];

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

8.2 线性DP

8.2.1 数字三角形

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。 

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

注意只能朝着左下方和右下方的结点移动。

因为结点有可能有负值，所以最好将dp数组初始化为-INF，防止max函数取到三角形之外的数。另外顺序向下有可能需要比较三角形内的数和外的数，所以将其边缘也初始化为-INF。

dp[1][1]需要预先给定，否则整个dp数组都很难逃离-INF。时间复杂度。

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 <bits/stdc++.h>
using namespace std;

const int N = 510;
const int INF = 0x3fffffff;
int a[N][N], dp[N][N];  // dp表示考虑到第i行第j层为止的最大路径和

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= i + 1; j++) {
            dp[i][j] = -INF;
        }
    }
    dp[1][1] = a[1][1];
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i][j] = max(dp[i-1][j-1] + a[i][j], dp[i-1][j] + a[i][j]);
        }
    }
    int maxn = -INF;
    for (int i = 1; i <= n; i++) {
        if (dp[n][i] > maxn) maxn = dp[n][i];
    }
    cout << maxn << endl;
    
    return 0;
}

如果不想考虑边缘情况的话，可以逆序向上。既然一条路正着走路径和最短，那么反着走也一定路径和最短。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
#include <bits/stdc++.h>
using namespace std;

const int N = 510;
const int INF = 0x3fffffff;
int dp[N][N];  // dp表示考虑到第i行第j层为止的最大路径和

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            scanf("%d", &dp[i][j]);
        }
    }
    for (int i = n; i >= 1; i--) {
        for (int j = i; j >= 1; j--) {
            dp[i][j] = dp[i][j] + max(dp[i + 1][j], dp[i + 1][j + 1]);
        }
    }
    cout << dp[1][1] << endl;
    
    return 0;
}

8.2.2 最长上升子序列

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。 子序列中单调递增的部分可以不连续。

dp[i] 表示以第i个字符结尾的序列严格单调递增的最长长度。有一个边界，若前面没有比i小的，dp[i] 为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 <bits/stdc++.h>
using namespace std;

const int N = 1010;
int a[N], dp[N];    //dp[i]表示以第i个字符结尾的序列严格单调递增的最长长度

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    int maxn = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = 1;
        for (int j = 1; j <= i; j++) {
            if (a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1);
        }
        maxn = max(maxn, dp[i]);
    }
    cout << maxn << endl;
    
    return 0;
}

有一种二分的优化写法，可以将时间复杂度降低到，这种写法的思想更像是贪心。

  • 状态表示：**f[i] 表示长度为 i 的最长上升子序列，末尾最小的数字**。即长度为 i 的子序列末尾最小元素是什么。cnt 表示目前的最长上升序列长度。

  • 状态计算：对于每一个w[i]，如果大于 f[cnt - 1]那就cnt + 1，当前末尾最小元素为w[i]。 若 w[i] 小于等于f[cnt - 1]，说明不会更新当前的长度，但之前序列末尾的最小数字要发生变化，找到最小的大于或等于 (这里不能是大于) w[i]的位置 r，更新以 r 结尾序列的最小数字。

  • 为什么 cnt 能用来表示最长上升序列长度？这里用到了贪心的思想。举个例子：一个序列 3 1 2 1 8 5 6，长度为 1 时，能接在 3 后面的数字一定可以接在 1 后面，所以 1 比 3 更合适作为结尾的数字。cnt 在这种最优的条件下判断w[i] > f[cnt-1]的次数，所以可以得到最优解。

  • f[i]一定是一个单调递增的数组，所以可以用二分法来找最小的大于或等于 w[i] 的数字。

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 <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int a[N], f[N]; //f[i]表示长度为i的最长上升子序列中末尾最小的数字
int n, cnt;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) 
        cin >> a[i];
    f[cnt++] = a[0];
    for (int i = 1; i < n; i++) {
        if (a[i] > f[cnt - 1]) f[cnt++] = a[i];
        else {
            int l = 0, r = cnt - 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (f[mid] >= a[i]) r = mid;
                else l = mid + 1;
            }
            f[r] = a[i];
        }
    }
    cout << cnt << endl;
    
    return 0;
}

8.2.3 最长公共子序列

给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。

dp[i][j]表示长度为 i 的 A 字符串和长度为 j 的 B 字符串的最长公共子序列长度。考虑不同情况

  • 如果a[i] == b[j]，说明字符串 A 和字符串 B 的 LCS 都增加了一位。
  • 如果a[i] ！= b[j]，说明字符串 A 和字符串 B 的 LCS 无法继续延长，因此dp[i][j]将会继承dp[i-1][j]和dp[i][j-1]中的较大者。

时间复杂度为。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
char a[N], b[N];
int n, m, dp[N][N];  //dp[i][j]表示长度为i的A字符串和长度为j的B字符串的最长公共子序列长度

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

8.2.4 最短编辑距离

给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：

  1. 删除 – 将字符串 A 中的某个字符删除。
  2. 插入 – 在字符串 A 的某个位置插入某个字符。
  3. 替换 – 将字符串 A 中的某个字符替换为另一个字符。

现在请你求出，将 A 变为 B 至少需要进行多少次操作。

一般来说，动态规划，题目怎么问，就怎么表示状态。比如说这道题目中，dp[i][j] 可以表示字符串 A 中前 i 个字符要和 B 中前 j 个字符匹配需要进行的最少的操作次数。操作分三种情况：

  • 删除：即需要删除 A 字符串中第 i 个字符才能使得其与字符串 B 中前 j 个字符匹配，可以得到dp[i][j] = dp[i-1][j] + 1。表示字符串 A 前 i - 1 个字符与 B 前 j 个字符匹配的最小操作数加上删除这个操作。
  • 增加：同理，既然需要增加才能匹配，那么意为前 i 个字符和前 j - 1 个字符是匹配的。dp[i][j] = dp[i][j-1] + 1。
  • 替换：这里需要分情况讨论，如果A[i] = B[j]，那么不需要修改，直接继承dp[i-1][j-1]即可，否则需要进行替换操作，dp[i][j] = dp[i-1][j-1] + 1。

上述三种情况取最小值就可以得到我们想要的 dp 数组。

注意首先要进行边缘化操作：dp[0][i] = i表示 A 字符串前 0 个字符和 B 字符串前 i 个字符想要匹配需要增加 i 个字符，dp[i][0] = i同理。

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 <bits/stdc++.h>
using namespace std;

const int N = 1010;
int n, m;
char a[N], b[N];
int dp[N][N];

int main() {
    cin >> n >> a + 1 >> m >> b + 1;	//表示把第一位空出来，从第二位开始输入。
    for (int i = 0; i <= n; i++) 
        dp[i][0] = i;
    for (int i = 0; i <= m; i++)
        dp[0][i] = i;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1);
            if (a[i] == b[j])
                dp[i][j] = min(dp[i][j], dp[i-1][j-1]);
            else
                dp[i][j] = min(dp[i][j], dp[i-1][j-1] + 1);
        }
    }
    cout << dp[n][m] << endl;
    
    return 0;
}

8.3 区间DP

设有 N 堆石子排成一排，其编号为 1，2，3，…，N。每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

问题是：找出一种合理的方法，使总的代价最小，输出最小代价。

区间 DP 不同于线性 DP，其数组 dp[L][R]表示的含义为将区间 L - R 的石子合并为一堆的方案的集合的最小值。同一个区间有多种合并方案，例如说，我们可以通过最左端的值来区别不同合并方案（如下图所示）。假设我们正在进行这个区间的合并工作，分界点为 k 。现在区间为[L, k] 和 [k + 1, R]。我们所要做的是就是计算前一个区间的最小合并价值，后一个区间的最小合并价值和两个区间合并的价值（两个区间合并价值固定，可以通过前缀和来求出）。这样就得到了 DP 中我们喜闻乐见的重叠子问题。

区间 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
#include <bits/stdc++.h>
using namespace std;

const int N = 310;
const int INF = 0x3fffffff;
int n;
int a[N], s[N], dp[N][N];   //dp[L][R]表示的含义为将区间 L - R 的石子合并为一堆的方案的集合的最小值

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i-1] + a[i];
    }
    //区间长度为1时代价为0，不需要考虑
    for (int len = 2; len <= n; len++) {  //区间长度
        //表示区间长度变大，左端点初始一直为1，右端点始终不大于n
        for (int l = 1; l + len - 1 <= n; l++) {    
            int r = l + len - 1;
            dp[l][r] = INF;     //考虑边界点
            for (int k = l; k < r; k++) {
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + s[r] - s[l-1]);
            }
        }
    }
    cout << dp[1][n] << endl;
    
    return 0;
}
  • 本文标题：数据结构与算法
  • 本文作者：ZOU
  • 创建时间：2021-12-22 11:24:08
  • 本文链接：https://yipeng.xyz/2021/12/22/数据结构与算法/
  • 版权声明：可随意使用，但是转载请联系我！
 评论