# GESP 八级编程能力认证讲义

## 第一模块：组合数学与杨辉三角

### 1. 知识点拆解
*   **加法与乘法原理**：分类用加法，分步用乘法。
*   **排列与组合**：
    *   排列 $P(n, k) = \frac{n!}{(n-k)!}$：考虑顺序。
    *   组合 $C(n, k) = \frac{n!}{k!(n-k)!}$：不考虑顺序。
*   **杨辉三角 (Pascal's Triangle)**：
    *   第 $n$ 行第 $k$ 个数（从 0 开始）对应 $C(n, k)$。
    *   递推公式：$C(n, k) = C(n-1, k-1) + C(n-1, k)$。这是处理大组合数取模的基础。

### 2. 具体例子
**例子 1.1**：有 5 个学生，选 3 个去参加比赛，有多少种选法？
这是不考虑顺序的组合：$C(5, 3) = \frac{5 \times 4 \times 3}{3 \times 2 \times 1} = 10$ 种。

### 3. 练习巩固
1.  **【简单】单选题**：在杨辉三角中，第 6 行（行号从 0 开始）的所有数字之和是（ ）。
    A. 32  B. 64  C. 128  D. 12
2.  **【中等】填空题**：从 6 名男生和 4 名女生中选出 3 人，要求至少有 1 名女生，共有 ______ 种不同的选法。
3.  **【困难】阅读程序填空**：利用杨辉三角递推求 $C(n, k) \pmod p$。
    ```cpp
    for(int i = 0; i <= n; i++) {
        c[i][0] = 1;
        for(int j = 1; j <= i; j++)
            c[i][j] = (c[i-1][j-1] + __________) % p;
    }
    ```

---

## 第二模块：倍增法 (Binary Lifting)

### 1. 知识点拆解
*   **核心思想**：利用 $2$ 的幂次（$2^0, 2^1, 2^2 \dots$）将 $O(n)$ 的线性跳跃优化为 $O(\log n)$。
*   **经典应用**：
    1.  **ST 表 (Sparse Table)**：解决区间最值查询 (RMQ)，预处理 $O(n \log n)$，查询 $O(1)$。
    2.  **最近公共祖先 (LCA)**：通过倍增向上跳转，快速寻找两个节点的公共祖先。
    3.  **快速幂**：计算 $a^b \pmod p$。

### 2. 具体例子
**例子 2.1**：快速幂计算 $3^{13}$。
$13$ 的二进制是 $1101$。
$3^{13} = 3^8 \times 3^4 \times 3^1$。通过不断平方即可快速求得。

### 3. 练习巩固
1.  **【简单】对错题**：倍增法可以将某些时间复杂度为 $O(N)$ 的问题优化到 $O(\log N)$。（ ）
2.  **【中等】单选题**：在求 LCA 的倍增算法中，若 `fa[i][j]` 表示节点 `i` 的第 $2^j$ 级祖先，则 `fa[i][j]` 等于（ ）。
    A. `fa[fa[i][j-1]][j-1]`  B. `fa[fa[i][j-1]][j]`  C. `fa[i][j-1] + fa[i][j-1]`  D. `fa[i][j-1] * 2`
3.  **【困难】填空题**：ST 表预处理 `f[i][j]`（表示从 `i` 开始长度为 $2^j$ 的区间最值）的递推式为：`f[i][j] = max(f[i][j-1], __________)`。

---

## 第三模块：图论综合应用（MST 与 SSSP）

### 1. 知识点拆解
*   **最小生成树 (MST)**：
    *   **Kruskal 算法**：贪心边，配合并查集，适合稀疏图 $O(E \log E)$。
    *   **Prim 算法**：贪心点，适合稠密图。
*   **单源最短路 (SSSP)**：
    *   **Dijkstra 算法**：贪心+优先队列，不能处理负权边，$O(E \log V)$。
    *   **Bellman-Ford / SPFA**：可以处理负权边。
*   **综合应用**：如何建图（如差分约束、虚拟源点）。

### 2. 具体例子
**例子 3.1**：Dijkstra 为什么要用优先队列？
为了每次都能快速找到当前“距离起点最近且未访问”的点，避免 $O(V)$ 的遍历，将效率提升至对数级别。

### 3. 练习巩固
1.  **【简单】对错题**：Kruskal 算法在运行过程中，如果发现当前边连接的两个顶点已经在同一个集合中，则应舍弃该边以防成环。（ ）
2.  **【中等】单选题**：在一个有 $V$ 个顶点、$E$ 条边的带权图中，使用 Dijkstra 算法（配合优先队列优化）求单源最短路，其时间复杂度为（ ）。
    A. $O(V^2)$  B. $O(V+E)$  C. $O(E \log V)$  D. $O(E \log E)$
3.  **【困难】阅读程序写结果**：已知图的边为：`(1,2,5), (2,3,3), (1,3,10)`。从 1 号点出发，Dijkstra 跑完后到 3 号点的最短距离是 ______。

---

## 第四模块：算法分析与优化进阶

### 1. 知识点拆解
*   **代数与平面几何**：
    *   **点积/叉积**：判断向量位置关系。
    *   **距离公式**：欧几里得距离与曼哈顿距离。
*   **复杂度深度分析**：
    *   能够识别主定理（Master Theorem）下的分治复杂度。
    *   区分平均复杂度和最坏复杂度。
*   **优化技巧**：
    *   **常量优化**：位运算代替乘除，读入优化（Fast I/O）。
    *   **空间优化**：位图（Bitset）、内存复用。

### 2. 具体例子
**例子 4.1**：判断三点 $A, B, C$ 是否共线。
利用叉积：若 $\vec{AB} \times \vec{AC} = 0$，则三点共线。

### 3. 练习巩固
1.  **【简单】单选题**：下列哪种操作通常不能显著提升 C++ 程序的运行速度？
    A. 使用 `scanf` 代替 `cin`  B. 开启 `inline` 函数  C. 将 `long long` 全部改为 `int`  D. 增加注释数量
2.  **【中等】填空题**：计算两个 $N \times N$ 的矩阵乘法，最朴素的算法时间复杂度是 ______。
3.  **【困难】分析程序**：
    ```cpp
    void merge_sort(int l, int r) {
        if(l >= r) return;
        int mid = (l + r) / 2;
        merge_sort(l, mid);
        merge_sort(mid + 1, r);
        merge(l, mid, r); // 合并复杂度为 O(n)
    }
    ```
    该算法的时间复杂度递归式为 $T(n) = 2T(n/2) + O(n)$，根据主定理推导其复杂度为 ______。

---

## 教练参考答案与解析

### 第一模块
1.  **B**。第 $n$ 行数字之和为 $2^n$，$2^6 = 64$。
2.  **100**。总选法 $C(10, 3) = 120$。全男选法 $C(6, 3) = 20$。$120 - 20 = 100$。
3.  **c[i-1][j]**。

### 第二模块
1.  **对**。
2.  **A**。跳 $2^j$ 步等于先跳 $2^{j-1}$ 步，再跳 $2^{j-1}$ 步。
3.  **f[i + (1 << (j-1))][j-1]**。

### 第三模块
1.  **对**。
2.  **C**。
3.  **8**。路径 $1 \to 2 \to 3$ 距离为 $5+3=8$，比 $1 \to 3$ 的 $10$ 更短。

### 第四模块
1.  **D**。注释不参与编译，对速度无影响。
2.  **$O(N^3)$**。
3.  **$O(N \log N)$**。

---
**教练寄语**：
恭喜你走到这里！八级不仅仅是荣誉，更是你实力的证明。在八级的题目中，**“暴力”通常只能拿到 30% 的分，剩下的 70% 属于懂得优化、懂得数学规律的人**。
记住：真正的 OI 大师，不仅能写出复杂的代码，更能用最简单的逻辑（如倍增、组合数）去化解复杂的时空矛盾。保持思考，我们在更高水平的赛场见！加油！

GESP 八级编程能力认证讲义

第一模块：组合数学与杨辉三角

1. 知识点拆解

加法与乘法原理：分类用加法，分步用乘法。
排列与组合：
- 排列 $P(n, k) = \frac{n!}{(n-k)!}$：考虑顺序。
- 组合 $C(n, k) = \frac{n!}{k!(n-k)!}$：不考虑顺序。
杨辉三角 (Pascal's Triangle)：
- 第 $n$ 行第 $k$ 个数（从 0 开始）对应 $C(n, k)$。
- 递推公式：$C(n, k) = C(n-1, k-1) + C(n-1, k)$。这是处理大组合数取模的基础。

2. 具体例子

例子 1.1：有 5 个学生，选 3 个去参加比赛，有多少种选法？这是不考虑顺序的组合：$C(5, 3) = \frac{5 \times 4 \times 3}{3 \times 2 \times 1} = 10$ 种。

3. 练习巩固

【简单】单选题：在杨辉三角中，第 6 行（行号从 0 开始）的所有数字之和是（）。 A. 32 B. 64 C. 128 D. 12
【中等】填空题：从 6 名男生和 4 名女生中选出 3 人，要求至少有 1 名女生，共有 ______ 种不同的选法。
【困难】阅读程序填空：利用杨辉三角递推求 $C(n, k) \pmod p$。 cpp for(int i = 0; i <= n; i++) { c[i][0] = 1; for(int j = 1; j <= i; j++) c[i][j] = (c[i-1][j-1] + __________) % p; }

第二模块：倍增法 (Binary Lifting)

1. 知识点拆解

核心思想：利用 $2$ 的幂次（$2^0, 2^1, 2^2 \dots$）将 $O(n)$ 的线性跳跃优化为 $O(\log n)$。
经典应用：
1. ST 表 (Sparse Table)：解决区间最值查询 (RMQ)，预处理 $O(n \log n)$，查询 $O(1)$。
2. 最近公共祖先 (LCA)：通过倍增向上跳转，快速寻找两个节点的公共祖先。
3. 快速幂：计算 $a^b \pmod p$。

2. 具体例子

例子 2.1：快速幂计算 $3^{13}$。 $13$ 的二进制是 $1101$。 $3^{13} = 3^8 \times 3^4 \times 3^1$。通过不断平方即可快速求得。

3. 练习巩固

【简单】对错题：倍增法可以将某些时间复杂度为 $O(N)$ 的问题优化到 $O(\log N)$。（）
【中等】单选题：在求 LCA 的倍增算法中，若 fa[i][j] 表示节点 i 的第 $2^j$ 级祖先，则 fa[i][j] 等于（）。 A. fa[fa[i][j-1]][j-1] B. fa[fa[i][j-1]][j] C. fa[i][j-1] + fa[i][j-1] D. fa[i][j-1] * 2
【困难】填空题：ST 表预处理 f[i][j]（表示从 i 开始长度为 $2^j$ 的区间最值）的递推式为：f[i][j] = max(f[i][j-1], __________)。

第三模块：图论综合应用（MST 与 SSSP）

1. 知识点拆解

最小生成树 (MST)：
- Kruskal 算法：贪心边，配合并查集，适合稀疏图 $O(E \log E)$。
- Prim 算法：贪心点，适合稠密图。
单源最短路 (SSSP)：
- Dijkstra 算法：贪心+优先队列，不能处理负权边，$O(E \log V)$。
- Bellman-Ford / SPFA：可以处理负权边。
综合应用：如何建图（如差分约束、虚拟源点）。

2. 具体例子

例子 3.1：Dijkstra 为什么要用优先队列？为了每次都能快速找到当前“距离起点最近且未访问”的点，避免 $O(V)$ 的遍历，将效率提升至对数级别。

3. 练习巩固

【简单】对错题：Kruskal 算法在运行过程中，如果发现当前边连接的两个顶点已经在同一个集合中，则应舍弃该边以防成环。（）
【中等】单选题：在一个有 $V$ 个顶点、$E$ 条边的带权图中，使用 Dijkstra 算法（配合优先队列优化）求单源最短路，其时间复杂度为（）。 A. $O(V^2)$ B. $O(V+E)$ C. $O(E \log V)$ D. $O(E \log E)$
【困难】阅读程序写结果：已知图的边为：(1,2,5), (2,3,3), (1,3,10)。从 1 号点出发，Dijkstra 跑完后到 3 号点的最短距离是 ______。

第四模块：算法分析与优化进阶

1. 知识点拆解

代数与平面几何：
- 点积/叉积：判断向量位置关系。
- 距离公式：欧几里得距离与曼哈顿距离。
复杂度深度分析：
- 能够识别主定理（Master Theorem）下的分治复杂度。
- 区分平均复杂度和最坏复杂度。
优化技巧：
- 常量优化：位运算代替乘除，读入优化（Fast I/O）。
- 空间优化：位图（Bitset）、内存复用。

2. 具体例子

例子 4.1：判断三点 $A, B, C$ 是否共线。利用叉积：若 $\vec{AB} \times \vec{AC} = 0$，则三点共线。

3. 练习巩固

【简单】单选题：下列哪种操作通常不能显著提升 C++ 程序的运行速度？ A. 使用 scanf 代替 cin B. 开启 inline 函数 C. 将 long long 全部改为 int D. 增加注释数量
【中等】填空题：计算两个 $N \times N$ 的矩阵乘法，最朴素的算法时间复杂度是 ______。
【困难】分析程序： cpp void merge_sort(int l, int r) { if(l >= r) return; int mid = (l + r) / 2; merge_sort(l, mid); merge_sort(mid + 1, r); merge(l, mid, r); // 合并复杂度为 O(n) } 该算法的时间复杂度递归式为 $T(n) = 2T(n/2) + O(n)$，根据主定理推导其复杂度为 ______。

教练参考答案与解析

第一模块

B。第 $n$ 行数字之和为 $2^n$，$2^6 = 64$。
100。总选法 $C(10, 3) = 120$。全男选法 $C(6, 3) = 20$。$120 - 20 = 100$。
c[i-1][j]。

第二模块

对。
A。跳 $2^j$ 步等于先跳 $2^{j-1}$ 步，再跳 $2^{j-1}$ 步。
f[i + (1 << (j-1))][j-1]。

第三模块

对。
C。
8。路径 $1 \to 2 \to 3$ 距离为 $5+3=8$，比 $1 \to 3$ 的 $10$ 更短。

第四模块

D。注释不参与编译，对速度无影响。
$O(N^3)$。
$O(N \log N)$。

教练寄语：恭喜你走到这里！八级不仅仅是荣誉，更是你实力的证明。在八级的题目中，“暴力”通常只能拿到 30% 的分，剩下的 70% 属于懂得优化、懂得数学规律的人。记住：真正的 OI 大师，不仅能写出复杂的代码，更能用最简单的逻辑（如倍增、组合数）去化解复杂的时空矛盾。保持思考，我们在更高水平的赛场见！加油！

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com