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

## 第一模块：数学库进阶与哈希表

### 1. 知识点拆解
*   **数学库 `<cmath>`**：
    *   `sin(x), cos(x)`：注意 $x$ 是**弧度**而非角度（$弧度 = 角度 \times \pi / 180$）。
    *   `log(x)`：默认是以 $e$ 为底的自然对数（$\ln$）；`log10(x)` 是以 10 为底。
    *   `exp(x)`：计算 $e^x$。
*   **哈希表 (Hash Table)**：
    *   **核心**：通过哈希函数将关键字映射到数组下标，实现 $O(1)$ 查找。
    *   **冲突处理**：拉链法（链表存储冲突元素）和开放地址法。
    *   **应用**：C++ 中的 `unordered_map` 和 `unordered_set`。

### 2. 具体例子
**例子 1.1**：计算 $\log_2 8$。
在 C++ 中没有 `log2` 之前（早期版本），常用换底公式：`log(8) / log(2)`。

**例子 1.2**：使用哈希快速统计频率。
```cpp
unordered_map<string, int> hash;
string word;
while(cin >> word) hash[word]++; // 极速统计单词出现次数
```

### 3. 练习巩固
1.  **【简单】单选题**：在 C++ 中，计算 $\sin(30^\circ)$ 正确的代码是（ ）。
    A. `sin(30)`  B. `sin(30 * M_PI / 180)`  C. `asin(30)`  D. `sin(30 * 180 / M_PI)`
2.  **【中等】对错题**：哈希表的查找效率在所有情况下都能保持 $O(1)$。（ ）
3.  **【困难】填空题**：若使用“除留余数法”构建哈希表，哈希函数为 $H(key) = key \% 11$。对于关键字序列 `{12, 23, 34}`，它们在哈希表中的下标分别是 ______、______、______。

---

## 第二模块：图的定义与存储

### 1. 知识点拆解
*   **图论概念**：顶点（Vertex）、边（Edge）、度数、入度/出度、有向图/无向图、连通图。
*   **存储方式**：
    *   **邻接矩阵**：`g[i][j]` 存储 $i$ 到 $j$ 是否有边。空间 $O(V^2)$。
    *   **邻接表**（推荐）：`vector<int> g[N]`。空间 $O(V+E)$，适合稀疏图。

### 2. 具体例子
**例子 2.1**：邻接表的建立（无向图）。
```cpp
vector<int> g[100];
int u, v;
for(int i = 0; i < m; i++) {
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u); // 无向图双向加边
}
```

### 3. 练习巩固
1.  **【简单】单选题**：一个包含 $n$ 个顶点的完全无向图，其边数为（ ）。
    A. $n$  B. $n(n-1)$  C. $n(n-1)/2$  D. $n^2$
2.  **【中等】填空题**：对于邻接矩阵 `int g[10][10]`，若 `g[i][j] = 1` 表示有边，则顶点 `i` 的出度等于邻接矩阵中第 `i` ______（行/列）中 1 的个数。
3.  **【困难】填空题**：若图有 10000 个顶点、20000 条边，最节省空间的存储方式是 ______。

---

## 第三模块：图的遍历与泛洪算法（Flood Fill）

### 1. 知识点拆解
*   **图的 DFS**：利用递归访问所有连通顶点。
*   **图的 BFS**：利用队列按“层”访问。
*   **泛洪算法 (Flood Fill)**：在网格图中，从一个点出发寻找所有相连的同类点。
    *   常见应用：迷宫填色、扫雷区域展开、计算连通块数量。

### 2. 具体例子
**例子 3.1**：统计二维地图中岛屿的数量（Flood Fill）。
```cpp
void dfs(int x, int y) {
    vis[x][y] = true;
    for(int i = 0; i < 4; i++) { // 四个方向
        int nx = x + dx[i], ny = y + dy[i];
        if(nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && map[nx][ny] == '1')
            dfs(nx, ny);
    }
}
```

### 3. 练习巩固
1.  **【简单】对错题**：图的广度优先搜索 (BFS) 可以用来求解无权图中的最短路径问题。（ ）
2.  **【中等】单选题**：在进行图的深度优先搜索 (DFS) 时，通常需要一个额外的数组来记录（ ）。
    A. 节点的入度  B. 节点的出度  C. 节点是否被访问过  D. 节点的编号大小
3.  **【困难】阅读程序填空**：在网格图中，若要求“八连通”方向（含斜对角），则 `dx` 和 `dy` 数组的长度应该是 ______。

---

## 第四模块：复杂动态规划（二维 DP 与优化）

### 1. 知识点拆解
*   **二维 DP**：状态定义包含两个变量，如 `dp[i][j]`。
    *   经典问题：**最长公共子序列 (LCS)**、**最小编辑距离**、**矩阵路径最大和**。
*   **DP 优化思路**：
    *   **空间优化**：使用“滚动数组”将 $O(N^2)$ 空间降至 $O(N)$。
    *   **最值优化**：在状态转移时，通过前缀和、单调队列等手段减少搜索最值的时间。

### 2. 具体例子
**例子 4.1**：矩阵路径问题。
从矩阵左上角到右下角，只能向右或向下，求经过数字的最大和。
方程：`dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]`。

### 3. 练习巩固
1.  **【简单】填空题**：计算两个长度为 $N$ 和 $M$ 的字符串的最长公共子序列，二维 DP 表的大小通常定义为 `dp[N+1][M+1]`，其时间复杂度为 ______。
2.  **【中等】阅读程序写结果**：
    ```cpp
    int dp[3][3] = {0};
    int a[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    dp[0][0] = a[0][0];
    for(int i=1; i<3; i++) dp[i][0] = dp[i-1][0] + a[i][0];
    for(int j=1; j<3; j++) dp[0][j] = dp[0][j-1] + a[0][j];
    for(int i=1; i<3; i++)
        for(int j=1; j<3; j++)
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + a[i][j];
    cout << dp[2][2];
    ```
    输出：__________
3.  **【困难】对错题**：对于 0/1 背包问题，通过滚动数组优化后，空间复杂度可以从 $O(NW)$ 降为 $O(W)$，但时间复杂度依然是 $O(NW)$。（ ）

---

## 教练参考答案与解析

### 第一模块
1.  **B**。
2.  **错**。在发生严重哈希冲突（如所有键都映射到同一个位置）时，会退化为 $O(n)$。
3.  **1, 1, 1**。$12\%11=1, 23\%11=1, 34\%11=1$。（这是严重的哈希冲突案例）。

### 第二模块
1.  **C**。
2.  **行**。
3.  **邻接表**。邻接矩阵需要 $10^8$ 个 `int`，空间超限。

### 第三模块
1.  **对**。
2.  **C**。
3.  **8**。

### 第四模块
1.  **$O(N \times M)$**。
2.  **21**。
    *   路径：1 -> 4 -> 7 -> 8 -> 9？不对。
    *   1->2->3->6->9 = 21。
    *   1->4->5->6->9 = 25？再算：1->4->5->8->9 = 27。
    *   *(纠正计算：dp[0][0]=1, dp[1][0]=5, dp[2][0]=12; dp[0][1]=3, dp[0][2]=6; dp[1][1]=max(5,3)+5=10, dp[1][2]=max(10,6)+6=16; dp[2][1]=max(12,10)+8=20, dp[2][2]=max(20,16)+9=29)*。
    *   最终结果应为 **29**。
3.  **对**。优化的是空间，计算过程并没减少。

---
**教练寄语**：
七级是真正的“算法设计”开端。**图论**让你学会处理复杂的关系网络，**二维 DP** 让你学会处理复杂的状态决策。
在这个阶段，**多画表格（DP表）和多画图（邻接表结构）**是核心。不要只在脑子里想，写下来，逻辑才会清晰！加油！

GESP 七级编程能力认证讲义

第一模块：数学库进阶与哈希表

1. 知识点拆解

数学库 <cmath>：
- sin(x), cos(x)：注意 $x$ 是弧度而非角度（$弧度 = 角度 \times \pi / 180$）。
- log(x)：默认是以 $e$ 为底的自然对数（$\ln$）；log10(x) 是以 10 为底。
- exp(x)：计算 $e^x$。
哈希表 (Hash Table)：
- 核心：通过哈希函数将关键字映射到数组下标，实现 $O(1)$ 查找。
- 冲突处理：拉链法（链表存储冲突元素）和开放地址法。
- 应用：C++ 中的 unordered_map 和 unordered_set。

2. 具体例子

例子 1.1：计算 $\log_2 8$。在 C++ 中没有 log2 之前（早期版本），常用换底公式：log(8) / log(2)。

例子 1.2：使用哈希快速统计频率。

unordered_map<string, int> hash;
string word;
while(cin >> word) hash[word]++; // 极速统计单词出现次数

3. 练习巩固

【简单】单选题：在 C++ 中，计算 $\sin(30^\circ)$ 正确的代码是（）。 A. sin(30) B. sin(30 * M_PI / 180) C. asin(30) D. sin(30 * 180 / M_PI)
【中等】对错题：哈希表的查找效率在所有情况下都能保持 $O(1)$。（）
【困难】填空题：若使用“除留余数法”构建哈希表，哈希函数为 $H(key) = key \% 11$。对于关键字序列 {12, 23, 34}，它们在哈希表中的下标分别是 __、_、___。

第二模块：图的定义与存储

1. 知识点拆解

图论概念：顶点（Vertex）、边（Edge）、度数、入度/出度、有向图/无向图、连通图。
存储方式：
- 邻接矩阵：g[i][j] 存储 $i$ 到 $j$ 是否有边。空间 $O(V^2)$。
- 邻接表（推荐）：vector<int> g[N]。空间 $O(V+E)$，适合稀疏图。

2. 具体例子

例子 2.1：邻接表的建立（无向图）。

vector<int> g[100];
int u, v;
for(int i = 0; i < m; i++) {
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u); // 无向图双向加边
}

3. 练习巩固

【简单】单选题：一个包含 $n$ 个顶点的完全无向图，其边数为（）。 A. $n$ B. $n(n-1)$ C. $n(n-1)/2$ D. $n^2$
【中等】填空题：对于邻接矩阵 int g[10][10]，若 g[i][j] = 1 表示有边，则顶点 i 的出度等于邻接矩阵中第 i ______（行/列）中 1 的个数。
【困难】填空题：若图有 10000 个顶点、20000 条边，最节省空间的存储方式是 ______。

第三模块：图的遍历与泛洪算法（Flood Fill）

1. 知识点拆解

图的 DFS：利用递归访问所有连通顶点。
图的 BFS：利用队列按“层”访问。
泛洪算法 (Flood Fill)：在网格图中，从一个点出发寻找所有相连的同类点。
- 常见应用：迷宫填色、扫雷区域展开、计算连通块数量。

2. 具体例子

例子 3.1：统计二维地图中岛屿的数量（Flood Fill）。

void dfs(int x, int y) {
    vis[x][y] = true;
    for(int i = 0; i < 4; i++) { // 四个方向
        int nx = x + dx[i], ny = y + dy[i];
        if(nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && map[nx][ny] == '1')
            dfs(nx, ny);
    }
}

3. 练习巩固

【简单】对错题：图的广度优先搜索 (BFS) 可以用来求解无权图中的最短路径问题。（）
【中等】单选题：在进行图的深度优先搜索 (DFS) 时，通常需要一个额外的数组来记录（）。 A. 节点的入度 B. 节点的出度 C. 节点是否被访问过 D. 节点的编号大小
【困难】阅读程序填空：在网格图中，若要求“八连通”方向（含斜对角），则 dx 和 dy 数组的长度应该是 ______。

第四模块：复杂动态规划（二维 DP 与优化）

1. 知识点拆解

二维 DP：状态定义包含两个变量，如 dp[i][j]。
- 经典问题：最长公共子序列 (LCS)、最小编辑距离、矩阵路径最大和。
DP 优化思路：
- 空间优化：使用“滚动数组”将 $O(N^2)$ 空间降至 $O(N)$。
- 最值优化：在状态转移时，通过前缀和、单调队列等手段减少搜索最值的时间。

2. 具体例子

例子 4.1：矩阵路径问题。从矩阵左上角到右下角，只能向右或向下，求经过数字的最大和。方程：dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]。

3. 练习巩固

【简单】填空题：计算两个长度为 $N$ 和 $M$ 的字符串的最长公共子序列，二维 DP 表的大小通常定义为 dp[N+1][M+1]，其时间复杂度为 ______。
【中等】阅读程序写结果： cpp int dp[3][3] = {0}; int a[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; dp[0][0] = a[0][0]; for(int i=1; i<3; i++) dp[i][0] = dp[i-1][0] + a[i][0]; for(int j=1; j<3; j++) dp[0][j] = dp[0][j-1] + a[0][j]; for(int i=1; i<3; i++) for(int j=1; j<3; j++) dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + a[i][j]; cout << dp[2][2]; 输出：____
【困难】对错题：对于 0/1 背包问题，通过滚动数组优化后，空间复杂度可以从 $O(NW)$ 降为 $O(W)$，但时间复杂度依然是 $O(NW)$。（）

教练参考答案与解析

第一模块

B。
错。在发生严重哈希冲突（如所有键都映射到同一个位置）时，会退化为 $O(n)$。
1, 1, 1。$12\%11=1, 23\%11=1, 34\%11=1$。（这是严重的哈希冲突案例）。

第二模块

C。
行。
邻接表。邻接矩阵需要 $10^8$ 个 int，空间超限。

第三模块

对。
C。
8。

第四模块

$O(N \times M)$。
21。
- 路径：1 -> 4 -> 7 -> 8 -> 9？不对。
- 1->2->3->6->9 = 21。
- 1->4->5->6->9 = 25？再算：1->4->5->8->9 = 27。
- (纠正计算：dp[0][0]=1, dp[1][0]=5, dp[2][0]=12; dp[0][1]=3, dp[0][2]=6; dp[1][1]=max(5,3)+5=10, dp[1][2]=max(10,6)+6=16; dp[2][1]=max(12,10)+8=20, dp[2][2]=max(20,16)+9=29)。
- 最终结果应为 29。
对。优化的是空间，计算过程并没减少。

教练寄语：七级是真正的“算法设计”开端。图论让你学会处理复杂的关系网络，二维 DP 让你学会处理复杂的状态决策。在这个阶段，多画表格（DP表）和多画图（邻接表结构）是核心。不要只在脑子里想，写下来，逻辑才会清晰！加油！

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