CSP 考前快速复习（S 组）下

作者：云斗官方教研团队 yummy 老师

算法

排序系列

大部分情况下 sort 够用了。但是掌握相关排序的流程，可能会对一些思路的实现产生启发；同时可能还可以出构造题，考察相关思想。

例如 MdOI R4 Kotori 要求在归并排序的过程中去掉太菜的人，是一个变形；

或者在一些按位处理，并且考虑每一位时需要按照重新排序的问题中可以考虑基数排序。

当问题的值域比较大，且不强制在线时我们可以考虑离散化。否则你可以考虑用 01-trie 来维护。

搜索

NOIP 时代搜索的出现频率很高，但是这里面很多题放现在都是有问题的——时间复杂度很多都是假的。

考纲中的搜索里面，双向搜索以及记忆化搜索是重点，时间复杂度通常比较好算；其他几个算法则更多地用来骗分，或者用类似随机化的办法考察。

搜索除了用于枚举外基本上就是用于遍历了，如 DAG 上跑 dp 很多时候就是用记忆化搜索实现的。

DP

事实上很多难度达到 S 组的 DP 事实上考纲没有超过 J 组，所以不止树形 DP 和状态压缩 DP 需要复习，比如说云斗 6 月 Silver 第 3 题和云斗 10 月 Golden 的 S 组第 2 题。

“动态规划的常用优化”？到底多常用？数据结构优化、前缀和优化自然是有的，斜率优化和四边形不等式到底能不能考，这点并没有明说。

图论

二分图

二分图是可以把点划分进两个集合，使得集合内部没有边的图。等价表述为没有奇环的图。

因为我们不考二分图匹配，所以基本上只有二分图判定。除了通过 DFS 时给结点染色外，还可以通过并查集维护，参考关押囚犯。

欧拉图

参考洛谷模板题。我一时间没想好这个东西除了模板能怎么考，可能会结合数据结构考你有欧拉回路的判定条件，或者把一个奇奇怪怪的题目转化成欧拉路。

有向无环图

主要考察拓扑排序（2020 年 CSP 第 3 题）。

最小生成树

贪心算法的应用，而且我最近做到了好多个图本身边数超大，无法直接套用模板，但是思考时仍然使用 Kruscal 算法的最小生成树题（类似 CSP2019-江西 网格图）。

最短路系列

Floyd 算法求的是所有点对的最短路，时间复杂度 $O(n^3)$，是最慢的，但是码量最小，允许负边。其可以结合矩阵快速幂考察，因为 $\min$ 对加法有分配律。

Dijkstra 算法求的是定点到所有点的最短路，时间复杂度 $O(n^2)$（不优化）或 $O(m\log m)$（优先队列优化）或 $O(n\log n+m)$（斐波那契堆优化，不实用）。其不允许负边，因为使用的是贪心算法。

Bellman-Ford 算法和其队列优化版本求的也是定点到所有点的最短路，时间复杂度最坏 $O(nm)$，允许负边。一般而言如果题目里有负边（无法用一些技巧转化），则应当允许 Bellman-Ford 通过；但是如果你正在骗分，你可以考虑使用队列优化版本并祈祷 CCF 不会把你的程序打回原形喜提 TLE。

求最短路时不一定问的是边权和，可能是边权最小值或者其他类型的数据。你需要注意，求最短路时的运算必须有保序性，例如求路径边权异或和最小值就不适用上面的算法，因为 $a<b$ 不代表 $a\oplus c<b\oplus c$。

次短路的求法就是在最短路基础上同时维护最小和次小值。我建议把“维护前二小”当成一个整体，重新定义求最小值（四选二）和加法。

Tarjan 系列

该系列包括强连通分量与缩点、割点割边、点（边）双连通分量、离线求 LCA 四个主要应用。

这几个算法实现略有区别，复习时可以仔细思考其中的细节。

云斗 10 月 Golden Round S 组第 4 题的 72 分部分分也是 Tarjan 算法，大家可以去补个题。

数学

高中代数和高中几何

可能会放点解析几何？但是应该会局限于直线和圆，圆锥曲线还是离谱了点。

主要是如果有很多条直线和圆，弄不好就是计算几何（不能考），所以这一条不会成为主要难点。

同余方程和乘法逆元

其实考纲说的是模意义下的逆元，所以加法逆元也能考，但是这太无聊了。

$ax+by=c$ 或者说 $ax\equiv c\pmod b$ 几乎是 S 组数论的主场。

求解这个方程有如下几种方法：

• exgcd 是通用的方法，然而需要一定的记忆。虽然好久没考了，但是万一死灰复燃了呢（笑）
• 费马小定理只有在模数为质数时成立，然而大部分题目模数都是质数，很少有出题人冒着“乘法逆元不存在”的风险出非质数模数自找麻烦。因此费马小定理是最常用的乘法逆元求法。

关于同余的定理

前置知识：$\varphi(x)$ 表示不超过 $x$ 的数中和 $x$ 互质的数字个数，可以通过如下结论计算：

• 当 $p$ 为质数时 $\varphi(p^n)=(p-1)p^{n-1}$。
• 当 $a,b$ 互质时 $\varphi(ab)=\varphi(a)\varphi(b)$。（称为“积性函数”）

只要是积性函数，就可以在线性筛时顺带求出来。

---

欧拉定理是费马小定理的推论：$a^{\varphi(m)}\equiv 1\pmod m$，当 $a,m$ 互质。

威尔逊定理：若 $p$ 为质数，则 $(p-1)!\bmod p=p-1$。

裴蜀定理：若 $a,b,x,y$ 都是整数，则 $ax+by$ 一定是 $\gcd(x,y)$ 的倍数。（可以推广到 $n$ 个数的情形，只要使用数学归纳法即可）

中国剩余定理（CRT）：求解同余方程组的算法。

计数

这个“等价类”放在这里很迷。我现在在大学里上代数与分析基础，不是很懂这东西怎么放进 OI 试题里。

圆排列、多重集上的排列组合只要把重复的方案除掉即可，可能需要借助乘法逆元。

鸽巢原理可以用于辅助证明一些结论，比如说“有多少个 $m$ 使得存在 $x$ 使得 xxx 成立”，如果你可以通过鸽巢原理得到“只要 $m\le$ 某个数就必然存在 $x$”。

如何在没有生成函数的情况下出二项式定理，我不知道。

容斥原理的难度上限很高，值得注意，例如 ZJOI2016 的小星星、ZJOI2022 的树都是容斥，哪怕眼光只在 CSP 范围内，Emiya 家的饭也是很不错的一个容斥 + DP 的经典组合。

卡特兰数可以参考一下 SCOI2010 生成字符串，里面有很详细、更一般的推导过程，比单纯结论可能会好记一些。

线性代数

矩阵的加减法都非常自然，乘法可以根据式子 $(AB)_{i,j}=\sum\limits_k A_{i,k}B_{k,j}$ 记，也可以根据“矩阵是向量的拼接”来记忆。然后乘法最重要的性质就是乘法有结合律无交换律，用于快速幂。

矩阵另一个重要的应用是高斯消元。高斯消元时碰到零元时要先把非零元换到当前位置再消元，同时请考虑清楚如何区分无解和有无数组解。

高斯消元的另一个体现形式是位运算版本，在云斗 10 月 Golden Round 第 3 题有涉及到。线性基也是高斯消元的经典应用，相比于高斯消元码量小很多。