1. 八级新增知识框架

• 加法原理、乘法原理。
• 排列、组合。
• 杨辉三角与组合数。
• 倍增法。
• 一元一次方程、二元一次方程、基本平面几何面积。
• 最小生成树：Kruskal、Prim。
• 最短路径：Dijkstra、Floyd。
• 较复杂算法的时间/空间复杂度分析。
• 一般算法优化和利用数学知识优化。

2. 加法原理与乘法原理

原理	适用场景	公式直觉
加法原理	完成目标有若干互斥类别的方法	$n_1+n_2+\cdots+n_k$
乘法原理	完成目标必须经过若干连续步骤	$n_1n_2\cdots n_k$

口诀：分类相加，分步相乘。

3. 排列与组合

阶乘

$n!=1\times2\times\cdots\times n$，规定 $0!=1$。

排列数

从 $n$ 个不同元素中选 $m$ 个并考虑顺序：

$A_n^m=\frac{n!}{(n-m)!}$。

组合数

从 $n$ 个不同元素中选 $m$ 个，不考虑顺序：

$C_n^m=\frac{n!}{m!(n-m)!}$。

必背性质

• $C_n^0=C_n^n=1$。
• $C_n^m=C_n^{n-m}$。
• $C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}$。
• $\sum_{m=0}^{n}C_n^m=2^n$。

区分排列/组合的核心问题：交换选中元素的顺序，会不会产生一种新方案？

4. 杨辉三角

每行首尾为 1，中间每项等于左上与右上之和。

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

组合意义：第 $n$ 行（若从 0 行开始）第 $m$ 项对应 $C_n^m$。

二项式展开：

$(a+b)^n=\sum_{m=0}^{n}C_n^m a^{n-m}b^m$。

5. 倍增法

核心思想：预处理 $2^0,2^1,2^2,\ldots$ 级别的信息，使一次“大跳”拆成若干二进制跳跃。

若最大规模为 $n$，倍增层数通常只需 $O(\log n)$。

典型问题：

• 快速向上跳 $k$ 个祖先。
• LCA 最近公共祖先。
• 某些区间/路径上的快速跳转。

树上倍增父节点

$up[u][j]$ 表示 $u$ 的 $2^j$ 级祖先，则：

$up[u][j]=up[up[u][j-1]][j-1]$。

预处理常见时间 $O(n\log n)$，单次按二进制位跳转 $O(\log n)$。

6. 初中代数必背

一元一次方程

$ax+b=0$ 且 $a\ne0$：$x=-\frac{b}{a}$。

二元一次方程组

$\begin{cases}a_1x+b_1y=c_1\\a_2x+b_2y=c_2\end{cases}$

常用方法：代入消元、加减消元。

7. 平面几何面积

图形	面积公式
长方形	$S=ab$
正方形	$S=a^2$
三角形	$S=\frac12 ah$
平行四边形	$S=ah$
梯形	$S=\frac12(a+b)h$
圆	$S=\pi r^2$

【辅助补充】坐标平面三点面积可用叉积理解：

$S=\frac12|(x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1)|$。

8. 最小生成树 MST

定义

对连通无向带权图，选择 $V-1$ 条边连接全部顶点且无环，使总边权最小。

树的关键性质：$V$ 个顶点的树有 $V-1$ 条边。

9. Kruskal

思想：按边权从小到大枚举，若加入该边不会形成环，就选它。

通常配合并查集判断两个端点是否已连通。

步骤：

1. 所有边按权值升序排序。
2. 初始化并查集。
3. 依次看边 (u,v,w)：若 find(u)!=find(v)，合并并加入答案。
4. 选满 $V-1$ 条边结束。

复杂度主要来自排序：常见 $O(E\log E)$。

10. Prim

思想：从一个点集开始，每次选择连接“已选集合”和“未选集合”的最小边。

实现	常见时间复杂度
邻接矩阵朴素 Prim	$O(V^2)$
邻接表 + 优先队列	常见写作 $O(E\log V)$ 量级

Kruskal 更偏“选边”；Prim 更偏“扩点”。

11. Dijkstra 单源最短路

适用：边权非负的单源最短路。

松弛：若经过 u 到 v 更短，则：

$dist[v]=\min(dist[v],dist[u]+w(u,v))$。

优先队列版本骨架：

priority_queue<pair<long long,int>,
               vector<pair<long long,int>>,
               greater<pair<long long,int>>> pq;

dist[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d != dist[u]) continue;
    for (auto [v, w] : g[u]) {
        if (dist[v] > d + w) {
            dist[v] = d + w;
            pq.push({dist[v], v});
        }
    }
}

常见复杂度：$O((V+E)\log V)$ 或简写 $O(E\log V)$（连通/边数关系下）。

Dijkstra 不能直接用于含负边的普通最短路问题。

12. Floyd 全源最短路

状态：d[i][j] 表示当前允许某些中间点后，i 到 j 的最短距离。

核心转移：

$d[i][j]=\min(d[i][j],d[i][k]+d[k][j])$。

循环顺序：k 必须在最外层。

for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

时间 $O(V^3)$，空间 $O(V^2)$。

13. MST 与最短路区别

问题	目标
最小生成树	用最小总成本把所有点连起来
最短路径	求某两个点/某源到各点的最短路程

MST 中树上两点路径不一定是原图的最短路径。

14. 复杂度总表

好的，按照您的要求，去掉所有公式外的反引号 ，只保留 $...$` 内联数学环境。修改后的表格如下（同时修正了“最小公倍数”一行的显示问题，但该行不在此表格中，当前表格只处理原有的公式）：

算法/结构	时间复杂度（典型）	空间复杂度（典型）
顺序扫描	$O(n)$	$O(1)$
二分查找	$O(\log n)$
冒泡/插入/选择	$O(n^2)$
归并排序	$O(n\log n)$	$O(n)$
快速排序	平均 $O(n\log n)$，最坏 $O(n^2)$	递归栈与实现相关
链表查找	$O(n)$	—
DFS/BFS 邻接表	$O(V+E)$	$O(V)$ 量级
LCS	$O(nm)$	$O(nm)$，滚动可降
0/1 背包	$O(nW)$	可 $O(W)$
Kruskal	$O(E\log E)$	$O(V+E)$ 量级
Prim 朴素	$O(V^2)$	与存储方式相关
Dijkstra + 堆	$O((V+E)\log V)$	$O(V+E)$
Floyd	$O(V^3)$	$O(V^2)$
倍增预处理	$O(n\log n)$
倍增单次查询	$O(\log n)$	—

15. 算法优化常见方向

优化方向	典型变化
去掉重复计算	递归 → 记忆化/DP
利用单调性	线性枚举 → 二分
预处理	多次查询前先算表
换数据结构	线性查找 → 哈希/树结构
换图存储	稠密矩阵 ↔ 稀疏邻接表
空间压缩	二维 DP → 滚动数组
数学化简	循环求和 → 公式
分治/倍增	逐步处理 → 按倍数跳跃

等差数列

首项 $a_1$、末项 $a_n$、项数 $n$：

$S_n=\frac{n(a_1+a_n)}{2}$

若公差 $d$：

$a_n=a_1+(n-1)d$

等比数列【辅助补充】

公比 $q\ne1$：

$S_n=a_1\frac{1-q^n}{1-q}$

16. 八级必背易错点

1. 分类用加法原理，连续步骤用乘法原理。
2. 排列考虑顺序，组合不考虑顺序。
3. $0!=1$。
4. 杨辉三角与组合数递推本质相同。
5. Kruskal 需要避免成环；并查集是常用实现工具。
6. Dijkstra 要求边权非负。
7. Floyd 的 k 必须放最外层。
8. 最小生成树与最短路径不是同一个问题。
9. 复杂度必须结合具体实现，不能说“Dijkstra 永远 $O(V^2)$”或“Prim 永远某一个复杂度”。
10. 算法优化要先找瓶颈，再决定是换算法、换数据结构、预处理还是数学化简。

17. 八级背诵清单

• [ ] 加法/乘法原理。
• [ ] $A_n^m$、$C_n^m$、组合数递推与对称性。
• [ ] 杨辉三角。
• [ ] 倍增思想与 $O(n\log n)$ 预处理、$O(\log n)$ 查询。
• [ ] 基础方程与面积公式。
• [ ] Kruskal / Prim 的思想与复杂度。
• [ ] Dijkstra / Floyd 的适用条件、转移与复杂度。
• [ ] 全阶段复杂度总表和常见优化方向。