算法基础笔记

发表于2023-06-15更新于2024-06-18字数统计26.4k阅读时长211分阅读次数

author：SmallBoat
所谓基础，指的是base，而非easy。—— yxc

第一章：基础算法

1. 1 快速排序O(nlog⁡n)\mathcal{O}(n \log n)：快速排序

算法思想：分治

  1. 确定分界点 x = q[l + r >> 1]
  2. 调整区间：让第一个区间里的数小于等于x， 让第二个区间的数大于等于x
  3. 递归处理左右两边

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void quick_sort(int[] q, int l, int r) {
    if(l >= r) return; // 如果左端点大于等于右端点，则直接返回，也为递归退出条件
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while(i < j) {
        do i ++; while(q[i] < x);
        do j --; while(q[j] > x);
        if(i < j) {
            int tmp = q[i];
            q[i] = q[j];
            q[j] = tmp;
        }
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

1.2 归并排序O(nlog⁡n)\mathcal{O}(n \log n)

1.2.1 归并排序：归并排序

算法思想：分治
  1. 确定分界点 mid = r + l >> 1
  2. 递归处理左右两边
  3. 归并，将两个区间合二为一（从递归后的最底层开始合并，每次回溯后达到排序的效果）(O(n)\mathcal{O}(n))
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static 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)
        // tmp为辅助数组，用于临时存储归并数据，也是归并排序空间复杂度主要来源
        if (q[i] <= q[j]) tmp[k ++] = q[i ++];
        else tmp[k ++] = q[j ++];

    while (i <= mid) tmp[k ++] = q[i ++];
    while (j <= r) tmp[k ++] = q[j ++];

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

1.2.2 归并求逆序对：逆序对的数量

代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static long merge_sort(int l, int r) {
    if(l >= r) return 0;
    int mid = l + r >> 1;
    int k = 0, i = l, j = mid + 1;
    long res = merge_sort(l, mid) + merge_sort(mid + 1, r);
    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(i = l, j = 0; i <= r; i ++, j ++) q[i] = tmp[j];
    return res;
}

1.3 整数二分O(log⁡n)\mathcal{O}(\log n)：数的范围

算法思想：

  1. 时时刻刻保证答案在所维护的区间内部。
  2. check()函数为满足条件部分，例如：1、2、3、3、4、5中，求3的起始位置，则所求位置在所有3范围的最左侧，于是需要保证每次mid需要在最左边一个3或其右侧，故check()函数为if (q[mid] >= 3)；若求3的最后位置，同理check()函数为if (q[mid] <= 3)。每次判断后需要调整区间端点，例如在求3的左端点时，如果满足q[mid] >= 3,则说明所求位置在mid左侧或就是mid，则将区间右端点更新为mid，即r = mid。
  3. 每次二分之前需将l、r初始化，注意： 更新时，若r被更新为mid - 1，则mid应初始化为mid = l + r + 1 >> 1，避免更新边界后范围不变，出现死循环。
  • 能使用二分的条件：必须要有二段性，即一定存在一个分界点，使得分界点一边(包括分界点)满足题目要求，另一边不满足。（参考二分算法详解）
  • 二分的题目有两种，一种是直接裸的二分题目，另一种则是枚举可能的答案，然后check这个答案是否可行（二分答案）。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 检查x是否满足某种性质，不一定是一个函数，也可能是例如 if (a[mid] >= 3) 的简单形式
public static boolean check(int x) {/* ... */} 

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
public static 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]时使用：
public static 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.4 浮点数二分O(log⁡n)\mathcal{O}(\log n)：数的三次方根

算法思想：

算法原理与整数二分相似，在区间划分的时候没有整数二分的各种边界情况，一般用左右端点的差值是否小于某个值ϵ\epsilon来判定是否需要继续循环。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
// 检查x是否满足某种性质
public static boolean check(double x) {/* ... */} 

public static double bsearch_3(double l, double r) {
    // eps 表示精度 epsilon，取决于题目对精度的要求，一般比题目保留小数位数大2
    final static double eps = 1e-8;
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

1.5 一维前缀和：前缀和

算法思想：

  • 在输入时，顺便记录前i项的和，i从1 ~ n，记为：s[i]，当需要求第i个数到第j 个数的和时，直接使用s[j] - s[i - 1]，时间复杂度为O(1)，比重新遍历更快。
  • 但是，如果数据会发生改变，则前缀和数组也会发生改变，而这种方式求解前缀和是O(n)\mathcal{O}(n)的。则此时需要使用树状数组或者线段树进行求解（详见第二章2.9）。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
s[i] = a[1] + a[2] + ... a[i]

// 输入数组时顺带求出前缀和
for (int i = 1; i <= n; i ++) {
    a[i] = sc.nextInt();
    // sum[0] 默认为 0
    sum[i] = sum[i - 1] + a[i];
}

// 只需要前缀和
for (int i = 1; i <= n; i ++) s[i] = s[i - 1] + sc.nextInt();

a[l] + ... + a[r] = s[r] - s[l - 1]

1.6 二维前缀和：二维前缀和

算法思想：

二维前缀和思想类似于一维前缀和，用s[i][j]表示以(i,j)为右下角，(0,0)为左上角的子矩阵中所有数之和。可用于求解以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为（可利用容斥原理推导）。

代码实现：

1
2
3
4
5
6
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];
// 求解以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和
int res = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];

1.7 一维差分：差分

算法思想：

  • 实际上，差分与前缀和互为逆运算，例如，如果数组s为数组a的前缀和数组，那么a则称为s的差分数组，即a[i] = s[i] - s[i - 1]。
  • 差分数组的作用在于，如果需要对一个数组中的l ~ r区间的k个数字均加上c，则时间复杂度与k相关，而对其差分数组进行操作，则只需在其差分数组的第l项加c，再对第r + 1项减去c，时间复杂度降为O(1)\mathcal{O}(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
// 插入操作，用于对差分数组的修改，a 数组初始化为 0
public static void insert(int l, int r, int c) {
    a[l] += c;
    a[r + 1] -= c;
}

// 读入需要操作的原数组
for (int i = 1; i <= n; i ++) s[i] = sc.nextInt(); 

/*
利用插入操作，直接求解s数组的差分数组a。
原理是在a[i]位置插入s[i]后，a[i + 1]会先减去s[i]，
等到i = i + 1时，a[i + 1]的位置会加上s[i + 1]，则最终a[i + 1]位置上的数
正好为s[i + 1] - s[i]，由定义可知，a正好构成s的差分数组
*/
for (int i = 1; i <= n; i ++) insert(i, i, s[i]); 

// 当然，也可以直接根据定义求差分数组：a[i] = s[i] - s[i - 1];

// 该操作可能会有很多组，直接对s数组操作时间复杂度较高，则对其差分数组操作，最后统一求一次前缀和即可得到新的s数组
int l = sc.nextInt(), r = sc.nextInt(), c = sc.nextInt();
insert(l, r, c);

// 求一遍前缀和
for (int i = i; i <= n; i ++) b[i] += b[i - 1];

1.8 二维差分：差分矩阵

算法思想：

  • 类似于一维差分，二维差分与二维前缀和互为逆运算，例如，数组s是数组b的前缀和数组，那么b就称为s差分数组。
  • 二维差分数组的作用在于，如果需要对二维矩阵中以(x1, y1)为左上角，(x2, y2)为右下角的区域内每个数加上c，那么可以对差分矩阵中b[x1][y1]加上c，对b[x2 + 1][y1]与b[x1][y2 + 1]减去c，再对b[x2 + 1][y2 + 1]减去c。因为对b[x1][y1]，将会导致求前缀和后，s[x1][y1]到右下角这部分区域每个数都加上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
// 插入操作，用于对差分数组b进行修改，同时可以用来构造差分数组b
public static void insert(int x1, int y1, int x2, int y2, int c) {
    b[x1][y1] += c; // 加c后右下角都将+c
    b[x2 + 1][y1] -= c; // 需要对b[x2 + 1][y1]右下角减去一个c使其保持不变
    b[x1][y2 + 1] -= c; // 需要对b[x1][y2 + 1]右下角减去一个c使其保持不变
    b[x2 + 1][y2 + 1] += c; // b[x2 + 1][y2 + 1]右下角被减了两次，需要加一次补回来
}

// 读入需要操作的二维数组
for (int i = 1; i <= n; i ++)
    for (int j = 1; j <= m; j ++)
        s[i][j] = sc.nextInt();

// 求差分数组 b
for (int i = 1; i <= n; i ++)
    for (int j = 1; j <= m; j ++)
        insert(i, j, i, j, s[i][j]);

// 对原数组 O(n) 的操作等价于对差分数组 O(1) 的操作
int x1 = sc.nextInt(), y1 = sc.nextInt(), x2 = sc.nextInt(), y2 = sc.nextInt(), c = sc.nextInt();
insert(x1, y1, x2, y2, c);

// 对 b 数组求一遍前缀和
for (int i = 1; i <= n; i ++)
    for (int j = 1; j <= m; j ++)
        b[i][j] += b[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1];

1.9 双指针： 最长连续不重复子序列

算法思想：

  • 双指针算法是优化枚举最常用的算法，其核心思想在于通过找到单调性，将O(n2)\mathcal{O}(n^2)的暴力枚举转变成O(n)\mathcal{O}(n)的双指针算法。
  • 该算法有两类，第一类为类似于归并排序中，在两个区间上归并的操作。第二类则在一个区间上动态维护一个小区间。

代码实现：

1
2
3
4
5
6
7
// 第一类同归并排序中两个指针同时扫描两个数组

// 第二类
for (int i = 0, j = 0; i < n; i ++) {
    while (j < i && check(i, j)) j ++; // j < i 也可以根据具体逻辑适当调整，check()为检验是否满足某一性质
    // 具体问题的逻辑
}

最长连续不重复子序列题解（第二类）：

题目描述：
给定一个长度为n的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式：
第一行包含整数n。
第二行包含n个整数，表示整数序列。
输出格式：
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围：
1≤n≤1051 \leq n\leq 10^5
输入样例：

1
2
5
1 2 2 3 5

输出样例：

1
3

双指针算法O(n)\mathcal{O}(n)：
定义两个指针i, j，数组a，i从第一个元素开始往后走，每经过一个元素，用s数组记录当前数字出现的次数，当走到某个元素a[i]时，若s[a[i]] > 1，则说明该数字前面出现过一次，此时让j指针向后走，j指针每经过一个元素，就让该元素出现次数就减一，当不满足s[a[i]] > 1时，说明j刚好经过与a[i]重复的那个数值，则此时j不再向后走，记录j ~ 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
24
25
26
27
28
import java.util.Scanner;

public class Main {

    static final int N = 100010;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int[] s = new int[N]; // 用于记录每位数出现的次数

        for (int i = 0; i < n; i ++)
            a[i] = sc.nextInt();

        int res = 0;
        for (int i = 0, j = 0; i < n; i ++) {
            s[a[i]] ++; // 每次 i 往后走，相应的数字出现的次数就自增
            while (j < i && s[a[i]] > 1) {
                s[a[j]] --; // 让 j 经过的数字出现的次数减一
                j ++; // j 往后走
            }
            // 这一步就算没有遇到重复元素也会计算最长不连续数目
            res = Math.max(res, i - j + 1); 
        }
        System.out.println(res);
    }
}

这道题还有滑动窗口解法，滑动窗口更好理解，许多双指针理解起来较为抽象的题目均可使用滑动窗口解决，详见第二章2.5滑动窗口模板。

1.10 位运算：二进制中1的个数

算法思想：

该部分不存在什么思想，更多的是语法，会用即可。
用法一： 求n的二进制表示中第k位（从右往左看，最右边为第0位）数字。原理： n >> k & 1。
用法二：lowbit操作，返回x的最后一位1，例如x = (1010)₂，则lowbit(x) = 10；若x = (101000)₂，则lowbit(x) = 1000，具体见代码实现。原理： 因为x & -x = x & (~x + 1)，而x & (~x + 1)能返回x的最后一位1，所以一般用x & -x求解x的最后一位1。（lowbit操作是树状数组的基础。）

代码实现：

1
2
3
4
5
6
7
8
9
10
11
// 用法一：求 n 的二进制表示中第 k 位数字
int res = n >> k & 1;

// 用法二：返回 x 的最后一位 1
public static int lowbit(int x) {
    return x & -x;
}

// 求解一个二进制数中含有多少个1的问题时，可以每次减去最后一位1（用lowbit实现），减了多少次就代表有多少个1（状态压缩常用）
// 或者使用 Integer 的静态方法 bitCount
int cnt = Integer.bitCount(x);

1.11 离散化：离散化

算法思想：

离散化的思想是将数值范围很大，但是数据量不大的一系列数映射到从0开始的有序递增的区间，从而降低算法的时间和空间复杂度。离散化不改变数据间的相对大小，压缩数据间无用的距离。例如，1, 3, 200, 48, 67349, 6546646这一系列数的范围为1 ~ 6546646，中间有许多无用的距离，我们将其压缩到0 ~ 5这几个位置（有时映射到从1开始更加方便），此时就产生了映射关系0 -> 1, 1 -> 3, 2 -> 48, 3 -> 200, 4 -> 67349, 5 -> 6546646。这与直接开一个数组将他们存进去再排序是有本质区别的，例如我们想对200这个值加上50，如果直接开数组，想要找到200这个值，需要遍历一遍，而如果是通过离散化映射，我们可以直接利用映射关系找到在什么位置，然后直接进行操作，该步骤时间复杂度直接降低到O(1)\mathcal{O}(1)。在映射之前，我们需要对数据进行排序，便于后面用整数二分找到每个数对应的映射值（下标）。同时需要对数据进行去重，因为即使有两个200，我们每次对200操作时，也是在同一个位置上进行操作的，因此重复的那个200不但没有存在的意义，反而影响在二分时寻找其映射值（下标）。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 将所有值排序，然后去重
Arrays.sort(alls); 

// 二分找到每个数离散化后的值（核心）
public static 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;
    }
    // 将离散化后的值映射到 1 ~ n，便于可能需要求前缀和的情况。
    return r + 1;
}

1.12 区间合并：区间合并

算法思想：

区间合并是将数轴上所有有交集的区间进行合并，得到没有交集的区间。例如将区间[0, 2], [3, 7], [4, 5], [7, 10], [13, 15]合并后的区间为[0, 2], [3, 10], [13, 15]。其思想类似于贪心，先将所有区间按照左端点进行排序，每次维护一个区间，如果枚举的区间与当前区间无交集，则将维护的区间放入答案中去，再将维护的区间更新为枚举的区间，否则将维护的区间的右端点更新为维护区间与枚举区间右端点的最大值。

代码实现：

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
class PII implements Comparable<PII> {
    int x, y;
    public PII(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public int compareTo(PII p) {
        return x - p.x;
    }
}

// 将所有区间合并
public static ArrayList<PII> merge(ArrayList<PII> segs) {
    ArrayList<PII> res = new ArrayList();
    Collections.sort(segs);
    int l = -2000000000, r = -2000000000;
    for (var seg : segs)
        if (seg.x > r) {
            if (l != -2000000000)
                res.add(new PII(l, r));
            l = seg.x;
            r = seg.y;
        }
        else r = Math.max(r, seg.y);

    if (l != -2000000000) res.add(new PII(l, r));
    return res;
}

新总结的模板（2024-03-12）：

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
// 求合并后的区间个数
import java.util.*;

public class Main {
    static class Segement implements Comparable<Segement> {
        int x, y;
        public Segement(int x, int y) {
            this.x = x;
            this.y = y;
        }
        @Override
        public int compareTo(Segement s) {
            if (x != s.x) return x - s.x;
            return s.y - y;
        }
    }
    static final int N = 100010;
    static Segement[] segments = new Segement[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i ++) 
            segments[i] = new Segement(sc.nextInt(), sc.nextInt());
        Arrays.sort(segments, 0, n);
        int lastEnd = segments[0].y, res = 1;
        for (int i = 1; i < n; i ++) {
            int x = segments[i].x, y = segments[i].y;
            if (y <= lastEnd) continue;
            if (x > lastEnd) res ++;
            lastEnd = y;
        }
        System.out.println(res);
    }
}

第二章：数据结构

2.1 ~ 2.3节在算法题中一般不会被直接用到，但是却是后面的邻接表（图论）和单调栈及单调队列的基础（当然啦，也可以被Java的集合代替 ，毕竟Java是最强语言）。

2.1 单链表：单链表

算法思想：

  • 该部分主要通过数组模拟单链表，进行插入结点、删除结点等操作。之所以需要用数组进行模拟，是因为在C ++或java中，new操作是非常慢的，在数据范围比较大的情况和容易TLE，并且，在很多时候，容器可以做的数组都可以做，而数组可以做的，容器不一定可以做。那么利用数组模拟就显得十分有优势。通过数组模拟单链表，需要定义head, e[], ne[], idx，其中head表示头结点，e[]表示每个点的值，ne[]表示每个点所指向的下一个点的下标，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
// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
static int head;
static int[] e = new int[N];
static int[] ne = new int[N];
static int idx;

// 初始化
public static void init() {
    head = -1;
    idx = 0;
}

// 在表头插入一个数x
public static void addHead(int x) {
    e[idx] = x;
    ne[idx] = head;
    // 此时 idx 未被使用过，现在使用 idx
    head = idx;
    // idx 移动到下一个位置备用
    idx ++;
}

// 在下标为k的结点后面插入一个数x
public static void add(int k, int x) {
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx ++;
}

// 删除下标为k的结点后面的一个结点
public static void remove(int k) {
    if (k == 0 && head != -1) head = ne[head]; // 特判是否为头结点，删除头结点时需要判断头结点是否存在
	else ne[k] = ne[ne[k]];
}

// 单链表的遍历
for (int i = head; i != -1; i = ne[i]) System.out.printf("%d ", e[i]);

2.2 双链表：双链表

算法思想：

与单链表相似，用数组模拟双链表。需定义数组e, l, r和变量idx，其中e表示每个结点的值，l表示结点的上一个结点下标，r表示结点的下一个结点下标，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
int e[N], l[N], r[N], idx;

// 初始化链表
public static void init() {
    // 0是左端点，1是右端点
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}

// 在节点k的右边插入一个数x
public static void insert(int k, int x) {
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx ++ ;
}

// 删除节点k
public static void remove(int k) {
    // 先后顺序无所谓
    l[r[k]] = l[k];
    r[l[k]] = r[k];
}

// 遍历双链表
for (int i = r[0]; i != 1; i = r[i]) System.out.printf("%d ", e[i]);

2.3 栈和队列：模拟栈模拟队列

算法思想：

用数组模拟栈和队列，操作相对简单，具体见代码实现。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
// 数组模拟栈
static int[] stk = new int[N];
static int tt = 0; // 栈顶指针
stk[ ++ t] = x; // 在栈顶插入x
tt --; // 栈顶元素出栈

// 数组模拟队列
static int[] queue = new int[N];
static int hh = 0, tt = -1;
queue[ ++ tt] = x; // 在队尾插入元素x
hh ++; // 弹出队头元素

2.4 单调栈：单调栈

算法思想：

单调栈用于维护一个递增或递减的序列，可以快速求出每个数左/右边离它最近的比它大/小的数。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
static final int N = 100010;
int[] stk = new int[N];

int n = sc.nextInt();
int tt = 0;
for (int i = 0; i < n; i ++) {
    int x = sc.nextInt();
    while(tt > 0 && check(stk[tt])) tt --; // check为具体题目的判断
    if (tt > 0) System.out.printf("%d ", stk[tt]);
    else System.out.printf("%d ", -1);
    stk[++ tt] = x; // 插入新元素
}

2.5 单调队列：滑动窗口

算法思想：

  • 单调队列与单调栈比较类似，用一个队列动态维护一组有序序列。每次先判断队头是否需要出栈，然后从队尾开始向前检查队尾元素与当前枚举元素的关系，如果满足check(a[i])，则让队尾元素弹出，直到队尾元素不满足条件。最后再将当前枚举元素加入队列。值得注意的是，队列q[]存储的是数组中元素的下标。
  • 该算法常用的场景为求解滑动窗口中的最大值或最小值、单调队列优化 dp。
  • Leetcode一题秒懂单调队列！（利用Deque实现单调队列）

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
int[] a = new int[N]; // 存储所有元素
int[] q = new int[N]; // 用于动态维护队列，存储的是元素下标

// n表示所有元素个数， k表示单调队列的大小
int n = sc.nextInt(), k = sc.nextInt();

// 这里的tt初始值是有说法的，如果队列开始没有元素，则tt = -1，否则tt = 0;
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[i] <= a[q[tt]]) tt --; // 判断队尾元素是否需要弹出，a[i] <= a[q[tt]]可根据题目具体条件更换
    q[++ tt] = i; // 将枚举的元素插入队尾
}

tt = 0 和 tt = -1的情况可参考烽火传递与E. Rudolf and k Bridges这两题。

子串类问题(滑动窗口算法框架)：

注意：单调队列并不一定对所有的滑动窗口题目好用，只是上面这道题使用单调队列能完美解决。当涉及到字串类问题时，优先选择滑动窗口框架。

看不懂模板可以先做做Leetcode 438. 找到字符串中所有字母异位词，再看这个模板框架。

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
/* 滑动窗口算法框架 */
public static void slidingWindow(String s, String p) {
    char[] cs = s.toCharArray(), cp = p.toCharArray();
    HashMap<Character, Integer> need = new HashMap<>();
    HashMap<Character, Integer> window = new HashMap<>();
    int L = p.length();
    for (int i = 0; i < L; i ++) {
        need.put(cp[i], need.getOrDefault(cp[i], 0) + 1);
    }
    // 有的题目只有一个字符串，甚至都不需要 need 和 valid
    int n = s.length(), m = need.size();
    int left = 0, right = 0;
    int valid = 0;
    while (right < n) {
        // c 是将移入窗口的字符
        char c = cs[right];
        // 右指针后移
        right ++;
        // 进行窗口内数据的一系列更新（主要是将元素抓进窗口）
        ...
        /**
        示例：
        if (need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (window.get(c).equals(need.get(c))) {
                // 如果窗口中的字符c已经够了，则需求数量的字母多了一个
                valid ++;
            }
        }
        */
        
        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // if (right - left == L) res.add(left); 根据具体题目修改
            // d 是将移出窗口的字符
            char d = cs[left];
            // 左指针后移
            left ++;
            // 进行窗口内数据的一系列更新（主要是将元素驱出窗口）
            ...
            /**
            示例：
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d))) {
                    valid --;
                }
                window.put(d, window.get(d) - 1);
            }
            */
        }
    }
}

2.6 KMP算法：KMP字符串

算法思想：

kmp算法是比较经典的字符串匹配算法，kmp是其三个发明人名字缩写。kmp算法是将模式串P与主串S进行匹配，其核心思想是将已经匹配过的字符利用起来，例如主串S为abaabac，模式串P为abac，当匹配到第四个字符发现不匹配时，主串中前三个字符已经匹配成功，我们可以将这个信息利用起来，那么下次匹配可以将P串的第一个字符直接与S串的第四个字符开始匹配，跳过了中间的一段，从而降低算法时间复杂度。而P串最少可以往前移动多少且可能匹配成功只取决于P串本身以P[i]结束的字串的前缀和后缀相等的最大值(next[i])，这便是KMP算法中比较抽象的next数组的含义。

掌握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
// s[]为主串，p[]为模式串，n为模式串的长度， m为主串的长度
// 求next数组
for (int i = 2, j = 0; i <= n; i ++) { // ne[1] = 0
    // 当不能匹配时，j跳转到ne[j]处
    while (j != 0 && p[i] != p[j + 1]) j = ne[j]; 
    // 若能够匹配，则让j向后走一位
    if (p[i] == p[j + 1]) j ++; 
    ne[i] = j;
}

// 匹配过程
for (int i = 1, j = 0; i <= m; i ++) {
    while (j != 0 && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++;
    // 当j走到p串末尾时，则说明一个匹配完成，即在s串中找到一个子串与p串完全相同
    if (j == n) { 
        // 匹配成功。之所以匹配成功还需要 j = ne[j]是因为一个主串里可能包含多个模式串(为下一段匹配做准备)
        j = ne[j]; 
        // 每道题的具体逻辑，这里是输出匹配成功的开始下标
        bw.write(i - n + " "); 
    }
}
bw.flush();

// tip：最小循环节长度：i - ne[i]

2.7 Trie树/字典树：字符串统计

算法思想：

Tree树是一种用于存储字符串的高效的数据结构，以一棵树的形式存储字符串中的每个字符，如果该字符已经存在，则不重新创建，否则创建该字符，并在树中每个字符串结尾的地方做标记，表示树中含有以该字符结尾的字符串。
Trie树.png

代码实现：

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
static int[][] son = new int[N][26]; // 表示每个字符的所有儿子结点
static int idx; // 表示当前son中用到了哪个下标
static int[] cnt = new int[N]; // 表示以cnt[p]这个字符结尾的字符串个数

// 插入字符串到Trie树中
public static void insert(char[] str) {
    // 从根节点开始找
    int p = 0;
    // 遍历要插入字符串的每个字符
    for (int i = 0; i < str.length; i ++) {
        // 将该字符转换为0 ~ 25的数字
        int u = str[i] - 'a';
        // 如果p结点不存在u这个儿子，则创建一个，son[p][u] == 0表示指向空节点，开始时也是根节点，没有子节点也指向空节点
        if(son[p][u] == 0) son[p][u] = ++ idx; 
        // 然后更新p的位置，p往后走一个（对于存在的往后走一个，对于不存在这个字母的，上一步创建了，也往后走一个位置）
        p = son[p][u];
    }
    // 添加成功后将以p位置结尾的这个字符串数量 +1
    cnt[p] ++;
}

// 查询字符串是否在Trie树中
public static int query(char[] str) {
    int p = 0;
    for (int i = 0; i < str.length; i ++) {
        int u = str[i] - 'a';
        // 如果发现某个字符在当前查询的路线中不存在，则说明该字符串不在树中，直接返回0个
        if (son[p][u] == 0) return 0;
        // 更新p的位置
        p = son[p][u];
    }
    // 返回以p位置处的字符结尾的字符串个数
    return cnt[p];
}

2.8 并查集：连通块中点的数量

算法思想：

  • 并查集的作用是在O(1)\mathcal{O}(1)的时间内将两个集合合并。其原理为：让一个集合的根节点直接指向另一个集合的根节点，成为另一个集合的一个子集。可以通过寻找一个节点的祖宗节点判断该元素属于哪个集合，其时间复杂度与树的高度相关，所以，需要对其进行优化。
  • 优化思想 ：将每个节点直接指向其祖宗节点，该操作是在寻找祖宗节点的回溯过程中完成的。
  • 查找两个点是否在同一个集合当中时，可以通过其祖宗节点是否是同一个节点进行判断。
  • 规定： 祖宗节点的父节点等于自己（递归的退出条件）

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// find函数，并查集的核心
public static int find(int x) {
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 初始化父亲数组，即每个节点开始都是一个集合
for (int i = 1; i <= n; i ++) p[i] = i; 

// 将a, b两个点合并进一个集合，此处很容易出错(将b的祖宗节点变为a的祖宗节点的父亲)
p[find(a)] = find(b); 

// 判断两个点是否在同一个集合
if (find(a) == find(b))

2.9 树状数组：动态求连续区间和

算法思想：

树状数组是一种能在O(log⁡n)\mathcal{O}(\log n)时间复杂度内修改某个数，并动态求出前缀和的数据结构。
能够在O(log⁡n)\mathcal{O}(\log n)内求出前缀和的原因：动态维护了一个数组（树状数组）。
为什么树状数组修改某个数需要O(log⁡n)\mathcal{O}(\log n)：我们是在维护的树状数组上进行修改的，因此需要修改该数并维护该树状数组。

注意，树状数组的下标必须从1开始，否则会死循环，因为lowbit(0)≡0lowbit(0) \equiv 0。

树状数组的三个核心方法：

  • lowbit：用于定位其关联的数组元素下标；
  • add：对元素增加一个值（修改操作需要转为增加操作来完成）；
  • query：查询以某个下标结尾的前缀和。

2.9 树状数组.png

代码实现：

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
import java.util.*;

public class Main {
    static final int N = 100010;
    static int[] a = new int[N], tr = new int[N];
    static int n, m;
    public static int lowbit(int x) {
        return x & -x;
    }
    public static void add(int x, int v) {
        for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
    }
    public static int query(int x) {
        int res = 0;
        for (int i = x; i > 0; i -= lowbit(i)) res += tr[i];
        return res;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 1; i <= n; i ++) a[i] = sc.nextInt();
        for (int i = 1; i <= n; i ++) add(i, a[i]);
        while (m -- > 0) {
            int k = sc.nextInt(), x = sc.nextInt(), y = sc.nextInt();
            if (k == 0) System.out.println(query(y) - query(x - 1));
            else add(x, y);
        }
    }
}

2.10 线段树：数列区间最大值，动态求连续区间和

算法思想：

线段树是一种能在O(log⁡n)\mathcal{O}(\log n)内求出一段区间内的某个属性（最大值、最小值、sum等）的数据结构。

一般来说，树状数组能干的，线段树都能干，因为线段树更加灵活。但是，由于线段树的常数太大，所以会比树状数组慢比较多。

线段树的四个核心方法：

  • pushup：用子节点的信息更新当前节点信息（有时不用显式地写出）；
  • build：在一段区间上初始化线段树；
  • modify：修改某个数的属性，同时维护线段树；
  • query：查询属性。

2.10线段树.png

代码实现：

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
import java.io.*;

public class Main {
    static class Segment {
        int l, r, max;
        public Segment(int l, int r, int max) {
            this.l = l;
            this.r = r;
            this.max = max;
        }
    }
    static final int N = 100010;
    static int[] w = new int[N];
    static Segment[] tr = new Segment[4 * N];
    
    public static void build(int u, int l, int r) {
        if (l == r) tr[u] = new Segment(l, r, w[r]);
        else {
            tr[u] = new Segment(l, r, 0);
            int mid = l + r >> 1;
            build(u << 1, l, mid);
            build(u << 1 | 1, mid + 1, r);
            // 其实就是 pushup，只是没有单独写一个pushup函数
            tr[u].max = Math.max(tr[u << 1].max, tr[u << 1 | 1].max);
        }
    }
    
    public static int query(int u, int l, int r) {
        if (tr[u].l >= l && tr[u].r <= r) return tr[u].max;
        int mid = tr[u].l + tr[u].r >> 1;
        int max = Integer.MIN_VALUE;
        if (l <= mid) max = query(u << 1, l, r);
        if (r > mid) max = Math.max(max, query(u << 1 | 1, l, r));
        return max;
    }
    
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s1 = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]), m = Integer.parseInt(s1[1]);
        String[] s2 = br.readLine().split(" ");
        for (int i = 1; i <= n; i ++) w[i] = Integer.parseInt(s2[i - 1]);
        build(1, 1, n);
        while (m -- > 0) {
            String[] s = br.readLine().split(" ");
            int x = Integer.parseInt(s[0]), y = Integer.parseInt(s[1]);
            bw.write(query(1, x, y) + "\n");
        }
        bw.flush();
    }
}
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
import java.util.*;

public class Main {
    static class Segment {
        int l, r, sum;
        public Segment(int l, int r, int sum) {
            this.l = l;
            this.r = r;
            this.sum = sum;
        }
    }
    static final int N = 100010;
    static Segment[] tr = new Segment[4 * N];
    static int[] w = new int[N];

    // 显示地将pushup写出
    public static void pushup(int u) {
        tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    }
    
    public static void build(int u, int l, int r) {
        if (l == r) tr[u] = new Segment(l, r, w[r]);
        else {
            tr[u] = new Segment(l, r, 0);
            int mid = l + r >> 1;
            build(u << 1, l, mid);
            build(u << 1 | 1, mid + 1, r);
            pushup(u);
        }
    }
    
    public static int query(int u, int l, int r) {
        if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
        int mid = tr[u].l + tr[u].r >> 1;
        int res = 0;
        if (l <= mid) res = query(u << 1, l, r);
        if (r >= mid + 1) res += query(u << 1 | 1, l, r);
        return res;
    }
    
    public static void modify(int u, int x, int v) {
        if (tr[u].l == tr[u].r) tr[u].sum += v;
        else {
            int mid = tr[u].l + tr[u].r >> 1;
            if (x <= mid) modify(u << 1, x, v);
            else modify(u << 1 | 1, x, v);
            pushup(u);
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        for (int i = 1; i <= n; i ++) w[i] = sc.nextInt();
        build(1, 1, n);
        while (m -- > 0) {
            int k = sc.nextInt(), x = sc.nextInt(), y = sc.nextInt();
            if (k == 0) System.out.println(query(1, x, y));
            else modify(1, x, y);
        }
    }
}

2.11 字符串哈希：字符串哈希

算法思想：

这里的字符串哈希是一种特殊的哈希方式，即字符串前缀哈希，其思想是将字符串转换为一个P进制的数，P的经验取值为131或13331。
例如，将SmallBoat转换为P进制的数（该字符串的哈希值）为：H[n]=H[9]=H[n−1]×P+str[n]=H[8]×P+str[9]H[n] = H[9] = H[n - 1] \times P + str[n] = H[8] \times P + str[9]

计算时会自动将字母转换为对应的ASCII编码值

那么，给定任意的l,r∈[0,n−1]l, r \in [0, n - 1]，l∼rl \sim r这段字符的哈希值为：H[l∼r]=H[r]−H[l−1]×Pr−l+1H[l \sim r] = H[r] - H[l - 1] \times P^{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
import java.io.*;

public class Main {
    static final int N = 100010, P = 131;
    static long[] h = new long[N], p = new long[N];
    static int n, m;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]); m = Integer.parseInt(s1[1]);
        char[] str = (" " + br.readLine()).toCharArray();
        
        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 -- > 0) {
            String[] s2 = br.readLine().split(" ");
            int l1 = Integer.parseInt(s2[0]), r1 = Integer.parseInt(s2[1]);
            int l2 = Integer.parseInt(s2[2]), r2 = Integer.parseInt(s2[3]);
            if (getHash(l1, r1) == getHash(l2, r2)) bw.write("Yes\n");
            else bw.write("No\n");
        }
        bw.flush();
    }
    public static long getHash(int l, int r) {
        // 注意公式正确性，并非 (h[r] - h[l]) * p[r - l + 1]
        return h[r] - h[l - 1] * p[r - l + 1];
    }
}

第三章：搜索与图论

3.1 树与图的存储：

  • 树是一种特殊的图，所以只需要会图的存储方式即可。在图中，无向图又是特殊的有向图，例如，对于一无向边a -- b，只需要存储两条有向边即可，即a -> b、b -> a，故只需要会有向图的存储即可。
  • 图的存储常用的有两种，分别为邻接矩阵和邻接表存储法。一般用邻接矩阵存储稠密图，即使用二维数组g[][]存储，g[a][b]表示一条由a指向b权值为g[a][b]的边。使用邻接表存储稀疏图，h[]存储每一条单链表的头结点，e[]存储每个顶点的值，ne[]存储每个顶点的邻点的下标，有时还会用w[]存储边的权重。

3.2 树与图的遍历：

3.2.1 DFS：

注意：
  • 在dfs过程中，必要时需要恢复现场，同时对于有的问题需要进行剪枝，如n皇后问题。
代码实现：
1
2
3
4
5
6
7
8
public static void dfs(int u) {
    if (check()) return; // dfs退出条件
	st[u] = true;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

DFS技巧：
  • 优化搜索顺序：应当优先搜索分支较少的节点，或者以使得整体搜索次数更少的顺序搜索；
  • 排除等效冗余：例如先选一再选二和先选二再选一是同一种，在搜索的时候要避免重复搜索；
  • 可行性剪枝：搜索过程中发现该分支再往下已经不是想要的结果，直接return；
  • 最优化剪枝：例如查找某最小值时，当前分支已经大于当前的最优解时，直接return；
  • 记忆化搜索（DP）：加缓存，每次要搜寻某个方案时，先看缓存中是否已存在，存在直接返回，不存在再搜索。

3.2.2 BFS：

注意：
  • 在BFS过程中没有递归，初学时要分清BFS和DFS的区别，BFS是维护一个队列。
代码实现（基于双端队列）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
public static void bfs() {
    Deque<int[]> q = new ArrayDeque<>();
    q.addLast(new int[]{0, 0});
    st[0][0] = true;
    
    while (!q.isEmpty()) {
        int[] t = q.pollFirst();
        int x = t[0], y = t[1];
        for (int i = 0; i < 4; i ++) {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m || st[a][b])
                continue;
            // 具体题目可能的逻辑
            ...
            st[a][b] = true;
            q.addLast(new int[] {a, b});
        }
    }
}

3.3 拓扑排序：有向图的拓扑排序

算法思想：

拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

  • 每个顶点出现且只出现一次；
  • 若存在一条从顶点A 到顶点 B 的路径，那么在序列中顶点A 必须出现在顶点 B的前面。

拓扑排序利用队列，先将所有入度为0的点放进队列中（用d数组记录每个点的入度），然后从队头元素开始遍历，并让队头元素出队，对每个点的所有邻边遍历一遍，每次遍历让其入度减一，当某个点入度为0时，将其放进队列中。当队列为空时，排序结束。

代码实现：

数组模拟队列可以不用单独存储答案，出队操作时逻辑出队，因此可以直接输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static boolean topSort() {
    int hh = 0, tt = -1; // 数组模拟队列
    for (int i = 1; i <= n; i ++) // 先将所有入度为0的点放进队列中
        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; // 返回是否成功进行拓扑排序，当tt == n - 1时，表示已经遍历完所有点
}

代码实现（基于双端队列）：

基于双端队列的实现则需要单独存一下序列，以便输出。下面代码中不用st也可以，因为d[j]每次都会被 -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
static List<Integer> res = new ArrayList<>();
// 建图省略
public static boolean top_sort() {
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 1; i <= n; i ++) {
        if (d[i] == 0) {
            q.addLast(i);
            st[i] = true;
        }
    }
    while (!q.isEmpty()) {
        int t = q.pollFirst();
        res.add(t);
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (st[j]) continue;
            d[j] --;
            if (d[j] == 0) {
                st[j] = true;
                q.addLast(j);
            }
        }
    }
    return res.size() == n;
}

3.4 朴素Dijkstra算法O(n2+m)\mathcal{O}(n^2 + m)：Dijkstra求最短路Ⅰ

算法思想：

  • 迪杰斯特拉算法只能用于求解非负权图的单源路径问题。
  • 迪杰斯特拉算法基于贪心，将第一个点到第一个点的距离赋值为0，其他赋值为无穷大INF，然后进行n - 1次迭代，每次从还未确定与起点最短距离的点中选出与起点距离最小的点，然后用这个点更新其他点到起点的距离，并将这个点的状态改为已确定最短距离（即st[t] = true）。
  • 使用邻接矩阵存储。

一般都不用朴素版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
public static int dijkstra() {
    // INF = 0x3f3f3f3f表示无穷大
    Arrays.fill(dist, INF);
    // 初始化起点到起点的距离为0
    dist[1] = 0; 
    // 进行n - 1次迭代，每次确定一个最小距离点
    for (int i = 0; i < n - 1; i ++) {
        // t只作为一个临时变量，用于筛选当前还未确定的距离最小的点
        int t = -1;
        for (int j = 1; j <= n; j ++) {
            // 寻找当前还未确定最小距离的点中的最小值（t == -1 表示最开始的状态，刚开始循环。）
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        }
        // 如果当前确定这个点是n号点(求的就是1~n的距离)，则直接退出循环（剪枝）
        if (t == n) break;
        // 将t（此次确定的最小距离点）放入集合中
        st[t] = true;
        // 用此次确定的最小距离点更新其他点到起点的距离
        for (int j = 1; j <= n; j ++)
            dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
    }
    if (dist[n] == INF) return -1;
    return dist[n];
}

3.5 堆优化版Dijkstra算法O(mlog⁡n)\mathcal{O}(m \log n)：Dijkstra求最短路Ⅱ

算法思想：

  • 算法思想同朴素版，朴素版中，每次寻找当前距离最小的点时，该操作是O(n)\mathcal{O}(n)级别，但是如果用堆进行维护，则该步骤时间复杂度降低为O(1)\mathcal{O}(1)，降低了瓶颈处复杂度，不过当用堆维护后，在后面需要用该点更新其他点到起点的距离时，需要对堆进行操作，所以最终时间复杂度为O(mlog⁡n)\mathcal{O}(m \log 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
54
static class PII implements Comparable<PII> {
    // x表示该点到起点的距离，y表示节点编号
    int x, y;
    public int compareTo(PII p) {
        return this.x - p.x;
    }
}

static int n, m, idx;
static final int N = 150010;
static final int INF = 0x3f3f3f3f;
static int[] h = new int[N], e = new int[N], ne = new int[N], dist = new int[N], w = new int[N]; // w表示权值
static boolean[] st = new boolean[N];
static PriorityQueue<PII> heap = new PriorityQueue<>();
// 或者也可以 PriorityQueue<int[]> heap = new PriorityQueue<>((o1,o2)->o1[1]-o2[1]); <int[]>这块是一个泛型的参数声明，在集合中只能存取指定类型的元素，这里限定堆中每个元素都是一个一维数组，后面传入了一个重写compare()方法的Lambda表达式，表示每个数组元素按下标为1处的元素distance进行升序排序，堆顶元素就是还未确定最终距离的点到源点距离最近的点。
// 大根堆写法：PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2)->o2.compareTo(o1));

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

public static int dijkstra() {
    // 初始化距离为无穷大
    Arrays.fill(dist, INF); 
    // 将起点到起点的距离定义为0
    dist[1] = 0; 
    // 将起点放进堆中(小根堆)
    heap.add(new PII(0, 1));
    // st[1] = true; 这里不需要提前将1的状态改为确定，因为要先用其更新其他点的距离之后再确定
    while(!heap.isEmpty()) {
        // 取出堆顶元素
        PII t = heap.remove(); 
        // vertex为顶点编号,diatance为当前点到起点的距离
        int vertex = t.y, distance = t.x; 
        // 如果当前点已经确定过最小距离，则跳过该点（因为有的点可能不止进堆一次）
        if (st[vertex]) continue;
        // 将该点标记为已经确定最小距离
        st[vertex] = true;
        // 用该点更新其他点到起点距离
        for (int i = h[vertex]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > distance + w[i]) {
                dist[j] = distance + w[i];
                // 更新后再次进堆，原来堆中的该点将会在 if (st[vertex]) continue; 这里被跳过
                heap.add(new PII(dist[j], j));
            }
        }
    }
    if (dist[n] == INF) return -1; // 如果n号点到起点的距离不存在，返回-1即可（注意，dijkstra不存在负权值，无需考虑距离为-1的情况，bellmanFord和spfa需要考虑）
    return dist[n];
}

3.6 Bellman-Ford算法O(nm)\mathcal{O}(nm)：有边数限制的最短路

算法思想：

  • Bellman-Ford算法以边为单位，进行n次迭代，每次迭代更新一遍每个点到起点的距离。Bellman-Ford算法对边的存储没什么要求，直接用一个类存储即可。
  • 当题目规定求只能经过k条边的最短路径时，只能用Bellman-Ford算法，此时算法复杂度为O(mk)\mathcal{O}(mk)。
  • 值得一提的是每次更新时应该用上一次迭代后的dist数组进行更新。如果用当前的dist，则在更新过几条边后，dist数组已经改变，此时再用当前的dist去更新会导致本来不能更新的点也被更新掉了。例如下图中，如果要求k = 1时，第一次迭代，会扫面一遍所有的边，当更新完编号为2这个点的距离后，dist数组已经发生变化，当扫描到2->3这条边时，dist[3]就会被更新为2，而题目要求只经过1条边，因此答案应该为3，显然不对。而我们每扫描一条边，利用上一次迭代的结果，就不会因为当前一次迭代过程中dist数组的改变而出现错误，这就是代码实现中backup数组的作用。

backup数组的意义.PNG

代码实现：

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
// 定义边类，a表示起点，b表示终点，w表示权值
static class Edge {
    public int a, b, w;
    public Edge(int a, int b, int w) {
        this.a = a;
        this.b = b;
        this.w = w;
    }
}

public static int bellmanFord() {
    // 初始化距离为无穷大
    Arrays.fill(dist, INF); 
    // 起点距离为 0
    dist[1] = 0;
    // 进行k次迭代（k为题目要求的只能经过k条边）
    for (int i = 0; i < k; i ++) { 
        // 拷贝上一次迭代后的dist数组
        int[] backup = Arrays.copyOf(dist, dist.length); 
        // 扫描每一条边
        for (int j = 0; j < m; j ++) { 
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            dist[b] = Math.min(dist[b], backup[a] + w); // 更新距离
        }
    }
    if (dist[n] > INF / 2) flag = true; // 这种写法是为了避免下图中起点根本到达不了n这个点，而n-1这个点将dist[n]的无穷大更新为INF - 1，如下图所示
    return dist[n];
}

无穷大被更新.PNG

3.7 SPFA算法O(m)∼O(nm)\mathcal{O}(m) \sim \mathcal{O}(nm)：SPFA求最短路

算法思想：

  • SPFA算法是对Bellman-Ford算法的宽搜优化，但是失去了k的限制（有些题目就是要在k次内），Bellman-Ford每次都用当前点去更新其他点到起点的距离，如果当前点的距离没有变小的话，那么这个操作就是在浪费时间，所以SPFA算法在此处进行了优化，利用一个队列，每当遍历到的点距离变小时，将其放入队列中，之后会用它去更新其他点的距离。
  • 并且，SPFA算法一般情况下很快，很多Dijkstra的题都可以用SPFA过掉，除非出题人故意编造数据，将SPFA算法时间复杂度卡成O(nm)\mathcal{O}(nm)。SPFA算法时间复杂度一般为O(m)\mathcal{O}(m)，最坏O(nm)\mathcal{O}(nm)。
  • 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
public static boolean spfa() {
    Arrays.fill(dist, INF);
    Deque<Integer> q = new ArrayDeque<>();
    // st数组表示当前的点是否在队列当中，防止存储重复的点(不校验基本都会TLE，因为spfa中有的点可能会重读入队)
    q.addLast(1); dist[1] = 0; st[1] = true;
    
    while (!q.isEmpty()) {
        int t = q.pollFirst();
        // 维护st
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            // d = dist[t] + dist{t -> j}
            int d = dist[t] + w[i];
            // 能被更新才更新
            if (dist[j] > d) {
                dist[j] = d;
                // 未在队列中才入队
                if (!st[j]) {
                    q.addLast(j);
                    st[j] = true;
                }
            }
        }
    }
    return dist[n] != INF;
}

3.8 SPFA判负环：SPFA判负环

算法思想：

该算法基于SPFA算法，在该过程中增加一个cnt数组，表示从起点到该点经过了多少个点，如果某条最短路径上除了自己有n个点（假设总共有n个点），那么加上自己之后一共有n + 1个点，由抽屉原理一定有两个点相同，所以存在环。并且在该背景下，这个环一定是负环，否则不会一直更新距离从而导致死循环。（当然，因为有cnt限制，一旦cnt[j] >= n，则直接return ture，所以代码中不会存在死循环）。

代码实现：

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
// 队列里存储节点编号（早期代码，用LinkedList写的，实际并非队列，集合而已）
static List<Integer> q = new LinkedList();
public static boolean spfa() {
    // 之所以将所有点放进队列，是因为可能1号点根本到不了负环
    for (int i = 1; i <= n; i ++) {
        q.add(i);
        st[i] = true;
    }
    while (!q.isEmpty()) {
        int t = q.remove();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            // 一开始所有dist都等于0（不用初始化为INF），如果满足dist[j] > dist[t] + w[i]说明有负权值
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                // 每更新一次，将cnt[j]也更新
                cnt[j] = cnt[t] + 1;
                if (!st[j]) {
                    // 如果当前点不在队列中，就将其放进队列
                    q.add(j);
                    st[j] = true;
                }
                // 如果发现某个点的cnt大于等于n，说明已经在里面转了n次了，因为如果这个环的权值之和大于等于0的话，是不会在里面一直转的，所以直接return，避免死循环
                if(cnt[j] >= n) return true;
            }
        }
    }
    return false; // 如果一切顺利，则说明没有负环
}

3.9 Floyd算法：Floyd求最短路

算法思想：

Floyd算法基于动态规划，使用三重循环，可以求解多源汇问题。
由于Floyd算法是最短路算法的最后一个算法，所以在此进行总结：

  • 朴素Dijkstra（单元最短路）常用于求解非负权图中的稠密图，时间复杂度O(n2+m)\mathcal{O}(n^2 + m)；
  • 堆优化版Dijkstra（单元最短路）常用于求解非负权图中的稀疏图，时间复杂度O(mlog⁡n)\mathcal{O}(m \log n)；
  • Bellman-Ford算法常用于求解有边数限制的最短路问题，时间复杂度O(nm)\mathcal{O}(nm)；
  • spfa算法常用于求解存在负权边的最短路问题（也可以求正权边最短路，有被卡风险），时间复杂度O(m)\mathcal{O}(m)；
  • Floyd算法常用于求解多源汇最短路问题，时间复杂度O(n3)\mathcal{O}(n^3)，Floyd算法的代码实现较简单，理解不了先直接背过即可，后面学了dp后就好理解了。

代码实现：

1
2
3
4
5
6
7
public static void floyd() {
    for (int k = 1; k <= n; k ++)
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n; j ++)
                // d为图的邻接矩阵，Floyd算法完成后d变成每个点到其他点的最短距离矩阵
                d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
}

3.10 朴素Prim算法：prim算法求最小生成树

算法思想：

  • Prim算法是求最小生成树的一种算法，原理是从一个点出发，每次找到离集合最近的点，并将其加入到集合中，然后用这个点来更新剩下的点到集合的距离。常常用于求解稠密图的最小生成树问题。
  • 集合中维护的元素就是生成树中的节点，每个点到集合的距离定义为该点到集合中任意一点距离的最小值。
  • 用邻接矩阵存储图。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int prim() {
    Arrays.fill(dist, INF);
    // res表示生成树中每条边的权值之和
    int res = 0;
    // 迭代n次，每次确定一个节点
    for (int i = 0; i < n; i ++) {
        // t为临时变量，用于寻找到集合的最短节点
        int t = -1;
        // 寻找到集合距离最短的节点
        for (int j = 1; j <= n; j ++)
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        // 如果不是第一个点，并且到集合距离最短的点的距离为无穷大，则说明最小生成树不存在
        if (i != 0 && dist[t] == INF) return INF;
        // 将该条边的权值加到res中
        if (i != 0) res += dist[t];
        // st表示是否加入到集合中
        st[t] = true;
        // 用该点更新其他点到集合的距离，注意不是 dist[t] + g[t][j]
        for (int j = 1; j <= n; j ++) dist[j] = Math.min(dist[j], g[t][j]);
    }
    return res;
}

3.11 Kruskal算法：Kruskal算法求最小生成树

算法思想：

  • Kruskal是以边为对象，首先将所有边按照权值进行排序，然后枚举每一条边，如果一条边对应的两个顶点不在同一个集合中，那么我们就将其加入到一个集合中，在枚举过程中记录一个cnt变量，每次有点加入集合中，则cnt ++，如果枚举完成之后，cnt < 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.*;

public class Main {
    static class Edge {
        int a, b, w;
        public Edge(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
        }
    }
    static final int N = 100010, INF = 0x3f3f3f3f;
    static Edge[] edges = new Edge[2 * N];
    static int[] p = new int[N];
    static int n, m;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); m = sc.nextInt();
        for (int i = 0; i < m; i ++) {
            int a = sc.nextInt(), b = sc.nextInt(), w = sc.nextInt();
            edges[i] = new Edge(a, b, w);
        }
        Arrays.sort(edges, 0, m, (o1, o2) -> o1.w - o2.w);
        int res = kruskal();
        System.out.println(res == INF ? "impossible" : res);
    }
    public static int kruskal() {
        int res = 0, cnt = 0;
        for (int i = 0; i <= n; i ++) p[i] = i;
        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;
                cnt ++;
                res += w;
            }
            if (cnt == n - 1) return res;
        }
        return INF;
    }
    public static int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
}

3.12 染色法判别二分图：染色法判别二分图

算法思想：

  • 二分图： 当且仅当图中不存在奇数环，可以利用抽屉原理进行证明；
  • 染色法顾名思义，就是将每个点染色，染色过程中需要保证每个点与它相邻的点的颜色不同，一共两种颜色。如果在染色过程中出现矛盾，那么该图就一定不是二分图。

代码实现：

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
// u表示当前节点编号，c表示当前颜色
public static boolean dfs(int u, int c) { 
    // color表示颜色，0表示未染色，1和2表示两种不同颜色
    color[u] = c; 
    for (int i = h[u]; i != -1; i = ne[i]) { 
        int j = e[i];
        // 如果这个邻点未被染色，则将其染为与u不同的另一种颜色，如果染色不成功，则说明发生矛盾，直接退出
        if (color[j] == 0 && !dfs(j, 3 - c)) return false;
        // 如果当前节点的一个邻点与当前节点颜色相同，则发生矛盾，直接退出
        else if (color[j] == c) return false; 
    }
    return true;
}

// 开始时 flag 为 true，表示不存在染色失败的情况
boolean flag = true; 
// 枚举每一个点
for (int i = 1; i <= n; i ++) 
    // 对还没有染色的节点染色
    if (color[i] == 0 && !dfs(i, 1)) {
        // 染色失败，则说明不是二分图
        flag = false; 
        break;
    }
// 循环结束之后 flag 还是 true 则说明染色成功，为二分图

3.13 匈牙利算法：二分图的最大匹配

算法思想：

  • 匈牙利算法由两位匈牙利的数学家提出，因此得名。用一个形象的例子解释，一个二分图中，所有顶点分为左右两个部分，左半部分的点与右半部分的点之间存在许多边，如果其中一条边与其他任意的边都不依附于同一个顶点，则称这条边为一个匹配。例如图1的二分图中，图4就是该二分图的最大匹配，最大匹配数为4。
  • 在整个匹配过程中，最开始1号与5号匹配，2号和7号匹配，此时没有任何问题，当3号点匹配时，发现7号点已经被匹配过了，此时，我们看看与7号匹配的2号点能否换个点匹配，而2号点的另一个可匹配点5号点被1号点匹配，我们再看1号点能不能换个点匹配，此时发现1号点还可以和6号点匹配，于是，1、2、3号点都可以匹配，如图3所示。

二分图的最大匹配.PNG

代码实现：

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
public static boolean find(int x) {
    for (int i = h[x]; i != -1; i = ne[i]) {
        int j = e[i];
        // 如果j还没被考虑过
        if (!st[j]) {
            // 将j的状态设置为已考虑过
            st[j] = true;
            // 如果j还没有与其他点匹配，或者可以为与j匹配的点找到其他点进行匹配
            if (match[j] == 0 || find(match[j])) {
                // 那么就将j 这个点与x进行匹配(match[j]表示与j这个点匹配的点的节点编号)
                match[j] = x;
                // 匹配成功返回true
                return true;
            }
        }
    }
    // 如果实在匹配不了，就返回false
    return false;
}

int res = 0;
// 左半部分点的编号为1~n1，依次枚举每个点，看能否找到匹配
for (int i = 1; i <= n1; i ++) {
    // st表示当前点是否被考虑过，并非匹配成功与否
    Arrays.fill(st, false);
    // 如果找到匹配，最大匹配数加一
    if (find(i)) res ++;
}

第四章：数学知识

4.1 试除法判定质数：试除法判定质数

算法思想：

判定一个数n是否是质数，主要判定2∼n2 \sim \sqrt{n}之间是否有其约数。（所有小于2的数不是质数）

代码实现：

1
2
3
4
5
6
7
public static boolean isPrime(int x) {
    if (x < 2) return false;
    // 由于sqrt()比较慢，且i * i 可能爆int，所以采用此种写法
    for (int i = 2; i <= x / i; i ++)
        if (x % i == 0) return false;
	return true;
}

4.2 试除法分解质因数：试除法分解质因数

算法思想：

  • 想要对一个数x分解质因数，主要是通过从小到大枚举其约数，当枚举到一个约数i时，通过一个循环，将x反复更新为x = x / i，并记录更新了多少次，这个次数就是i这个质因子的指数。
  • 当上述过程结束后，需要判定一下最后的x是否被除成了1，如果不是，则说明被除剩下的这个x也是最开始的x的一个质因子，且该质因子不能再被分解。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void devide(int x) {
    for (int i = 2; i <= x / i; i ++) {
        // 如果i是x的约数
        if (x % i == 0) {
            int cnt = 0;
            // 求出i的指数cnt，并且更新x（将这个质因子除干净）
            while (x % i == 0) {
                x /= i;
                cnt ++;
            }
            // 输出这个质因子和它的指数
            System.out.println(i + " " + cnt);
        }
    }
    if (x > 1) System.out.println(x + " " + 1);
}

4.3 筛质数：筛质数

4.3.1 朴素筛法：

算法思想：
  • 筛质数的目的在于求出1 ~ n之间的质数。那么比较快速的办法就是将1 ~ n当中不是质数的数给筛出去
  • 朴素筛法是利用已经确定了的质数进行筛除，其原理是将一个质数的所有小于等于n的倍数全部筛除

一般都不用朴素筛法，都有线性筛了，谁还用朴素筛法呀~

代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 记录质数的个数
int cnt = 0;
// 存储所有的质数
int[] primes = new int[n];
// st 表示当前数是否被筛掉
boolean[] st = new boolean[n + 10];
// 从 2 开始枚举每个数
for (int i = 2; i <= n; i ++) {
    // 如果当前的数已经被筛掉，则跳过该次循环
    if (st[i]) continue;
    // 否则将其加到质数数组中，同时cnt ++
    primes[cnt ++] = i;
    // 用当前质数筛掉其所有的倍数（如2i，3i都被筛掉）
    for (int j = i + i; j <= n; j += i) st[j] = true;
}

4.3.2 线性筛法：

算法思想：
  • 线性筛法可以理解为是对朴素筛法的优化，因为朴素筛法里会多次筛除同一个数，而线性筛法中，每个合数只会被筛掉一次。
  • 其主要思想是通过每个合数的最小质因子将其筛掉。
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
int cnt = 0;
int[] primes = new int[n];
boolean[] st = new boolean[n + 10];
for (int i = 2; i <= n; i ++) {
    // if (st[i]) continue; 此处不能continue，因为还需要用i来筛掉后面的合数
    if (!st[i]) primes[cnt ++] = i;
    // 每次筛掉的数为primes[j] * i，所以需要primes[j] * i <= n
    for (int j = 0; primes[j] <= n / i; j ++) { 
        st[primes[j] * i] = true;
        // 保证primes[j]为primes[j] * i的最小质因子，当这个条件发生后，下一个枚举的元素一定大于primes[j] * i的最小质因子，所以需要break
        if (i % primes[j] == 0) break;
    }
}

4.4 试除法求约数：试除法求约数

算法思想：

与求质数差不多，从0开始枚举到n\sqrt{n}，对每个数i进行判断，如果是x的约数，且i != x / i，则将i与x / 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
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = sc.nextInt(); 
        while (T -- > 0) {
            List<Integer> devisors = new ArrayList();
            int x = sc.nextInt();
            for (int i = 1; i <= x / i; i ++) {
                if (x % i == 0) {
                    devisors.add(i);
                    if (x / i != i) devisors.add(x / i);
                }
            }
            Collections.sort(devisors);
            for (int a : devisors) bw.write(a + " ");
            bw.write("\n");
        }
        bw.flush();
    }
}

4.5 约数个数：约数个数

算法思想：

  • 该算法求解的是一个数x的所有2 ~ x - 1中的约数个数
  • 该算法基于约数个数公式：(α1+1)×(α2+1)×...×(αk+1)(\alpha_1 + 1) \times (\alpha_2 + 1) \times ... \times (\alpha_k + 1)，其中α1\alpha_1为x的第一个质因子的指数，α2\alpha_2为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
import java.util.*;

public class Main {
    static final int mod = (int)1e9 + 7;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        HashMap<Integer, Integer> primes = new HashMap<>();
        while (n -- > 0) {
            int x = sc.nextInt();
            for (int i = 2; i <= x / i; i ++) {
                int s = 0;
                while (x % i == 0) {
                    x /= i;
                    s ++;
                }
                primes.put(i, primes.getOrDefault(i, 0) + s);
            }
            if (x > 1) {
                primes.put(x, primes.getOrDefault(x, 0) + 1);
            }
        }
        long res = 1;
        for (int value : primes.values()) 
            res = res * (value + 1) % mod;
        
        System.out.println(res);
    }
}

4.6 约数之和：约数之和

算法思想：

  • 4.5节是求一个数的约数个数，而4.6则是求这些约数的和。
  • 该算法同样基于公式：(p10+p11+...+p1α1)×...×(pk0+pk1+...+pkαk)(p_1^0 + p_1^1 + ... + p_1^{\alpha_1}) \times ... \times (p_k^0 + p_k^1 + ... + p_k^{\alpha_k})。其中，p1p_1是第一个质因子，α1\alpha_1是第一个质因子的指数。
  • 上式中，可以利用t=t×p+1t = t \times p + 1求解每一项，例如第一项tα1t_{\alpha_1}：t0=1,t1=p+1,t2=p2+p+1,...,tα1=pα1+...+1t_0 = 1, t_1 = p + 1, t_2 = p^2 + p + 1, ..., t_{\alpha_1} = p^{\alpha_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
import java.util.*;

// 求n个数的乘积，再求这个数的所有约数之和
public class Main {
    static final int mod = (int)1e9 + 7;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        HashMap<Integer, Integer> primes = new HashMap<>();
        while (n -- > 0) {
            int x = sc.nextInt();
            for (int i = 2; i <= x / i; i ++) {
                int s = 0;
                while (x % i == 0) {
                    x /= i; // 同4.5节
                    s ++;
                }
                primes.put(i, primes.getOrDefault(i, 0) + s);
            }
            if (x > 1) primes.put(x, primes.getOrDefault(x, 0) + 1);
        }
        long res = 1;
        for (Map.Entry prime : primes.entrySet()) { // 遍历容器中的每一项
            long t = 1;
            int key = (int)prime.getKey(), value = (int)prime.getValue();
            while (value -- > 0) t = (t * key + 1) % mod; // 求解公式的每一项
            res = res * t % mod; // 将公式的每一项相乘
        }
        System.out.println(res);
    }
}

补充map遍历方式：

1
2
3
for (int key : map.keySet()) {} // 遍历每项key
for (int value : map.values()) {} // 遍历每项value
for (Map.Entry<Integer, Integer> p : entrySet()) {} // 遍历map的每个对象

4.7 最大公约数：最大公约数

算法思想：

如果一个数d能整除a，且能整除b，那么d一定能整除c₁ * a + c₂ * b。所以d也能够整除a - c * b，令c = (a / b)向下取整，则a - c * b = a mod b，所以d也能整除a mod b，故a、 b两个数的最大公约数等于b、 a mod b这两个数的最大公约数。这就是欧几里得算法的核心之处。

代码实现：

1
2
3
4
public static int gcd(int a, int b) {
    // 如果b等于0，那么最大公约数就是a，否则就是gcd(b, a % b)
    return b > 0 ? gcd(b, a % b) : a;
}

4.8 欧拉函数：欧拉函数

算法思想：

  • 欧拉函数是指：对于一个正整数x，小于或等于x的正整数中与x互质的正整数个数（包括1）的个数，记作φ(n)\varphi(n)。
  • 欧拉函数的公式推导大致为：

欧拉公式.png
其中pip_i为x的每一个质因子。上述公式的除法均为整除（即下取整），上述公式的思想为：1 ~ x中总共有x个数，减去与x有相同质因子的数后，剩下的数均与x互质，而每次会重复减去相同的数，所以再加回来（容斥原理）。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int getEuler(int x) {
    int res = x;
    for (int i = 2; i <= x / i; i ++) {
        if (x % i == 0) {
            // 公式，这种写法是避免出现小数，等价于res = res *(1 - 1 / i);
            res = res - res / i; 
            // 把 i 除干净
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) res = res - res / x;
    return res;
}

4.9 筛法求欧拉函数：筛法求欧拉函数

算法思想：

主要思想还是基于4.8中的公式，此算法适用于题目要求求解1 ~ x中的每一个数的欧拉函数值。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static final int N = 1000010;
static int[] primes = new int[N];
static boolean[] st = new boolean[N];
static int[] phi = new int[N]; // 用于存放每个数的欧拉函数值
public static void getEuler(int x) {
    int cnt = 0;
    phi[1] = 1; // 对于phi[]，由于其实际意义，i从1开始
    for (int i = 2; i <= x; i ++) {
        if (!st[i]) {
            primes[cnt ++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; primes[j] <= x / i; j ++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) {
                phi[i * primes[j]] = primes[j] * phi[i]; // 公式1
                break;
            }
            // 不需要else，因为如果执行了if,就会break
            phi[i * primes[j]] = (primes[j] - 1) * phi[i]; // 公式2
        }
    }
}

公式推导：

  • 公式1： 由于此时i % primes[j] == 0，说明primes[j]是i的最小质因子，则在计算phi[i * primes[j]]时，(1 - 1 / primes[j])已经在求解phi[i]时被乘过一次，所以此时不需要乘这一项。

φ(i× primes[j])=i× primes[j]×(1−1p1)×(1−1p2)×⋯×(1−1pk)=primes[j]×φ(i)\varphi(i \times\: \text{primes}[j]) = i \times\: \text{primes}[j] \times \left(1 - \frac{1}{p_1}\right) \times \left(1 - \frac{1}{p_2}\right) \times \cdots \times \left(1 - \frac{1}{p_k}\right) = \text{primes}[j] \times \varphi(i)

  • 公式2： 由于此时i % primes[j] != 0，说明primes[j]不是i的质因子，则在计算phi[i * primes[j]]时，需要乘(1 - 1 / primes[j])这一项，化简即可。

φ(i× primes[j])=i× primes[j]×(1−1p1)×(1−1p2)×⋯×(1−1pk)×(1−1primes[j])=primes[j]×(1−1primes[j])×φ(i)=(primes[j]−1)×φ(i)\varphi(i \times\: \text{primes}[j]) = i \times\: \text{primes}[j] \times \left(1 - \frac{1}{p_1}\right) \times \left(1 - \frac{1}{p_2}\right) \times \cdots \times \left(1 - \frac{1}{p_k}\right) \times (1 - \frac{1}{\text{primes}[j]}) \\ = \text{primes}[j] \times (1 -\frac{1}{\text{primes}[j]}) \times \varphi(i) \\ = (\text{primes}[j] - 1) \times \varphi(i)

4.10 快速幂：快速幂

算法思想：

  • 快速幂可以快速求解ab%pa^b \% p的结果。aba^b在java中虽然有方法pow可以使用，但是在计算过程中很容易就爆long，而快速幂计算的每一步都会%p\% p，一般不会爆long。
  • 其思想为先预处理出a20,a21,...,a2log⁡ba^{2^0}, a^{2^1}, ..., a^{2^{\log b}}的结果，这些数每一个都是前一个的平方。这一步显然是O(log⁡b)\mathcal{O}(\log b)复杂度的。
  • 再将aba^b分解为若干个前面预处理出来的值相乘，即将b分解为前面预处理出来的值的指数相加，这一步可以使用二进制进行计算，例如：十进制中的a5a^5，5的二进制的101，则5可以写为20+222^0 + 2^2，那么a5a^5就被分解为a20×a22a^{2^0} \times a^{2^2}，此时就可以用预处理出来的值相乘得到。而这一步也是O(log⁡b)\mathcal{O}(\log b)的，因此时间复杂度为O(log⁡b)\mathcal{O}(\log b)。

代码实现：

该模板相当精妙，在每次while循环时，算出a2ia^{2^i}，同时判断这一个预处理出来的值需不需要乘进去，并达到了更新a和b的效果

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int qmi(int a, int b, int p) {
    // 防止p=1，当p=1时，答案为0
    int res = 1 % p;
    while(b > 0) {
        // (b & 1)要加括号，否则&会被当作逻辑运算符，(b & 1) == 1 表示b的二进制中最后一位是否是1，& 运算符表示参与计算的两个数二进制中对应位置的数都是1才是1，否则为0
        if ((b & 1) == 1) res = (int)((long)res * a % p);
        // 将a更新为a^2(java为强类型语言，比c++严格，必须最后手动强转为int再复制给a)
        a = (int)((long)a * a % p);
        // 删除b的二进制中最后一位数
        b >>= 1;
    }
    return res;
}

4.11 快速幂求逆元：快速幂求逆元

算法思想：

  • 乘法逆元定义：若整数b, m互质，并且对于任意的整数a，如果满足b|a，则存在一个整数x，使得a/b ≡ a * x (mod m)，则称x为b的模m乘法逆元，记作b⁻¹ (mod m)。b存在乘法逆元的充分必要条件是b与模数m互质。

ab=a⋅x(modm)b⋅x≡1(modm)∵m为质数，由费马小定理知,bm−1≡1(modm)又∵bm−1=b⋅bm−2(m≥2)∴x≡bm−2(mod m)\frac{a}{b} = a \cdot x \pmod{m} \\ b \cdot x \equiv 1 \pmod{m} \\ \because m\text{为质数，由费马小定理知,} \\ b^{m-1} \equiv 1 \pmod{m} \\ \text{又} \because b^{m-1} = b \cdot b^{m-2}\quad (m \geq 2) \\ \therefore x \equiv b^{m-2}\quad (\text{mod } m)

  • 当b为m的倍数时，显然，b % m = 0，不存在逆元；
  • 当b不是m的倍数时，b的逆元为bm−2%mb^{m - 2} \% m。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int qmi(int a, int b, int p) {
    int res = 1 % p;
    while (b != 0) {
        if ((b & 1) == 1) res = (int)((long)res * a % p);
        a = (int)((long)a * a % p);
        b >>= 1;
    }
    return res;
}

int a = sc.nextInt(), p = sc.nextInt();
int res = qmi(a, p - 2, p);
if (b % m != 0) System.out.println(res);
else System.out.println("impossible");

4.12 扩展欧几里得算法：扩展欧几里得算法

算法思想：

  • 想了解扩展欧几里得算法，先引入裴属定理： 若a, b 是整数,且 gcd(a , b) = d ，那么对于任意的整数x, y, ax + by都一定是d的倍数，特别地，一定存在整数x, y，使ax + by = d成立。而扩展欧几里得算法则可以很方便的求解任意正整数a, b的x, y这两个系数。即通过函数exgcd(a, b, x, y)求得系数x, y。注意：x, y并不唯一。
  • 由欧几里得算法知，gcd(a, b) = gcd(b, a % b)，而a % b = a - a / b * b ，那么在递归求exgcd(b, a % b, y, x)时有by + (a % b)x = d，化简得ax + (y - a / b * x)b = d，说明在递归时系数x不用更新（这里的x是指exgcd函数里的x，因为在每次进行递归时，会将实参交换后再复制给形参），只需要更新y。
  • 在java中没有类似C ++的引用类型，可以用数组进行代替。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static int[] x = new int[1];
static int[] y = new int[1];
// 形式上是把gcd拆开写
public static int exgcd(int a, int b, int[] x, int[] y) {
    if (b == 0) {
        x[0] = 1;
        y[0] = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    // 核心，更新系数，这里实际上不只是更新y，只是变量名统一为y了，实际上是交替更新x, y
    y[0] -= a / b * x[0];
    return d;
}

4.13 线性同余方程：线性同余方程

算法思想：

  • 可以通过扩展欧几里得算法求解线性同余方程ax ≡ b (mod m)。从取模的定义出发，可以根据ax ≡ b (mod m)构造出ax = my' + b，令y = -y'，整理得ax + my = b，当b为a, m的最小公倍数的倍数时，可以利用扩展欧几里得算法进行求解，而当b不是其倍数时，则无解。
  • 当用扩展欧几里得求出一组x0,y0x_0, y_0后，此时的x0,y0x_0, y_0满足的是ax0+my0=gcd(a,m)ax_0 + my_0 = gcd(a, m)，此时，我们将等式两边同时乘以bgcd(a,m)\frac {b}{gcd(a, m)}，得到ax0(bgcd(a,m))+my0(bgcd(a,m))=bax_0(\frac {b}{gcd(a, m)}) + my_0(\frac {b}{gcd(a, m)}) = b，令x=x0(bgcd(a,m))x = x_0(\frac{b}{gcd(a, m)})，y=y0(bgcd(a,m))y= y_0(\frac{b}{gcd(a, m)})，则此时的x, y即为原线性同余方程的一组解。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static int[] x = new int[1];
static int[] y = new int[1];
public static int exgcd(int a, int b, int[] x, int[] y) {
    if (b == 0) {
        x[0] = 1;
        y[0] = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y[0] -= a / b * x[0];
    return d;
}

int d = exgcd(a, m, x, y);
// 若b不为d的倍数，则原线性同余方程无解
if (b % d != 0) bw.write("impossible\n"); 
// mod m是为了将其转换为int范围内的解
else bw.write((long)x[0] * (b / d) % m + "\n"); 
bw.flush();

4.14 高斯消元O(n3)\mathcal{O}(n^3)：高斯消元解线性方程组

算法思想：

高斯消元的原理是将线性方程组的增广矩阵进行初等行变换，使之成为上三角矩阵，再通过上三角矩阵倒着解出未知数。
步骤如下：

  • 依次遍历每一列c;
  • 找到这一列中绝对值最大的元素行号，若最大元素为0，则不需要处理此列；
  • 将其交换到第r行（r从0开始）;
  • 将第r行第c列元素化为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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
import java.util.*;
import java.io.*;

public class Main {
    static final int N = 110;
    static int n;
    static double[][] a = new double[N][N];
    static final double eps = 1e-6;
    // 便于交换数组中的元素
    public static void swap(int x1, int y1, int x2, int y2) { 
        double t = a[x1][y1];
        a[x1][y1] = a[x2][y2];
        a[x2][y2] = t;
    }
    public static int gauss() {
        int c, r; // col row
        for (c = 0, r = 0; c < n; c ++) {
            // 标记当前列中最大元素行号
            int t = r; 
            // 找到最大元素行号
            for (int i = r; i < n; i ++) 
                if (Math.abs(a[i][c]) > Math.abs(a[t][c])) 
                    t = i;

            // 若最大的一个元素为0，则该列不需要再进行处理
            if(Math.abs(a[t][c]) < eps) continue; 

            // 将找到的这行换到第r行,从第c列开始（c列之前的全为零且能与之交换的也是0）
            for (int i = c; i <= n; i ++)  swap(t, i, r, i); 

            // 将这一行所有的数除以这一行的第c个数（将第c个数化为1）
            for (int i = n; i >= c; i --) a[r][i] /= a[r][c]; 

            // 将该列在该行一下的元素化为0，初等行变换（某一行减去某一行的若干倍）
            for (int i = r + 1; i < n; i ++) { 
                // 若该列r行一下有元素本身是0，则元素所在行不需要进行处理
                if (Math.abs(a[i][c]) > eps) 
                    for (int j  = n; j >= c; j --)  
                        a[i][j] -= a[r][j] * a[i][c]; // 初等行变换
            }
            // 此处r也可以理解为增广矩阵的秩，可以通过秩判定唯一解/无穷多解/无解
            r ++; 
        }

        if (r < n) {
            for (int i = r; i < n; i ++) {
                // 如果系数为0，但多项式和不为0，则说明无解
                if (Math.abs(a[i][n]) > eps) return 2; 
            }
            // 否则为无穷多解
            return 1; 
        }
        // 唯一解的情况
        else {
            // 从倒数第二行往上解方程
            for (int i = n - 2; i >= 0; i --) { 
                for (int j = i + 1; j < n; j ++) // i为行数，j为列数
                    // 系数乘以未知数的值(值在该行的下一行(第j行)已经解出，并存放在a[][n])
                    a[i][n] -= a[i][j] * a[j][n]; 
            }
            return 0;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        // 读入增广矩阵
        for (int i = 0; i < n; i ++) { 
            String[] s = br.readLine().split(" ");
            // 每行会多一个多项式的和
            for (int j = 0; j <= n; j ++) { 
                a[i][j] = Double.parseDouble(s[j]);
            }
        }

        int ans = gauss();
        // 唯一解
        if (ans == 0)  
            for (int i = 0; i < n; i ++)
                if(Math.abs(a[i][n]) < eps)
                    // 避免数据存储时精度误差（例如存的答案为-0.00000000000001，如果保留两位小数会输出-0.00，答案应为0.00）
                    System.out.printf("0.00\n"); 
                else
                    System.out.printf("%.2f\n", a[i][n]);
        else if (ans == 1) System.out.println("Infinite group solutions"); // 无穷多解
        else System.out.println("No solution"); // 无解
    }
}

4.15 简单博弈论：Nim游戏

算法思想：

博弈论又被称为对策论(Game Theory)，既是现代数学的一个新分支，也是运筹学的一个重要学科。博弈论主要研究已公式化的激励结构间的相互作用，是研究具有斗争或竞争性质现象的数学理论和方法。博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。
以Nim游戏为例：给定n堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作（即没有石子可拿）的人视为失败。
问如果两人都采用最优策略，先手是否必胜？
结论：

  • 每堆石子的异或为0，则先手必败
  • 每堆石子的异或为1，则先手必胜

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] s = br.readLine().split(" ");
        int[] a = new int[100010];
        int res = 0; 
        for (int i = 0; i < n; i ++) {
            a[i] = Integer.parseInt(s[i]);
            res ^= a[i];
        }
        if (res == 0) System.out.print("No"); 
        else System.out.print("Yes");
    }
}

第五章：动态规划

5.1背包问题

考虑背包问题的时候，状态表示为：前i个物品（第一维），每增加一个限制，增加一维，然后再考虑对代码做等价变形优化空间。

5.1.1 01背包问题

问题描述：

01背包问题描述的是：有N件物品和一个容量为V的背包。每件物品只能使用一次。其中，第i件物品的体积是vi，价值是wi，问：将哪些物品装进背包，可使这些物品的体积不超过背包容量，且总价值最大。

问题分析：

01背包.png

代码实现：
  • 朴素版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.io.*;

public class Main {
    static final int N = 1010;
    static int[] v = new int[N], w = new int[N];
    static int[][] f = new int[N][N];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        for (int i = 1; i <= n; i ++) {
            String[] s1 = br.readLine().split(" ");
            v[i] = Integer.parseInt(s1[0]);
            w[i] = Integer.parseInt(s1[1]);
        }
        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] = Math.max(f[i][j], f[i - 1][j - v[i]] + w[i]);
            }
        System.out.println(f[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
import java.io.*;

public class Main {
    static final int N = 1010;
    static int[] v = new int[N], w = new int[N];
    static int[] f = new int[N];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        for (int i = 1; i <= n; i ++) {
            String[] s1 = br.readLine().split(" ");
            v[i] = Integer.parseInt(s1[0]);
            w[i] = Integer.parseInt(s1[1]);
        }
        for (int i = 1; i <= n; i ++) {
            for (int j = m; j >= v[i]; j --) {
                f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
            }
        }
        System.out.println(f[m]);
    }
}

优化成一维的说明：对于01背包一维优化的理解

5.1.2 完全背包问题

问题描述：

有N种物品和一个容量为V的背包，每种物品都有无限件可以使用。其中，第i件物品的体积是vi，价值是wi。问：将哪些物品装进背包，可使这些物品的体积不超过背包容量，且总价值最大。

问题分析：

完全背包.png
注： 上图中的k从1开始枚举。也可以从0开始枚举，则f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * 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
import java.io.*;

public class Main {
    public static final int N = 1010;
    public static int[][] f = new int[N][N];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int m = Integer.parseInt(s1[1]);
        int[] v = new int[N];
        int[] w = new int[N];

        for (int i = 1; i <= n; i ++) {
            String[] s2 = br.readLine().split(" ");
            v[i] = Integer.parseInt(s2[0]);
            w[i] = Integer.parseInt(s2[1]);
        }

        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] = f[i - 1][j]是因为完全背包在于第i个物品的个数，k层的f[i][j]实际上是k-1层算出来的f[i][j]。
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
        System.out.println(f[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
import java.io.*;

public class Main {
    static final int N = 1010;
    static int[] v = new int[N], w = new int[N];
    static int[][] f = new int[N][N];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        for (int i = 1; i <= n; i ++) {
            String[] s1 = br.readLine().split(" ");
            v[i] = Integer.parseInt(s1[0]);
            w[i] = Integer.parseInt(s1[1]);
        }
        for (int i = 1; i <= n; i ++)
            for (int j = 0; j <= m; j ++) {
                f[i][j] = f[i - 1][j];
                // 根据f[i][j]与f[i][j - v[i]]的关系推出
                if (j >= v[i]) f[i][j] = Math.max(f[i][j], f[i][j - v[i]] + w[i]); 
            }
        System.out.println(f[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
import java.io.*;

public class Main {
    static final int N = 1010;
    static int[] v = new int[N], w = new int[N];
    static int[] f = new int[N];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        for (int i = 1; i <= n; i ++) {
            String[] s1 = br.readLine().split(" ");
            v[i] = Integer.parseInt(s1[0]);
            w[i] = Integer.parseInt(s1[1]);
        }
        for (int i = 1; i <= n; i ++) 
            for (int j = v[i]; j <= m; j ++) 
                // 完全背包终极写法与01背包很像，此处是从小到大遍历体积
                f[j] = Math.max(f[j], f[j - v[i]] + w[i]); 
        System.out.println(f[m]);
    }
}

5.1.3 多重背包问题

问题描述：

有N种物品和一个容量为V的背包。第i件物品最多有si件，每件的体积为vi，价值为wi。问：将哪些物品装进背包，可使这些物品的体积不超过背包容量，且总价值最大。

问题分析：

多重背包问题的分析与完全背包问题几乎一样，只是对k多了一个限制（k <= s[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
import java.io.*;

public class Main {
    static final int N = 110;
    static int[] v = new int[N], w = new int[N], s = new int[N];
    static int[][] f = new int[N][N];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int m = Integer.parseInt(s1[1]);
        for (int i = 1; i <= n; i ++) {
            String[] s2 = br.readLine().split(" ");
            v[i] = Integer.parseInt(s2[0]);
            w[i] = Integer.parseInt(s2[1]);
            s[i] = Integer.parseInt(s2[2]);
        }
        for (int i = 1; i <= n; i ++) 
            for (int j = 1; j <= m; j ++) 
                for (int k = 0; k <= s[i] && k * v[i] <= j; k ++) 
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]); // 代码几乎与完全背包差不多
        System.out.println(f[n][m]);
    }
}
  • 二进制优化版

多重背包二进制优化主要是将多重背包问题转换为01背包问题：将每种物品分解为若干堆，这些堆的数量总是能够凑出这种物品原来数量的任意一种取法（例如一种物品总共有8个，则将其分为1、2、4、1这几堆），然后将分堆后的每一堆物品都看作是一件新物品，再对这个些物品做一遍01背包就能求出最终的解。

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
import java.io.*;

public class Main {
    static final int N = 25000;
    static int[] v = new int[N], w = new int[N];
    static int[] f = new int[N];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]), m = Integer.parseInt(s1[1]);
        int cnt = 0; // 表示最终物品的堆数，每一对物品只有拿和不拿两种状态
        for (int i = 1; i <= n; i ++) {
            String[] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]); // 当前物品的单个体积
            int b = Integer.parseInt(s2[1]); // 当前物品的单个价值
            int s = Integer.parseInt(s2[2]); // 当前物品的总数量
            int k = 1; // 将当前物品划分为很多堆，k表示每一堆的数量
            while (k <= s) { // 二进制优化，将其转为01背包问题
                cnt ++; // 每划分出一堆，总堆数加一
                v[cnt] = k * a; // 计算出这一堆的总体积
                w[cnt] = k * b; // 计算出这一对的总价值
                s -= k; // 更新这种物品还剩的数量
                k *= 2; // 更新k
            }
            if (s > 0) { // 若物品还有剩的，但是已经不足2^(k + 1)个，就直接将其看作新的一堆
                cnt ++;
                v[cnt] = a * s;
                w[cnt] = b * s;
            }
        }
        n = cnt; // 更新总物品堆数
        // 做一遍 01 背包
        for (int i = 1; i <= n; i ++)
            for (int j = m; j >= v[i]; j --)
                f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
        System.out.println(f[m]);
    }
}

5.1.4 分组背包问题：

问题描述：

有N组物品和一个容量是V的背包。每组物品有若干个，同一组内的物品最多只能选一个。且每件物品的体积是 v[i][j]，价值是 w[i][j]，其中i是组号，j是组内编号。问：将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

问题分析：

分组背包.png

代码实现：
  • 朴素版：
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
import java.util.*;

public class Main {
    static final int N = 110;
    static int[][] v = new int[N][N], w = new int[N][N];
    static int[] s = new int[N];
    static int[][] f = new int[N][N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        for (int i = 1; i <= n; i ++) {
            s[i] = sc.nextInt();
            for (int j = 1; j <= s[i]; j ++) {
                v[i][j] = sc.nextInt();
                w[i][j] = sc.nextInt();
            }
        }
        for (int i = 1; i <= n; i ++) 
            for (int j = 1; j <= m; j ++) 
                for (int k = 1; k <= s[i]; k ++) 
                    if(v[i][k] <= j)
                        f[i][j] = Math.max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
        System.out.print(f[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
import java.io.*;

public class Main {
    static final int N = 110;
    static int[][] v = new int[N][N], w = new int[N][N];
    static int[] s = new int[N], f = new int[N];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int m = Integer.parseInt(s1[1]);
        // 读入数据
        for (int i = 1; i <= n; i ++) {
            s[i] = Integer.parseInt(br.readLine());
            for (int j = 1; j <= s[i]; j ++) {
                String[] s2 = br.readLine().split(" ");
                v[i][j] = Integer.parseInt(s2[0]);
                w[i][j] = Integer.parseInt(s2[1]);
            }
        }
        // 有些许类似于01背包对于每个物品选或不选，倒着枚举j
        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)
                        f[j] = Math.max(f[j], f[j - v[i][k]] + w[i][k]);
        System.out.println(f[m]);
    }
}

5.2 线性dp

算法思想：

这一类Dp先思考需要用几维来表示集合、每个集合表示的是什么、然后再思考需要将每个集合分成哪几个部分，且这几个部分均能够用已知集合推导出来。
线性Dp以最长公共子序列这道题为例，进行分析。

  • 问题描述： 给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
  • 问题分析：
    • 首先思考需要用几维来表示集合：本题是两个字符串，且问的是这两个字符串之间的关系，那么根据经验，可以使用二维数组表示集合；
    • 每个集合分别表示什么：f[i][j]表示所有在第一个字符串的前i个字母中出现，且在第二个字符串的前j个字母中出现的子序列；
    • 每个集合需要分为哪几个部分：可以按照是否包含第i个字母或是否包含第j个字母分为4部分。

最长公共子序列.png

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.*;
public class Main {
    static final int N = 1010;
    static int[][] f = new int[N][N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        char[] a = (" " + sc.next()).toCharArray();
        char[] b = (" " + sc.next()).toCharArray();
        for (int i = 1; i <= n; i ++) 
            for (int j = 1; j <= m; j ++) {
                f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                if (a[i] == b[j]) 
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
            }
        System.out.println(f[n][m]);
    }
}

5.3 区间dp

算法思想：

区间Dp的题目通常的枚举顺序是：先枚举区间长度，再枚举左端点、再枚举决策。
下面将以石子合并这道题为例进行分析：

题目描述：

设有 NN 堆石子排成一排，其编号为 1,2,3,…,N1,2,3,…,N。
每堆石子有一定的质量，可以用一个整数来描述，现在要将这 NN 堆石子合并成为一堆。
每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
例如有 44 堆石子分别为 1 3 5 2， 我们可以先合并 1、21、2 堆，代价为 44，得到 4 5 2， 又合并 1、21、2 堆，代价为 99，得到 9 2 ，再合并得到 1111，总代价为 4+9+11=244+9+11=24；
如果第二步是先合并 2、32、3 堆，则代价为 77，得到 4 7，最后一次合并代价为 1111，总代价为 4+7+11=224+7+11=22。
问题是：找出一种合理的方法，使总的代价最小，输出最小代价。

问题分析：

合并石子分析.png

代码实现：

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
import java.io.*;

public class Main {
    static final int N = 310, INF = 0x3f3f3f3f;
    static int[] s = new int[N];
    static int[][] f = new int[N][N];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] s1 = br.readLine().split(" ");
        for (int i = 1; i <= n; i ++) s[i] = Integer.parseInt(s1[i - 1]);
        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 ++) { // i实际上就是左端点
                int l = i, r = i + len - 1; // 定义左右端点
                f[l][r] = INF; // 初始化f[l][r]，否则全是0，最小代价会被错误地更新
                for (int k = l; k < r; k ++) { // 从左端点开始，遍历每个分界点
                    // f[l][r]最终是由两个大区间合并，f[l][r]等于这两个大区间自身合并所需代价加合并这两个区间的代价
                    f[l][r] = Math.min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
                }
            }
        }
        System.out.print(f[1][n]); // 输出合并1~n这个区间的最小代价
    }
}

区间dp总结：

  1. 枚举区间长度len，len通常为2 ~ n;
  2. 枚举区间左端点（一般i 从第一个元素开始，右端点i + len - 1不能越界）；
  3. 进行决策：
  • 若有区间分界点，则枚举分界点（一般左端点位置为第一个分界点，右端点上一个位置为最后一个分界点）
  • 若不需要分界点，则直接进行决策

5.4 计数类dp

算法思想：

计数类Dp实际上就是计数类完全背包问题，只是在集合表示和集合属性上略有不同。计数类Dp中，f[i][j]的每一部分代表的就是该部分的数量，不需要加上价值，而完全背包则需要加上其价值。

问题分析：

笔误：集合表示只从前i个数中选，且总体积恰好是j的选法

计数类Dp.png

代码实现：

  • 优化时间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Scanner;

public class Main {
    static final int N = 1010, MOD = (int)(1e9 + 7);
    static int[][] f = new int[N][N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        f[0][0] = 1;
        for (int i = 1; i <= n; i ++) {
            for (int j = 0; j <= n; j ++) {
                // j需要从0开始遍历，当 j >= i 时，才有f[i] [j] = (f[i - 1] [j] + f[i] [j - i])这一步的转移，同完全背包朴素版。如果上面初始化时，将f[1~n][0]都初始化成1，那么这里的j可以从1开始
                f[i][j] = f[i - 1][j] % MOD;
                if (j >= i) f[i][j] = (f[i - 1][j] + f[i][j - i]) % MOD;
            }
        }
        System.out.print(f[n][n]);
    }
}
  • 优化时间+空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.Scanner;

public class Main {
    static final int N = 1010, MOD = (int)(1e9 + 7);
    static int[] f = new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        f[0] = 1;
        for (int i = 1; i <= n; i ++) 
            for (int j = i; j <= n; j ++) 
                f[j] = (f[j] + f[j - i]) % MOD;
        System.out.print(f[n]);
    } 
}

5.5 状态压缩dp

算法思想：

状态压缩dp的思想就是用一个数的二进制表现形式表示二维状态中某一维的状态。
以蒙德里安的梦想这道题为例：

蒙德里安的梦想：求把N×MN \times M的棋盘分割成若干个1×21 \times 2的长方形，有多少种方案。
例如2×42 \times 4的棋盘的方案有： 5.5状态压缩dp.png

题目中要求使用1 × 2的小方格把棋盘填满，那么我们可以横着填，也可以竖着填。当我们把横着填的长方形填完，那么竖着填的小方格的方案就是唯一的。因此我们只需要考虑横着填的长方形有多少种填法。
我们分析每一列，用一个二进制数表示该列长方形的摆放状态。如果该列的某一行是0，则表示该列的这行没有摆放长方形，1则是摆放了长方形。例如上面例图中的2 × 4棋盘，第二个摆放方案对应的状态表示为[11001100]\begin{bmatrix} 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \end{bmatrix}，那么我们可以用3表示第一列和第二列的状态，用0表示第三列和第四列的状态。
如何判断每一列的状态是不是一个合法的状态？
我们要知道，不是每一个数都能表示一个列的状态的，因为这是实际问题。例如，11的二进制表示1011就不是一个合法的状态，因为如果当前列这样摆放，那么竖着的长方形就无法摆放。
因此，只要一个数的二进制表示中出现了连续的奇数个0时，则该数就不是一个合法的状态。
如何进行状态转移？
首先我们定义状态数组f[i][j]f[i][j]表示前ii列摆放完成的所有方案数。
f[i][j]f[i][j]表示所有能从上一个列的状态转移过来的方案数之和。

假设第i−1i - 1列被戳的状态为kk，第ii列被戳状态为jj。（只考虑二进制表示中的11全部由上一列戳出的情况），那么这样第i−1i - 1列被戳和戳出的情况的考虑完了（即第i−1i - 1列的状态为j∣kj \mid k）。

能够从第i−1i - 1列戳到第ii列的条件（能转移的条件，实际就是在判断第i−1i- 1列的状态和转移方式是否合法）：

  • 第i−1i - 1与第ii列不能同时被戳（j & k = 0）
  • 在确定第i−1i- 1列被戳或向后戳出后所剩下的位置要能够摆放竖着的长方形（状态的二进制表示不能有连续奇数个0：即j | k的二进制表示不能有连续奇数个0）

状态转移方程：

1
2
if (满足能够从第i - 1列戳到第i列的条件)
    f[i][j] += f[i - 1][k];

初始化与答案：
根据f[i][j]f[i][j]的含义，第00列是不会被戳的，因此其上一列（虚拟）全是竖着摆放方块的（只有这一种方案），所以f[0][0]=1f[0][0] = 1。
当我们将全部的mm列（0∼m−10 \sim m - 1）摆好时，第mm列（不需要摆放方块的列）没有被戳的所有方案数之和即为答案，即f[m][0]f[m][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
import java.util.*;

public class Main {
    static final int N = 12, M = 1 << 12;
    static long[][] f = new long[N][M];
    static boolean[] st = new boolean[M];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            int n = sc.nextInt(), m = sc.nextInt();
            if (n == 0 && m == 0) break;
            // 预处理每个状态的合法性
            Arrays.fill(st, true);
            for (int i = 0; i < 1 << n; i ++) {
                int cnt = 0;
                for (int j = 0; j < n; j ++)
                    if (((i >> j) & 1) == 1) {
                        if ((cnt & 1) > 0) {
                            st[i] = false;
                            break;
                        }
                    }
                    else cnt ++;
                if ((cnt & 1) > 0) st[i] = false;
            }
            for (int i = 0; i < N; i ++) Arrays.fill(f[i], 0);
            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];
            System.out.println(f[m][0]);
        }
    }
}

第六章：由不同数据范围反推时间复杂度和算法内容

  1. n≤30⇒n \leq 30 \Rightarrow指数级别：dfs + 剪枝、状态压缩dp
  2. n≤100⇒O(n3)n \leq 100 \Rightarrow \mathcal{O}(n^3)：floyd、dp、高斯消元
  3. n≤1000⇒O(n2)或O(n2log⁡n)n \leq 1000 \Rightarrow \mathcal{O}(n^2) 或 \mathcal{O}(n^2 \log n)：dp、二分、朴素Dijkstra、朴素版Prim、Bellman-Ford
  4. n≤10000⇒O(n×n)n \leq 10000 \Rightarrow \mathcal{O}(n \times \sqrt{n})：块状链表、分块、莫队
  5. n≤105⇒O(nlog⁡n)n \leq 10^5 \Rightarrow \mathcal{O}(n \log n)：各种sort、线段树、树状数组、set/map、heap、拓扑排序、dijkstra + heap、prim + heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树
  6. n≤106⇒O(n)或常数较小的O(nlog⁡n)n \leq 10^6 \Rightarrow \mathcal{O}(n)或常数较小的\mathcal{O}(n \log n)：单调队列、hash、双指针、并查集，kmp、AC自动机、sort、树状数组、heap、dijkstra、spfa
  7. n≤107⇒O(n)n \leq 10^7 \Rightarrow \mathcal{O}(n)：双指针、kmp、AC自动机、线性筛质数
  8. n≤109⇒O(n)n \leq 10^9 \Rightarrow \mathcal{O}(\sqrt{n})：试除法判断质数
  9. n≤1018⇒O(log⁡n)n \leq 10^{18} \Rightarrow \mathcal{O}(\log n)：最大公约数，快速幂，数位dp
  10. n≤101000⇒O((log⁡n)2)(log⁡n表示位数)n \leq 10^{1000} \Rightarrow \mathcal{O}((\log n)^2)(\log n 表示位数)：高精度加减乘除
  11. n≤10100000⇒O(log⁡k×log⁡log⁡k)(k表示位数)n \leq 10^{100000} \Rightarrow \mathcal{O}(\log k \times \log\log k)(k表示位数)：高精度加减、FFT/NTT