第1章 GESP 八级考点总览

---

🎯 本章学习目标

通过本章的学习，你将能够：

1. 建立全局视野：清晰了解 GESP 八级考试的 8 大知识模块及其重要程度
2. 掌握计数原理：熟练运用加法原理和乘法原理解决计数问题
3. 理解排列组合：掌握排列数和组合数的计算与应用
4. 掌握杨辉三角：理解杨辉三角的递推关系和组合数意义
5. 理解倍增思想：掌握快速幂等倍增算法，理解二进制优化
6. 掌握图论进阶：理解最小生成树（Kruskal/Prim）和最短路径（Dijkstra/Floyd）
7. 精通复杂度分析：能分析各类算法的时间和空间复杂度
8. 理解算法优化：掌握数学公式化简、预处理、倍增等优化方法
9. 识别考点频率：知道各模块的出题频率和常见题型
10. 制定备考策略：根据自身情况合理安排复习计划

---

🗺️ 本章知识图谱

GESP 八级知识体系
├── 组合数学线
│   ├── 计数原理
│   │   ├── 加法原理（分类计数）
│   │   └── 乘法原理（分步计数）
│   ├── 排列与组合
│   │   ├── 排列 A(n,m) = n!/(n-m)!（有序）
│   │   └── 组合 C(n,m) = n!/(m!(n-m)!)（无序）
│   ├── 杨辉三角
│   │   ├── 递推：C(i,j)=C(i-1,j-1)+C(i-1,j)
│   │   ├── 边界：C(i,0)=C(i,i)=1
│   │   └── 第i行第j列 = C(i,j)
│   └── 倍增法
│       ├── 核心：二进制拼接
│       ├── 快速幂（O(log n)）
│       ├── LCA 最近公共祖先
│       └── RMQ 区间最值查询
├── 算法进阶线
│   ├── 图论算法
│   │   ├── 最小生成树
│   │   │   ├── Kruskal（边排序+并查集）
│   │   │   └── Prim（贪心加点）
│   │   └── 最短路径
│   │       ├── Dijkstra（单源，非负权）
│   │       └── Floyd（全源，O(n³)）
│   ├── 复杂度分析
│   │   ├── 大O表示法
│   │   ├── 时间复杂度分析
│   │   ├── 空间复杂度分析
│   │   └── 常见算法复杂度表
│   └── 算法优化
│       ├── 数学公式化简
│       ├── 预处理/查表
│       ├── 倍增优化
│       ├── 空间换时间
│       └── 数据结构升级
└── 数学工具
    └── 代数与平面几何
        ├── 一元/二元一次方程
        ├── 三角形/圆/长方形面积
        └── 浮点数比较（eps）

---

一、🎯 写在前面：为什么要考八级？

CCF GESP（Grade Examination of Software Programming，编程能力等级认证）由中国计算机学会主办，C++ 方向设 1～8 级（本书仅面向 C++）。官方对八级的定位是：

掌握组合数学中基本知识，通过算法的时间和空间效率分析，可以完成相对应的算法优化。

这句话信息量很大——它意味着八级不再考"你会不会写代码"，而是考"你会不会算得对、算得快、讲得清"：

• 算得对：组合计数不重不漏、图论算法正确实现；
• 算得快：用倍增、公式化简等手段把 O(n²) 优化到 O(n log n) 甚至 O(1)；
• 讲得清：能分析一个算法的时间、空间复杂度，并比较不同解法的优劣。

---

二、📊 八大知识块全景总表

根据 CCF GESP 官方考试大纲，八级知识内容可归纳为八大知识块。先上全景表，建立全局视野：

序号	知识块	一句话概括	主要考查形式	学习难度
①	计数原理	加法原理（分类）、乘法原理（分步）——组合数学的地基	选择/判断 + 编程计数	⭐⭐
②	排列与组合	有序排列 A(n,m)、无序组合 C(n,m) 的公式与计算	选择/判断 + 编程	⭐⭐⭐
③	杨辉三角	杨辉三角的定义与递推实现，天然产出组合数	选择/判断 + 编程	⭐⭐
④	倍增法	"成倍跳跃"思想：快速幂、LCA、RMQ，O(n) → O(log n)	选择/判断 + 编程压轴	⭐⭐⭐⭐
⑤	代数与平面几何	一元/二元一次方程、三角形/圆/长方形面积（初中数学）	选择/判断为主	⭐⭐
⑥	图论算法及综合应用	最小生成树（Kruskal/Prim）、最短路（Dijkstra/Floyd）+ 综合求解	编程题主战场	⭐⭐⭐⭐⭐
⑦	时间与空间效率分析	大 O 表示法；排序/查找/遍历/搜索/分治/DP 的复杂度	选择/判断高频	⭐⭐⭐⭐
⑧	算法优化	不同算法差异分析、优化一般方法、用数学公式（等差/等比求和）优化	编程题 + 判断压轴	⭐⭐⭐⭐⭐

💡 这八块并非零散考点，而是可以串成两条主线（后文知识地图详述）：一条是"组合数学线"，一条是"算法进阶线"，最后在"复杂度分析与优化"处汇合。

---

三、🔍 八大知识块逐块导览

① 计数原理：加法原理与乘法原理

📖 考纲要求：掌握加法原理、乘法原理，能将复杂计数问题分解为独立事件。

• 加法原理（分类计数）：完成一件事有 n 类办法，每类分别有 m₁, m₂, …, mₙ 种方法，则总方法数为 m₁ + m₂ + … + mₙ。关键词："要么……要么……"，类与类之间互斥。
• 乘法原理（分步计数）：完成一件事分 n 个步骤，每步分别有 m₁, m₂, …, mₙ 种方法，则总方法数为 m₁ × m₂ × … × mₙ。关键词："先……再……"，步与步之间独立。

🎯 在八级中的地位：组合数学线的第一块基石，排列组合、杨辉三角本质上都是两个原理的反复应用。

📝 考查形式：选择题给情景问方案数；编程题中作为计数类 DP 的背景（如路径数、染色方案数）。

⚠️ 易错点：分类时类与类不能重叠（重叠要减回去，这就是后面要学的容斥思想）；分步时步与步要真正独立。"从北京到上海有 3 班飞机、2 班高铁"用加法（3+2=5），"从北京经上海到广州，北京→上海 5 种走法、上海→广州 4 种走法"用乘法（5×4=20）。

---

② 排列与组合

📖 考纲要求：理解排列、组合的概念，掌握排列数 A(n,m) 与组合数 C(n,m) 的计算。

概念	含义	公式
排列 A(n,m)	从 n 个不同元素中有序取 m 个	A(n,m) = n!/(n−m)! = n×(n−1)×…×(n−m+1)
组合 C(n,m)	从 n 个不同元素中无序取 m 个	C(n,m) = n!/(m!(n−m)!) = A(n,m)/m!
八级编程题中组合数通常需要对大质数取模，需要预处理阶乘和阶乘逆元（费马小定理求逆元），直接算阶乘会溢出。

🎯 地位：组合计数的核心工具，也是杨辉三角、二项式定理的入口。

📝 考查形式：选择/判断直接考公式计算与"有序还是无序"的辨析；编程题考组合数的递推预处理、模意义下计数。

🔥 高频考点："排队拍照有多少种站法"是排列（A(n,n)=n!），"从 10 人中选 3 人参赛"是组合（C(10,3)=120）。判断顺序是否影响结果，是排列与组合的分水岭。

---

③ 杨辉三角

📖 考纲要求：掌握杨辉三角的定义，能编程实现杨辉三角形。

杨辉三角第 i 行第 j 个数（行、列均从 0 开始）满足：

• 边界：C(i, 0) = C(i, i) = 1
• 递推：C(i, j) = C(i−1, j−1) + C(i−1, j)

它的每一行正是二项式 (a+b)ⁿ 展开式的系数，也是组合数的"工厂"。 当 n 较大时，组合数会迅速超出 long long 的范围（C(60,30) 就已经接近 10¹⁷），八级编程题中通常要求对某个模数取模。

🎯 地位：递推（动态规划）思想与组合数学的交汇点，编程题常要求输出三角形或用它预处理组合数。

📝 考查形式：编程题打印杨辉三角；选择题考"第 n 行第 k 个数是 C(n,k)"这一对应关系。

---

④ 倍增法

📖 考纲要求：掌握倍增的概念，了解倍增法的时间复杂度。

倍增（Binary Lifting） 的核心：任何正整数都能表示成若干个 2 的幂之和（二进制）。因此我们不必"一步一步走"，而是预处理出 1, 2, 4, 8, … 步的信息，需要时像拼二进制一样拼出答案，把 O(n) 的过程降到 O(log n)。

三大经典应用：快速幂、LCA（最近公共祖先）、RMQ（区间最值查询）。

先上一道"开胃菜"——快速幂（计算 aᵇ mod p）：

// C++11 快速幂：倍增思想，O(log b)
long long qpow(long long a, long long b, long long mod) {
    long long res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;  // b 的当前二进制位为 1，乘上 a^(2^k)
        a = a * a % mod;                 // a 平方：a^(2^k) → a^(2^(k+1))
        b >>= 1;  //必须在判断完当前位之后执行，顺序不能颠倒
                  //先看最低位是不是1，再平方，最后把最低位移走。
    }
    return res;
}

🔥 高频考点：倍增法把指数/步数从"线性累积"变成"二进制拼接"，时间复杂度 O(log n)。判断题常考"倍增预处理后单次查询的复杂度"——记住预处理 O(n log n)、单次查询 O(log n)（RMQ 的 ST 表可做到 O(1) 查询）。

🎯 地位与难度：八级最具"竞赛味"的思想之一，概念抽象但代码短小，是编程题压轴与选择题的双重热点，难度 ⭐⭐⭐⭐。

---

⑤ 代数与平面几何（初中数学部分）

📖 考纲要求：一元一次方程、二元一次方程（组）的求解；三角形、圆形、长方形的面积计算。

内容	核心公式/方法
一元一次方程	ax + b = 0 → x = −b/a（注意 a = 0 的特判）
二元一次方程组	代入消元法 / 加减消元法
长方形面积	S = 长 × 宽
三角形面积	S = 底 × 高 ÷ 2；海伦公式 S = √(p(p−a)(p−b)(p−c))
圆面积	S = πr²

🎯 地位：难度不高，但几何题是编程题的常见背景板——很多图论/计算题最后一步都落在"算个面积、解个方程"上。

⚠️ 易错点：① 浮点数比较不能直接用 ==，要判断差值是否小于 eps（如 1e-9）；② 圆面积用 π 时建议用 acos(-1.0)获取高精度 π，别手写 3.14；③ 解方程组前先判断是否有唯一解。

---

⑥ 图论算法及综合应用

📖 考纲要求：掌握最小生成树的概念、Kruskal 算法、Prim 算法；掌握最短路径的概念、Dijkstra 算法、Floyd 算法；理解实现同一功能的不同算法之间的比较，能灵活解决相关综合问题。

问题	算法	核心思想	时间复杂度	适用场景
最小生成树	Kruskal	边排序 + 并查集，贪心加边不构成环	O(m log m)	稀疏图
最小生成树	Prim	从顶点出发，每次加入离集合最近的点	O(n²) / 堆优化 O(m log n)	稠密图
单源最短路	Dijkstra	贪心 + 松弛，每次确定最近点	O(n²) / 堆优化 O(m log n)	非负权图
全源最短路	Floyd	动态规划，枚举中转点 k	O(n³)	n 很小、求所有点对距离

感受一下 Floyd 的极简实现：

// C++11 Floyd：求任意两点间最短路，O(n^3)
for (int k = 1; k <= n; k++)        // 中转点必须在最外层！
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (dist[i][k] + dist[k][j] < dist[i][j])
                dist[i][j] = dist[i][k] + dist[k][j];

⚠️ 易错点： Floyd 三重循环中中转点 k 必须在最外层，写在内层结果必错； k 必须在最外层，是因为 Floyd 本质是动态规划：第 k 轮迭代只允许经过前 k 个节点中转，每一轮都建立在前一轮的基础上。

Dijkstra 不能处理负权边（有负权要用 Bellman-Ford/SPFA，但八级考纲不要求）；邻接矩阵初始化为无穷大时，dist[i][i] = 0 别忘。 通常取 const int INF = 0x3f3f3f3f;（约 10⁹，两个 INF 相加不会溢出 int）

🎯 地位：八级编程题的绝对主战场，分值密度最高，难度 ⭐⭐⭐⭐⭐。

---

⑦ 算法的时间和空间效率分析

📖 考纲要求：掌握时间、空间复杂度的一般分析方法；能分析排序、查找、树和图的遍历、搜索、分治、动态规划等各类算法的复杂度。

必会"复杂度常识表"：

大 O 表示法：f(n) = O(g(n)) 表示存在正常数 c 和 n₀，使得当 n ≥ n₀ 时，f(n) ≤ c · g(n)。即 g(n) 是 f(n) 的渐进上界。例如 3n² + 2n + 1 = O(n²)，因为当 n 足够大时，n² 项占主导。

算法类别	典型算法	时间复杂度
排序	冒泡/选择/插入排序	O(n²)
排序	快速/归并排序	O(n log n)
查找	顺序查找 / 二分查找	O(n) / O(log n)
树/图遍历	DFS / BFS	O(n+m)（图）
搜索	暴力枚举/回溯	指数级 O(2ⁿ) 等
分治	归并排序式递归	O(n log n)
动态规划	一维 / 二维状态 DP	O(n) / O(n²) 视状态数与转移数而定
图论	Floyd / Dijkstra（堆优化）	O(n³) / O(m log n)

🔥 高频考点：选择题常给一段嵌套循环让你判断复杂度。口诀："几层循环看嵌套，递归算法看递推式"——比如 T(n) = 2T(n/2) + O(n) 对应 O(n log n)（主定理思想），T(n) = T(n−1) + O(n) 对应 O(n²)。

🎯 地位：这块本身不难，但它是贯穿全卷的暗线——编程题是否超时、优化题如何评价，全靠复杂度说话，难度 ⭐⭐⭐⭐。

---

⑧ 算法优化（第9章的主角）

📖 考纲要求：能分析不同算法求解同一问题的差异；掌握算法优化的一般方法；能根据数学知识优化算法（如等差数列、等比数列求和公式）。

常见优化武器库：

优化手段	典型例子	优化效果
数学公式化简	1+2+…+n 用 n(n+1)/2，循环累加 → 公式	O(n) → O(1)
预处理/查表	杨辉三角预处理组合数	每次 O(n) → O(1)
倍增	快速幂、LCA	O(n) → O(log n)
空间换时间	记忆化搜索、DP 数组	指数级 → 多项式级
数据结构升级	线性查找 → 哈希表/堆	O(n) → O(1)/O(log n)
算法替换	暴力最短路 → Dijkstra	O(n³) → O(m log n)

🔥 高频考点："求 1+2+…+n"这类题，写 for 循环能拿部分分，写 n*(n+1)//2 才是八级要求的满分姿势——这正是考纲点名的"根据等差/等比数列求和公式优化算法"。等比数列求和 S = a₁(qⁿ−1)/(q−1)（q≠1）也要记牢。q=1 时必须特判，否则公式中 q−1 为 0 会导致除零错误。

🎯 地位：八级知识目标的落脚点，难度 ⭐⭐⭐⭐⭐。它不单独是一个"章节"，而是前七块知识学完后的综合境界。

---

四、🧭 两张知识地图

八级八大块可以串成清晰的两条线：

🧮 组合数学线（第2～5期）：

计数原理（分类/分步） → 排列与组合（有序/无序） → 杨辉三角（组合数递推） → 倍增法（二进制跳跃）

这条线从"怎么数清楚"讲到"怎么数得快"，数学味浓，是选择/判断题的富矿。

⚙️ 算法进阶线（第6～9期）：

图论算法（MST + 最短路） → 复杂度分析（看得懂快慢） → 算法优化（想办法变快）

这条线从"会实现经典算法"讲到"会评价、会改进算法"，工程味浓，是编程题主战场。

而代数与平面几何（第6期）作为数学工具穿插其间，为两条线提供计算支撑。

---

五、📊 考点总表

模块	重要程度	出题形式	核心考点	易错点
计数原理	⭐⭐⭐⭐	选择/判断	加法原理、乘法原理	分类不重不漏，分步相互独立
排列与组合	⭐⭐⭐⭐⭐	选择/判断/编程	A(n,m)、C(n,m)公式	有序用排列，无序用组合
杨辉三角	⭐⭐⭐⭐	选择/编程	递推关系、组合数对应	行列从0开始，边界都是1
倍增法	⭐⭐⭐⭐⭐	选择/编程压轴	快速幂、二进制思想	O(log n)，b&1判断最低位
代数与平面几何	⭐⭐⭐	选择/判断	方程求解、面积公式	浮点数比较用eps
图论算法	⭐⭐⭐⭐⭐	编程题主战场	Kruskal、Prim、Dijkstra、Floyd	Floyd的k在最外层；Dijkstra不能负权
复杂度分析	⭐⭐⭐⭐⭐	选择/判断高频	大O表示法、各类算法复杂度	看嵌套层数，递归看递推式
算法优化	⭐⭐⭐⭐⭐	编程+判断压轴	数学公式、预处理、倍增	等差/等比求和公式

---

六、💡 备考建议

复习策略

1. 图论是重中之重：八级编程题主要考图论，Kruskal和Dijkstra必须闭卷能写
2. 组合数学要细心：排列组合的辨析题是选择判断常客，搞清楚"有序还是无序"
3. 倍增法要理解：快速幂是基础，理解二进制思想才能举一反三
4. 复杂度是必考题：几乎每张卷子都有复杂度分析题，把常见算法复杂度背下来
5. 算法优化看数学：等差等比求和公式是八级的"满分姿势"

时间规划

• 第1-2周：组合数学线（计数原理→排列组合→杨辉三角→倍增）
• 第3-4周：图论算法（最小生成树→最短路径）
• 第5周：复杂度分析 + 算法优化
• 第6周：综合模拟 + 查漏补缺

刷题建议

• 快速幂至少写 5 遍，做到肌肉记忆
• Kruskal 和 Dijkstra 各写 3 遍以上
• 杨辉三角递推和组合数计算要熟练
• 复杂度分析题多做，培养"看代码估复杂度"的直觉

---

七、📝 实战练习

练习题 1（单选题）

题目： 从甲地到乙地有 3 班火车、2 班汽车、4 班飞机。从甲地到乙地共有多少种不同的走法？（ ）

A. 9
B. 24
C. 3+2+4=9
D. 3×2×4=24

🔑 点击查看答案与解析

答案： A

解析： 从甲地到乙地，"要么坐火车，要么坐汽车，要么坐飞机"——这是分类，用加法原理。

总方法数 = 3 + 2 + 4 = 9

选 A（C 虽然答案对，但选项形式不标准，考试中选最标准的）。

💡 记忆口诀：分类用加法（要么...要么...），分步用乘法（先...再...）。

---

练习题 2（单选题）

题目： 从 5 个人中选出 3 个人排成一排照相，共有多少种不同的排法？（ ）

A. 10
B. 60
C. 120
D. 15

🔑 点击查看答案与解析

答案： B

解析： "排成一排照相"——顺序不同算不同的排法，所以是排列问题。

A(5,3) = 5 × 4 × 3 = 60

验证：

• 第1个位置：5种选择
• 第2个位置：4种选择（剩4人）
• 第3个位置：3种选择（剩3人）
• 5 × 4 × 3 = 60 ✓

选 B。

🔥 高频考点：判断是排列还是组合，关键看"顺序是否影响结果"。排队、拍照、排名——都是排列。

---

练习题 3（判断题）

题目： 杨辉三角第 5 行第 2 个数（行和列都从 0 开始数）等于 C(5,2) = 10。（ ）

🔑 点击查看答案与解析

答案： 正确 ✅

解析： 杨辉三角的重要性质：第 i 行第 j 列 = C(i, j)（组合数）。

第 5 行第 2 列 = C(5, 2) = 5! / (2! × 3!) = (5 × 4) / (2 × 1) = 20 / 2 = 10

验证杨辉三角前几行：

第0行:       1
第1行:      1 1
第2行:     1 2 1
第3行:    1 3 3 1
第4行:   1 4 6 4 1
第5行:  1 5 10 10 5 1

第 5 行第 2 个数确实是 10。

💡 杨辉三角 = 组合数表。这个对应关系一定要记牢！

---

练习题 4（单选题）

题目： 快速幂算法的时间复杂度是？（ ）

A. O(1)
B. O(log n)
C. O(n)
D. O(n²)

🔑 点击查看答案与解析

答案： B

解析： 快速幂（倍增法求幂）的核心思想：

• 把指数 b 拆成二进制（如 13 = 1101₂ = 8 + 4 + 1）
• 每次把底数平方（a → a² → a⁴ → a⁸...）
• 遇到二进制位为 1，就乘到结果里

因为 b 的二进制位数是 log₂b，所以循环次数是 O(log b)。

选 B。

🔥 高频考点：倍增法把 O(n) 优化到 O(log n)，这是八级的核心思想之一。

---

练习题 5（判断题）

题目： Floyd 算法求最短路径的三重循环中，中转点 k 必须放在最外层。（ ）

🔑 点击查看答案与解析

答案： 正确 ✅

解析： Floyd 算法的正确写法：

for (k = 1; k <= n; k++)       // 中转点在最外层
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

为什么 k 必须在最外层？因为 Floyd 本质是动态规划：

• dp[k][i][j] = 允许经过前 k 个点中转时，i 到 j 的最短距离
• 第 k 层依赖第 k-1 层的结果

如果 k 在内层，就会出现"用了还没算出来的结果"的问题。

🔥 高频考点：Floyd 的 k 在最外层是判断题和代码填空题的常客！

---

练习题 6（单选题）

题目： 下面这段代码的时间复杂度是？（ ）

for (int i = 1; i <= n; i *= 2) {
    for (int j = 1; j <= n; j++) {
        // ... O(1) 操作
    }
}

A. O(n)
B. O(n log n)
C. O(n²)
D. O(log n)

🔑 点击查看答案与解析

答案： B

解析：

• 外层循环：i 从 1 开始，每次乘 2，直到 > n。循环次数 = log₂n → O(log n)
• 内层循环：j 从 1 到 n，每次 +1。循环次数 = n → O(n)

总时间复杂度 = O(log n) × O(n) = O(n log n)

选 B。

💡 口诀：循环变量每次乘/除 2 → log n；每次加/减固定值 → n。

---

练习题 7（单选题）

题目： Kruskal 算法的核心思想和时间复杂度是？（ ）

A. 从顶点出发贪心加点；O(n²)
B. 边排序后用并查集加边；O(m log m)
C. 动态规划枚举中转点；O(n³)
D. 每次选离源点最近的点松弛；O(m log n)

🔑 点击查看答案与解析

答案： B

解析：

• Kruskal 算法：

  1. 把所有边按权值从小到大排序
  2. 依次尝试加入每条边，如果加入后不形成环就加
  3. 用并查集判断是否成环
  4. 时间复杂度：O(m log m)（主要是排序的时间）

• Prim 算法：从顶点出发，每次加离集合最近的点 → A 选项描述的是 Prim

• Floyd 算法：动态规划枚举中转点 → C 选项是 Floyd

• Dijkstra 算法：单源最短路径，每次选最近点松弛 → D 选项是 Dijkstra

选 B。

🍎 记忆：Kruskal = 边排序 + 并查集（管边不管点）；Prim = 加点 + 找最近（管点不管边）。

---

练习题 8（编程题）

题目： 求 1 + 2 + 3 + ... + n 的和，要求时间复杂度 O(1)。

输入：一个整数 n
输出：1 到 n 的和

样例输入：100
样例输出：5050

🔑 点击查看答案与解析

答案： 参考代码（数学公式 O(1) 解法）：

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    cout << n * (n + 1) / 2 << endl;
    return 0;
}

解析： 等差数列求和公式：S = n × (n + 1) / 2

这是八级"算法优化"的典型例子：

• 暴力 for 循环：O(n)
• 数学公式：O(1)

🔥 高频考点：等差/等比求和公式是算法优化的利器。八级考试中，凡是能套公式的就别写循环！

等差数列：S = n × (a₁ + aₙ) / 2 等比数列：S = a₁ × (qⁿ - 1) / (q - 1)，q ≠ 1

⚠️ 注意数据溢出：n 大的时候 n*(n+1) 可能超出 int 范围，要用 long long。

---

⭐ 必背速记卡

┌─────────────────────────────────────────────┐
│         GESP 八级 · 必背速记卡              │
├─────────────────────────────────────────────┤
│  1. 分类用加法，分步用乘法                   │
│  2. 排列有序：A(n,m)=n!/(n-m)!              │
│  3. 组合无序：C(n,m)=n!/(m!(n-m)!)          │
│  4. 杨辉三角第i行第j列 = C(i,j)             │
│  5. 杨辉三角递推：C(i,j)=C(i-1,j-1)+C(i-1,j)│
│  6. 倍增思想：二进制拼接，O(log n)          │
│  7. 快速幂：a^b mod p，O(log b)             │
│  8. Kruskal：边排序+并查集，O(m log m)      │
│  9. Prim：加点找最近，O(n²)或O(m log n)     │
│ 10. Dijkstra：单源最短路，不能负权           │
│ 11. Floyd：全源最短路，k在最外层，O(n³)     │
│ 12. 复杂度：循环看嵌套，递归看递推           │
│ 13. 等差求和：n*(n+1)/2，O(1)               │
│ 14. 等比求和：a1*(q^n-1)/(q-1)，q≠1         │
│ 15. 算法优化：数学公式是神器                 │
└─────────────────────────────────────────────┘

---