CSP初赛知识整理

zzx6 · 2026-09-18 19:53:45 · 算法·理论

本篇文章由 @zzx6 编写，部分内容摘自 oiwiki，部分内容由 AI 优化，感谢 @susieli 对本篇文章的大力贡献！

竞赛历史

操作系统

‌Windows‌（闭源）、macOS‌（核心闭源，部分开源）、Linux（Ubuntu、Debian、Fedora 等）‌（完全开源）、ChromeOS‌（闭源）、Android‌（开源）、iOS / iPadOS‌（闭源）、鸿蒙系列‌（完全开源）

Linux 操作

算法

• 算法是指为解决问题而采取的方法与步骤

排序

图论

二叉树遍历

前序遍历（中、左、右）\ 中序遍历（左、中、右）\ 前序遍历（左、右、中）

经典题型 1：\ 已知二叉树的前序遍历为 ABDECFG，中序遍历为 DBEAFCG，请问该二叉树的后序遍历结果是？(来源：CSP 2024 入门级第一轮第 12 题)

第 1 步：A 为根 ({\color{Red}A}BDECFG,\ DBE{\color{Red}A}FCG)

第 2 步：B 为 A 的左儿子 (A{\color{Red}B}DECFG,\ D{\color{Red}B}EAFCG)

第 3 步：D 为 B 的左儿子 (AB{\color{Red}D}ECFG,\ {\color{Red}D}BEAFCG)

第 4 步：E 为 B 的右儿子 (ABD{\color{Red}E}CFG,\ DB{\color{Red}E}AFCG)

第 5 步：C 为 A 的右儿子 (BDEA{\color{Red}C}FG,\ DBEAF{\color{Red}C}G)

第 6 步：F 为 C 的左儿子 (BDECA{\color{Red}F}G,\ DBEA{\color{Red}F}CG)

第 7 步：G 为 C 的右儿子 (BDECFA{\color{Red}G},\ DBEAFC{\color{Red}G})

联通性

若一张有向图的节点两两互相可达，则称这张图是强连通的 (strongly connected)。\ 若一张有向图的边替换为无向边后可以得到一张连通图，则称原来这张有向图是弱连通的 (weakly connected)。

如果从一个连通图中删去一个点后图不连通，那这个点就是一个割点 (cut vertex)。没有割点的连通图是点双连通的 (biconnected)。\ 如果从一个连通图中删去一条变后图不连通，那这条边就是一个桥 (bridge)。没有桥的连通图是边双连通的 (2-edge-connected)。

常见图

竞赛图

每对顶点之间都恰有一条边相连的有向图称为竞赛图

欧拉图

欧拉路径（Eulerian path）是经过图中每条边恰好一次的路径。\ 欧拉回路（Eulerian circuit）是经过图中每条边恰好一次的回路。\ 如果一个图中存在欧拉回路，则这个图被称为欧拉图（Eulerian graph）。\ 如果一个图中不存在欧拉回路但是存在欧拉路径，则这个图被称为半欧拉图（semi-Eulerian graph）。

哈密顿图

通过图中所有顶点一次且仅一次的通路称为哈密顿通路。\ 通过图中所有顶点一次且仅一次的回路称为哈密顿回路。\ 具有哈密顿回路的图称为哈密顿图。\ 具有哈密顿通路而不具有哈密顿回路的图称为半哈密顿图。

编码

哈夫曼编码

设二叉树具有 n 个带权叶结点，从根结点到各叶结点的路径长度与相应叶节点权值的乘积之和称为树的带权路径长度（Weighted Path Length of Tree，WPL）。对于给定一组具有确定权值的叶结点，可以构造出不同的二叉树，其中，WPL 最小的二叉树 称为哈夫曼树（Huffman Tree，也称为霍夫曼树）。

哈夫曼树构造方式（摘自 oiwiki）：

1. 初始化：由给定的 n 个权值构造 n 棵只有一个根节点的二叉树，得到一个二叉树集合 F。
2. 选取与合并：从二叉树集合 F 中选取根节点权值最小的两棵二叉树分别作为左右子树构造一棵新的二叉树，这棵新二叉树的根节点的权值为其左、右子树根结点的权值和。
3. 删除与加入：从 F 中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到 F 中。
4. 重复 2、3 步，当集合中只剩下一棵二叉树时，这棵二叉树就是哈夫曼树。

设霍哈夫曼树的左分支代表 0，右分支代表 1，则从根结点到每个叶结点所经过的路径组成的 0、1 序列即为该叶结点对应字符的哈夫曼编码（Huffman Code，也称为霍夫曼编码）。

格雷码

格雷码是一个二进制数字系统，其中两个相邻数的二进制位只有一位不同。\

格雷码构造方式（摘自 oiwiki）：

1. 翻转最低位得到下一个格雷码，（例如 000\to 001）。
2. 把最右边的 1 的左边的位翻转得到下一个格雷码，（例如 001\to 011）。
3. 交替按照上述策略生成 2^{k-1} 次，可得到 k 位的格雷码序列。

主定理

假设有递推关系式 T(n)=aT(\frac{n}{b})+f(n)

则可以对于 n^{log_ba} 和 f(n) 分为 3 种情形：

1. n^{log_ba} > f(n)：T(n)=\Theta (n^{log_ba})
2. n^{log_ba} < f(n)：T(n)=\Theta (f(n))
3. n^{log_ba} = f(n)：T(n)=\Theta (n^{log_ba}logn)=\Theta (f(n) \log n)

口诀：较大取大，相等乘 \log

数学相关

进制

位运算

优先级：! > \&{} > \^{} > | > \&\& > ||

\_\_builtin 系列：

• 注意：上述函数范围均为 unsigned\ int 范围内，若要在 unsigned\ long\ long 范围内使用，请用对应的 64 位版本，例如：\_\_builtin\_popcount(x) \to \_\_builtin\_popcountll(x)。

卡特兰数 (Catalan 数)

通项公式：

1. C_n=\frac{\binom{2n}{n}}{n+1}
2. C_n=\binom{2n}{n}-\binom{2n}{n-1}

递推公式：

1. C_0=1,C_n=\sum_{i=0}^{n-1}C_iC_{n-1-i}
2. C_n=\frac{4n-2}{n+1}C_{n-1}

数列前几项：1, 1, 2, 5, 14, 42, 132, 429,...

应用场景：路径计数、多边形三角剖分计数、二叉树计数、括号序列计数、出栈序列计数等。

斯特林数（Stirling 数）

第二类斯特林数‌：表示将 n 个两两不同的元素，划分为 k 个互不区分的非空子集的方案数\ 最常用应用：求将 n 个不同小球放进 k 个相同盒子中的方案数为 S(n,k)

递推式：S(n,k)=S(n-1,k-1)+k\cdot S(n-1,k)

组合意义：

1. 将新元素单独放入一个子集，有 S(n-1,k-1) 种方案
2. 将新元素放入一个现有的子集，有 k\cdot S(n-1,k) 种方案

第一类斯特林数‌：表示将 n 个两两不同的元素，划分为 k 个互不区分的非空轮换的方案数\ 注：一个轮换就是一个首尾相接的环形排列，我们认为 [A,B,C]=[B,C,A]=[C,A,B]，即，两个可以通过旋转而互相得到的轮换是等价的

递推式：s(n,k)=s(n-1,k-1)+(n-1)\cdot s(n-1,k)

组合意义：

1. 将新元素单独放入一个轮换，有 S(n-1,k-1) 种方案
2. 将新元素放入一个现有的轮换，有 (n-1)\cdot S(n-1,k) 种方案\ （ps: 讲人话就是前 n-1 个元素选一个并将新元素放到它后面）

贝尔数

定义：含有 n 个元素的集合的划分方案数。

递推式：B_{n+1}=\sum_{k=0}^n\binom{n}{k}B_{k}

数列前几项：1,2,5,15,52,203,...

错位排列

定义：没有任何元素出现在其有序位置的排列。即对于 1\sim n 的排列 P，如果对于所有 i 均满足 P_i\neq i，则称 P 是 n 的错位排列。

递推式：

1. D_n=(n-1)(D_{n-1}+D_{n-2})
2. D_n=nD_{n-1}+(-1)^n

数列前几项：0,1,2,9,44,265,...