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++）

堆

二叉堆手写

对顶堆

反悔贪心

带权并查集

最小环

次短路

强连通分量

特别注意，强连通分量并不一定是环，其可能是多个环，所以做题分析时要想清楚到底是要找环还是找强连通分量。

首先看一下 Tarjan 算法。

使用 Tarjan 算法求强连通分量时，我们想的是对于每个点 u，维护两个时间 dfn[u] 和 low[u]。其中 dfn[u] 为 u 被第一次访问时的 dfs 时间戳，也就是 dfs 序号，low[u] 表示通过 u 能够走到的点里最小的 dfn 值，其初始化为 low[u] = dfn[u]。

这里对 low[u] 做详细的说明，其实其包含两种情况：

从 u 可以走到一个之前从来没走过的邻点 v，则显然 low[v] 是可以用来更新 low[u] 的。
从 u 走到一个已经走过的邻点 v，这样又可以分两种情况：
- v 是在结点访问栈里面的，则说明我们往回走到了 u 的祖先 v，成了一个环，当然也可以用 low[v] 更新 low[u]。
- （最难理解的一种情况）v 被访问过，但是现在不在结点访问栈里面，那么 u 和 v 一定不在同一个强连通分量内。我们反证一下上面这个事情，假如 u 和 v 在同一个强连通分量内，则必然存在一条路径能从 v 走到 u。那么在第一次访问到 v 的时候，假如其到 u 的那条路上的点都没被访问过，则 v 可以一直 DFS 到 u，这时候是 v 在栈中，和不在栈中的条件矛盾；假如其到 u 的那条路上的点有的已经被访问过了，那么 u 一定被更早的点访问过了，这会推出 u 比 v 更早被访问，和条件矛盾。综上，这种情况下 u 和 v 一定不在同一个强连通分量内，无需更新 low[u]。

最后弹出强连通分量时，我们要先找到 dfn[u] = low[u] 的点，然后从栈中一直弹，直到弹到这个点，则这部分都是属于 u 为“根”的强连通分量。对于 dfn[u] != low[u] 的点，我们就不能启动弹栈这个操作，因为其不是强连通分量的“根”。

模板题

代码模板：

int n, m, timestamp = 0, dfn[N], low[N];
bool vis[N], instk[N];
vector<vector<int>> e(N);
vector<vector<int>> scc;
vector<int> stk;

void tarjan(int u) {
    vis[u] = true;
    stk.push_back(u);
    instk[u] = true;
    dfn[u] = ++timestamp;
    low[u] = dfn[u];

    for (auto v : e[u]) {
        if (!vis[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (instk[v]) {
            low[u] = min(low[u], low[v]);
        }
    }

    if (dfn[u] == low[u]) {
        vector<int> s;
        while (true) {
            int v = stk.back();
            stk.pop_back();
            s.push_back(v);
            instk[v] = false;
            if (v == u) {
                break;
            }
        }
        scc.push_back(s);
    } 
}

void meibao() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
    }

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            tarjan(i);
        }
    }

    int res = 0;
    for (int i = 0; i < scc.size(); i++) {
        if (scc[i].size() > 1) {
            res++;
        }
    }
    cout << res << "\n";
}

双连通分量

割点与割边

二分图最大匹配

SPFA

欧拉图

即能否一笔画的图，无向图的话需要每个点的度数都是偶数，有向图的话需要入度 = 出度。

DP

树形 DP

重心

树上背包

数位 DP

数据结构

表达式树

树状数组基本原理

lowbit，下标的结构

线段树扩展操作

动态开点线段树

扫描线

数学

约数函数

我们记一个数 $n$ 的约数个数为 $d(n)$ ，将 $d(n)$ 称为约数函数。显然，一个数 $n$ 的约数个数不会超过 $2\sqrt{n} + 1$ ，但这是一个很粗糙的估计，这种粗糙的估计会让我们对一些算法的复杂度做出错误的估计。

在做题时，真正有用的是我们要知道 $n$ 在一定范围内的时候， $d(n)$ 最大可能的值。比如：

$n \le 10^5$ ，则 $d(n)$ 最大只有 $128$ ，我们可以打表打出来发现是 $n = 83160$ 时取到，显然 $128^2$ 比 $n$ 还小不少。
$n \le 10^7$ ，则 $d(n)$ 最大只有 $448$ ，在 $n = 8648640$ 时取到。

假如 $n \le 10^7$ ，做题时我们可以粗糙地将 $d(n)$ 认为是 $500$ ，用这个数去估计计算量。

乘法逆元

使用之前特别关注是否存在

怎么求倒是小问题，一般来说直接用费马小定理 + 快速幂搞定了。最关键的其实应该是“怎么求”之前的东西，即先判断一道可以用逆元求解的问题，会不会出现逆元不存在的情况。

我们先回忆一下逆元的定义，假如 $ax \equiv 1(\text{mod}m)$ ，则 $x$ 是 $a$ 的乘法逆元。对于某个 $a$ ，为了使其乘法逆元 $x$ 存在，需要这个同余方程有解，转化成不定方程就是 $ax + my = 1$ 有解，这需要 $\gcd(a, m) = 1$ ，这就是乘法逆元存在的充要条件。

一般来说，题目中给的模数 $m$ 是素数，这个时候相当于 $a$ 只要不是 $m$ 的倍数就好了。特别地， $0$ 是 $m$ 的倍数，所以这个时候不存在乘法逆元。什么时候会出现倍数的情况呢？假如有一个要求乘法逆元的数有可能比 $m$ 大，且这个数的来历可能是一堆数加减乘除得到的，则不排除这个数是 $m$ 的倍数的可能。但我们用乘法逆元最多的情况是求组合数，组合数中是对一阶乘求逆元，而只要 $n < m$ ，就必然有 $\gcd(n!, m) = 1$ ，因为 $1$ 到 $n$ 中都没有 $m$ 这个素因子。

有时候给的模数为合数，或者可能要输入模数，这时候就更要格外小心逆元不存在的情况了。

事实上，我们应该把乘法逆元仍然按照除法去思考，除法是不能除 0 的，所以也不能求 0 的乘法逆元，就算算出了一个所谓的“乘法逆元”，也是错误的，这在除法中本该报出除 0 异常，但使用乘法逆元就会把这个本该抛异常导致程序崩溃的错误，变成一个悄悄的可以继续执行的错误，这种问题就会很难排查。

一个不存在的例子

有一个比较典型的容易犯错的例子，给一个数组 $a$ ，我们想求去掉里面某个数之后，剩下的数字的乘积，则我们很容易想到两种方案：

前后缀分解，直接用剩下的前缀和后缀的乘积相乘即可。
预处理所有数的乘积，每次询问除去去掉的那个数（即乘以逆元）。

对于第一种方法，完全没用到逆元，所以无需担心。对于第二种方法，不妨设 $a = [1, 2, 0, 3, 4]$ ，假如去掉的是 0，由于最开始预处理所有的数的乘积就是 0，所以按照这种做法算出来剩下的数的乘积还是 0，但实际上应该是 24，这就错了。

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