CSP-S知识点备忘录

最近在备考 CSP-S，看到 B 站某竞赛教练有说到要拿省一需要补齐短板，检查自己每个知识点到底能会做什么难度的题目。考虑到自己最近一年多一直在随机刷题，虽然颇有进步，但是确实不太清楚自己每个知识点的具体掌握情况。稍微浏览了教练提供的 checklist 之后，意外的发现一些东西有点忘了，甚至有极个别的知识点我还不会（例如割点割边、树的重心等）。因此，我准备做一个备忘录，把自己已经忘掉的 CSP-J/S 组知识点做下总结，补齐短板，希望能够在复赛稳定打出一个满意的成绩，不要因为知识点忘了而丢分。

本备忘录优先记录有所遗忘的知识点，如有时间，会对重点考点的重要技巧再进行一些总结。

时间复杂度计算

初赛里的题目主要是考主定理，对于下面的式子：

T(n) = aT(\frac{n}{b}) + f(n)

当 $f(n) = O(n^{\log_ba - \epsilon}), \epsilon > 0$ 时，有 $T(n) = \Theta(n^{\log_ba})$ ，例如 $T(n) = 2T(\frac{n}{2}) + 1$ ，复杂度就是 $\Theta(n)$ 。

当 $f(n) = \Omega(n^{\log_ba + \epsilon}), \epsilon > 0$ 时，有 $T(n) = \Theta(f(n))$ ，直观理解就是对分治的结果进行合并时，合并代价太大了，以至于复杂度由合并复杂度主导。

当 $f(n) = \Theta(n^{\log_ba}\log^kn), k \ge 0$ 时，有 $T(n) = \Theta(n^{\log_ba} \log^{k + 1}n)$ 。例如 $T(n) = 2T(\frac{n}{2}) + n$ （归并排序），复杂度就是 $\Theta(n\log n)$ 。再例如， $T(n) = T(\frac{n}{2}) + 1$ （二分查找），复杂度就是 $\Theta(\log n)$ 。

基础算法与数据结构

排序

快速排序的最佳实践：

void quick_sort(int l, int r) {
    if (l >= r) return;

    int pivot = a[(l + r) / 2];
    int i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while (a[i] < pivot);
        do j--; while (a[j] > pivot);
        if (i < j) {
            swap(a[i], a[j]);
        }
    }
    
    quick_sort(l, j);
    quick_sort(j + 1, r);
}

划分区间时，左边的区间中都是 <= pivot 的数，右边的区间中都是 >= pivot 的数，这个隐含的意思是等于 pivot 的数在左右两个区间都有。

下面证明按照 [l, j] 和 [j + 1, r] 分区不会导致死递归。

本质上，我们需要证明每次递归调用的子数组范围 [l, j] 和 [j + 1, r] 都严格小于原数组 [l, r]（即至少减少一个元素），或者证明两个数组都不为空就好了。

首先，左半边区间 [l, j] 一定不会为空，因为最差的情况就是 l == j。下面只要证明右子数组不为空即可。事实上，i 会先移动到 pivot 或者更左边的第一个 >= pivot 的数字上，j 会先移动到 pivot 或者更右边的某个 <= pivot 的数字上，这又分两种情况：

倘若都恰好是 pivot，由于 (l + r) / 2 < r，所以 j < r 一定成立，所以 j + 1 <= r 一定成立，所以 [j + 1, r] 也不为空
倘若至少有一个不是 pivot，说明这个时候一定有 i < j，必然会发生一次交换，然后再分别至少执行一次 i++, j--，这个时候 j 一定移动得 < r 了，所以 j + 1 <= r 一定成立。

综上，左子数组和右子数组都不为空，都是原数组严格减小后的结果，所以不会死递归。

代码模板记忆：只要记得代码中全是严格大于和小于号，并记住是以 j 为分割点进行数组划分即可。

以上内容总结自 AcWing 算法基础课。

前/中/后缀表达式

差分

主要是二维差分记忆有点模糊。

如何得到差分矩阵？

d[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1]

这个结果并不是很直观。

如何在差分矩阵上做修改？

画一个 $3 \times 3$ 的矩阵，看如何把左上角 $2 \times 2$ 的矩阵通过差分变成全 1。

需要：

d[1][1] += 1;
d[1][3] -= 1;
d[3][1] -= 1;
d[3][3] += 1;

所以，如果要把 $(x_1, y_1)$ 到 $(x_2, y_2)$ 的矩阵都加上 $val$ ，需要：

d[x_1][y_1] += val;
d[x_1][y_2 + 1] -= val;
d[x_2 + 1][y_1] -= val;
d[x_2 + 1][y_2 + 1] += val;

关于区间加等差数列，笔者有点过于翡透了，推了一段时间公式并没有推出来想要的结果。事实上，在考场上我们也可能会遇到类似的情况。倘若我们真的忘了区间加等差数列的结论了，可以使用如下代码帮我们进行回忆：

int a[10], b[10], c[10];

void meibao() {
    int s = 3, d = 4;
    for (int i = 2; i <= 6; i++) {
        a[i] += s + (i - 2) * d;
    }

    for (int i = 1; i < 10; i++) {
        printf("%3d ", a[i]);
    }

    printf("\n");

    for (int i = 1; i < 10; i++) {
        b[i] = a[i] - a[i - 1];
        printf("%3d ", b[i]);
    }

    printf("\n");

    for (int i = 1; i < 10; i++) {
        c[i] = b[i] - b[i - 1];
        printf("%3d ", c[i]);
    }
}

输出结果为：

  0   3   7  11  15  19   0   0   0 
  0   3   4   4   4   4 -19   0   0 
  0   3   1   0   0   0 -23  19   0

通过观察，我们发现一阶差分上规律比较明显，先在 l 处加一个首项，再在 [l + 1, r] 上加公差，最后在 r + 1 上减掉最后一项。为了完成这三个对一阶差分的区间加操作，需要在二阶差分上做 6 次单点修改。

于是，我们归纳出在 [l, r] 上，加一个首项为 s，公差为 d 的等差数列怎么做：

void add(int l, int r, int s, int d) {
    // t 是最后一项
    int t = s + (r - l) * d;
    c[l] += s;
    c[l + 1] += d - s;
    c[r + 1] -= (t + d);
    c[r + 2] += t;
}

在考场上，我们写出这个之后，可以再写一个对拍去验证一下，这样就重新发明出了区间加等差数列公式。

事实上，在一阶差分数组上的规律更明显，但是可能得用线段树去维护一阶差分。

由于 NOI 特别把差分这个知识点在新大纲中提出来了，所以在这里做了比较多的总结。

二分查找

虽然我们已经会了下面这个模板：

while (l + 1 < r) {
    mid = (l + r) >> 1;
    if (check(mid)) {
        l = mid;
    } else {
        r = mid;
    }
}
// 单独判断 l 和 r

但是有些时候会有人问自己标准二分怎么写，或者直接给你来个程序填空或者捉虫，这个时候就还是得会标准二分。

二分要注意的地方主要有两个：

如何不丢/错过解
怎么样能不死递归

思考如何避免死递归时，不妨直接考虑最初始的数组长度就是 2，这是最容易死递归的情况。

以手写 lower_bound 为例子，假设我们想找 >= 1 的最小的数的位置，数组是 1 2，则可以这样写：

while (l < r) {
    mid = (l + r) >> 1;
    if (a[mid] >= 1) {
        r = mid;
    } else {
        l = mid + 1;
    }
}
return a[l];

为什么这样不会死递归？首先我们应该注意到，由于限制了 l != r，且右移是下取整的（除法是向 0 取整，负数时会有问题），所以一定有 ((l + r) >> 1) != r。因此，当 a[mid] 符合题意时，我们令 r = mid 即可，无需减去 1，减掉了会漏解。当 a[mid] 不符合题意时，说明 mid 没用，所以 l = mid + 1 即可。

类似的，还有一个东西叫做 mid = (l + r + 1) >> 1，这个东西是上取整的，所以在 l < r 时 mid != l。如果符合题意时要求区间左端点移动，则可以 l = mid，不符合题意时 r = mid - 1。

以上内容总结自算法竞赛进阶指南。

单调栈

解决各种问题

离散化

主要是 map 的大值域离散化

图论

链式前向星

先来一份代码：

// 数据结构
LL h[N], e[M], ne[M], w[M], idx;

// 加边函数
void add(int a, int b, LL c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

// 初始化邻接表
memset(h, -1, sizeof h);
idx = 0;
for (int i = 1; i <= m; i++) {
    LL a, b, c;
    cin >> a >> b >> c;
    add(a, b, c);
}

// 遍历 ver 结点的所有邻边，并做 dijkstra 的松弛操作
for (int i = h[ver]; i >= 0; i = ne[i]) {
    int v = e[i];
    if (d[v] > d[ver] + w[i]) {
        d[v] = d[ver] + w[i];
        q.push({d[v], v});
    } 
}

其中：

h[i] 存储的是 i 结点的第一条边的编号，注意所有 i 结点的邻边组成一条链表，所以 h[i] 相当于链表入口，一般初始化为 -1，表示链表为空。忘记初始化会 TLE，因为边的编号一直都是 0，跳不出循环。
e[id] 指的是编号为 id 的这条边指向的结点。
ne[id] 指的是编号为 id 的这条边所在链表的下一条边的 id。
add(a, b) 是加边函数，其逻辑是先把指向的结点 b 存到 e[idx] 中，再考虑创建一个新的链表结点，并将其头插到当前链表中作为新的头（ne[idx] = h[a], h[a] = idx++）

堆

二叉堆手写

对顶堆

反悔贪心

带权并查集

最小环

次短路

连通分量

割点与割边

二分图最大匹配

SPFA

DP

树形 DP

重心

树上背包

数位 DP

数据结构

表达式树

树状数组基本原理

lowbit，下标的结构

线段树扩展操作

动态开点线段树

扫描线

数学

约数函数

exgcd

主要是分析如何求通解。

假设现在已经得到了一组 $ax + by = c$ 的特解 $(x_0, y_0)$ ，则考虑 $x$ 最少变化多少，还能使得解出来的 $y$ 是整数。

不妨设 $x$ 最少变化 $d_1$ ，能够让 $y$ 还是整数，且 $y$ 的变化是 $d_2$ ，则有：

ax + by = a(x + d_1) + b(y - d_2) = c

也就是说

ad_1 = bd_2

所以有

d_2 = \frac{ad_1}{b}

我们想求最小的 $d_1$ ，使得 $d_2$ 也是整数，则要求 $ad_1$ 是 $b$ 的倍数，而 $ad_1$ 显然是 $a$ 的倍数，所以要：

ad_1 = \text{lcm}(a, b)

也就是：

d_1 = \frac{\text{lcm}(a, b)}{a}

所以 $x$ 的通解就是

x = x_0 + kd_1, k \in \Z

对于 $y$ 可以类似地得到结果。

扩展中国剩余定理（excrt）

我们直接跳过普通版中国剩余定理，因为其功能完全是扩展版的子集，且算法的逻辑很不一样。

扩展中国剩余定理的核心在于不断将现有的两个同余方程合并成一个，直到只剩下一个同余方程，此时我们也就解出了同余方程组的通解。

我们分析如何对如下两个方程组进行合并：

\begin{cases} x \equiv r_1 (\text{mod }m_1)\\ x \equiv r_2 (\text{mod }m_2) \end{cases}

先将其转化为带余除法的形式：

\begin{cases} x = k_1m_1 + r_1\\ x = k_2m_2 + r_2 \end{cases}

进而有：

k_1m_1 - k_2m_2 = r_2 - r_1

这是关于 $k_1$ 和 $k_2$ 的二元一次方程，其他量都是已知的，所以我们可以使用 exgcd 先求出 $k_1$ 的一个特解 $k_0$ ，并得到通解为 $k_1 = k_0 + t\times \frac{\text{lcm}(m_1, m_2)}{m_1}$ 。

我们把这个通解代入回 $x = k_1m_1 + r_1$ ，得到：

x = (k_0 + t\times \frac{\text{lcm}(m_1, m_2)}{m_1})\times m_1 + r_1

注意到这个式子中，只有 $x$ 和 $t$ 是未知的，其他的都是已知的，进一步整理有：

x = t\times \text{lcm}(m_1, m_2) + k_0m_1 + r_1

这个方程和 $x = k_1m_1 + r_1$ 形式很像，这意味着我们把最开始的两个方程，合并成了一个形式很像的方程。

落实到代码上，我们的合并方程函数相当于接收 4 个参数 $(r_1, m_1, r_2, m_2)$ ，即接收两个方程，最终返回两个参数 $(r, m)$ ，即一个新的方程，其中：

\begin{cases} r = k_0m_1 + r_1\\ m = \text{lcm}(m_1, m_2) \end{cases}

$k_0$ 需要使用 exgcd 计算，这个地方可能会触发无解，无解可以直接返回 $(0, 0)$ 。

把所有方程合并后，对于最终返回的 $(r, m)$ ，事实上就是方程：

x \equiv r(\text{mod }m)

所以 $x$ 的最小正整数解就是：

x_{min} = (r \text{ mod }m + m)\text{ mod }m

代码模板：

import sys

input = lambda: sys.stdin.readline().rstrip()

n = int(input())
rs = list(map(int, input().split()))
ms = list(map(int, input().split()))

def exgcd(a, b):
    if b == 0:
        return a, 1, 0

    g, xx, yy = exgcd(b, a % b)
    t = xx
    x = yy
    y = t - (a // b) * x
    return g, x, y

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def lcm(a, b):
    return a // gcd(a, b) * b

def combine_equation(r1, m1, r2, m2):
    g, x, y = exgcd(m1, m2)
    if (r2 - r1) % g != 0:
        return (0, 0)

    k0 = x * (r2 - r1) // g
    return (k0 * m1 + r1, lcm(m1, m2))

res = (rs[0], ms[0])
for i in range(1, n):
    res = combine_equation(res[0], res[1], rs[i], ms[i])

if res[0] == 0 and res[1] == 0:
    print("-1")
else:
    r, m = res[0], res[1]
    print((r % m + m) % m)

为什么这里给出的是 python 模板呢？因为这个算法是有可能出现最终结果不爆 long long，但中间过程爆 long long 的。要想彻底避免这种情况，应该使用龟速乘，但是我有点懒得写，所以直接 python 了。