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

## 第一模块：初等数论（数理基石）

### 1. 知识点拆解
*   **唯一分解定理**：任何大于1的整数都能唯一分解为质因数的乘积。
*   **欧几里得算法（辗转相除法）**：`gcd(a, b) = gcd(b, a % b)`。用于快速求最大公约数。
*   **素数筛法**：
    *   **埃氏筛**：标记质数的倍数为合数，复杂度 $O(n \log \log n)$。
    *   **线性筛（欧拉筛）**：每个合数只被其最小质因子筛一次，复杂度 $O(n)$。

### 2. 具体例子
**例子 1.1**：求 48 和 18 的最大公约数。
`gcd(48, 18) -> gcd(18, 48%18=12) -> gcd(12, 18%12=6) -> gcd(6, 12%6=0)`。
结果为 6。

### 3. 练习巩固
1.  **【简单】单选题**：使用辗转相除法求 `gcd(124, 52)`，第二次调用递归时，参数变为（ ）。
    A. (52, 20)  B. (20, 12)  C. (52, 24)  D. (24, 4)
2.  **【中等】对错题**：线性筛法之所以比埃氏筛法快，是因为它保证了每个合数只被标记一次。（ ）
3.  **【困难】填空题**：根据唯一分解定理，正整数 $360$ 的质因数分解形式为 $2^a \times 3^b \times 5^c$，则 $a+b+c = $ ______。

---

## 第二模块：高精度运算（突破 64 位限制）

### 1. 知识点拆解
*   **存储**：用 `int` 或 `vector` 数组逆序存储每一位（个位在下标0）。
*   **加法**：按位相加，处理进位。
*   **减法**：按位相减，不够减向高位借位（需先判断大小保证大减小）。
*   **乘法**：多位数乘一位数（直接乘+处理进位）；多位数乘多位数（$C[i+j] += A[i] \times B[j]$）。

### 2. 具体例子
**例子 2.1**：高精度加法核心逻辑。
```cpp
// c = a + b
for (int i = 0; i < max(la, lb); i++) {
    c[i] += a[i] + b[i];
    c[i+1] = c[i] / 10; // 进位
    c[i] %= 10;         // 本位
}
```

### 3. 练习巩固
1.  **【简单】填空题**：在高精度计算中，为了方便进位处理，通常将字符串读入后______（正序/逆序）存储到数组中。
2.  **【中等】对错题**：在执行高精度减法 `A - B` 之前，必须先比较 A 和 B 的大小，如果 `A < B`，应输出负号并计算 `B - A`。（ ）
3.  **【困难】代码阅读写结果**：若 `A = {2, 5}`（表示 52），`B = 3`，执行 `A[i] * B` 并处理进位后，结果数组为 ______。

---

## 第三模块：线性表与链表

### 1. 知识点拆解
*   **单链表**：每个节点包含 `data` 和 `next` 指针。
*   **双链表**：包含 `prev` 和 `next` 指针，支持双向遍历。
*   **循环链表**：尾节点的 `next` 指向头节点。
*   **优缺点**：插入删除 $O(1)$，随机访问 $O(n)$。

### 2. 具体例子
**例子 3.1**：单链表删除节点（删除 p 指向的后继节点）。
`p->next = p->next->next;`

### 3. 练习巩固
1.  **【简单】单选题**：链表不具备的特点是（ ）。
    A. 随机访问  B. 动态分配内存  C. 插入无需移动元素  D. 节点地址不连续
2.  **【中等】对错题**：在双链表中，删除一个节点需要修改 4 个指针方向。（ ）
3.  **【困难】阅读程序填空**：在单链表中 $p$ 节点后插入 $s$ 节点的逻辑是：
    `s->next = p->next;`
    `________________;`

---

## 第四模块：二分、分治与贪心

### 1. 知识点拆解
*   **二分查找**：在有序序列中寻找目标，每次缩小一半范围。
*   **二分答案**：当答案具有单调性时，通过二分枚举答案并用 `check` 函数验证。
*   **贪心算法**：每一步都采取当前状态下的局部最优解，期望达到全局最优（需证明正确性）。
*   **分治算法**：将大问题拆分为同类小问题。经典应用：**归并排序**（稳定）、**快速排序**（不稳定）。

### 2. 具体例子
**例子 4.1**：二分查找的边界处理。
```cpp
while (left <= right) {
    int mid = left + (right - left) / 2; // 防止溢出
    if (a[mid] == target) return mid;
    if (a[mid] < target) left = mid + 1;
    else right = mid - 1;
}
```

### 3. 练习巩固
1.  **【简单】单选题**：在一个包含 1000 个元素的有序数组中进行二分查找，最多需要比较多少次？
    A. 10  B. 50  C. 100  D. 500
2.  **【中等】对错题**：快速排序在最坏情况下的时间复杂度是 $O(n \log n)$。（ ）
3.  **【困难】阅读程序写结果**：
    用归并排序对 `{5, 2, 8, 1}` 进行升序排序，最后一步“合并（Merge）”前的两个子序列分别是：`____________`。

---

## 第五模块：算法复杂度进阶

### 1. 知识点拆解
*   **常见阶数**：$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!)$。
*   **空间复杂度**：程序运行所需的额外空间。
*   **估算技巧**：1秒内大约能处理 $10^8$ 次基本运算。

### 2. 具体例子
**例子 5.1**：判断算法是否可行。
若 $N = 10^5$，算法复杂度为 $O(n^2)$，则运算次数为 $10^{10}$，在 1 秒内一定会超时。此时应寻求 $O(n \log n)$ 的算法。

### 3. 练习巩固
1.  **【简单】单选题**：以下复杂度中，增长速度最快（效率最低）的是（ ）。
    A. $O(n^2)$  B. $O(2^n)$  C. $O(n \log n)$  D. $O(n^3)$
2.  **【中等】填空题**：二分查找的时间复杂度是 ______，归并排序的时间复杂度是 ______。
3.  **【困难】分析程序**：
    ```cpp
    for(int i = 1; i <= n; i *= 2)
        for(int j = 1; j <= n; j++)
            ans++;
    ```
    该程序段的时间复杂度为 ______。

---

## 教练参考答案与解析

### 第一模块
1.  **C**。`gcd(124, 52)` -> `gcd(52, 124%52=20)` -> `gcd(20, 52%20=12)`。第一次调用是 (52, 20)，第二次是 (20, 12)。
2.  **对**。这是线性筛的核心精髓。
3.  **6**。$360 = 2^3 \times 3^2 \times 5^1$。$a=3, b=2, c=1$。$3+2+1=6$。

### 第二模块
1.  **逆序**。
2.  **对**。
3.  **{6, 5, 1}**。$52 \times 3 = 156$。数组存储为 `{6, 5, 1}`。

### 第三模块
1.  **A**。
2.  **对**。要修改被删节点前驱的 next、后继的 prev，以及处理自身指针（如果是动态内存还需释放）。
3.  **p->next = s**。

### 第四模块
1.  **A**。$2^{10} = 1024$。
2.  **错**。最坏情况（如已排序序列）会退化到 $O(n^2)$。
3.  **{2, 5} 和 {1, 8}**。

### 第五模块
1.  **B**。指数级复杂度增长极快。
2.  **$O(\log n)$**；**$O(n \log n)$**。
3.  **$O(n \log n)$**。外层循环执行 $\log n$ 次，内层 $n$ 次。

---
**教练寄语**：
五级是**从“码农”向“算法工程师”**转化的第一步。如果你觉得高精度和数论很难，不要怕，那是你在接触计算机科学的本质。**多推导公式，多手动模拟数据流**。当你能熟练使用二分和贪心解决问题时，你已经跨过了 OI 最重要的一道坎！加油！

GESP 五级编程能力认证讲义

第一模块：初等数论（数理基石）

1. 知识点拆解

唯一分解定理：任何大于1的整数都能唯一分解为质因数的乘积。
欧几里得算法（辗转相除法）：gcd(a, b) = gcd(b, a % b)。用于快速求最大公约数。
素数筛法：
- 埃氏筛：标记质数的倍数为合数，复杂度 $O(n \log \log n)$。
- 线性筛（欧拉筛）：每个合数只被其最小质因子筛一次，复杂度 $O(n)$。

2. 具体例子

例子 1.1：求 48 和 18 的最大公约数。 gcd(48, 18) -> gcd(18, 48%18=12) -> gcd(12, 18%12=6) -> gcd(6, 12%6=0)。结果为 6。

3. 练习巩固

【简单】单选题：使用辗转相除法求 gcd(124, 52)，第二次调用递归时，参数变为（）。 A. (52, 20) B. (20, 12) C. (52, 24) D. (24, 4)
【中等】对错题：线性筛法之所以比埃氏筛法快，是因为它保证了每个合数只被标记一次。（）
【困难】填空题：根据唯一分解定理，正整数 $360$ 的质因数分解形式为 $2^a \times 3^b \times 5^c$，则 $a+b+c = $ ______。

第二模块：高精度运算（突破 64 位限制）

1. 知识点拆解

存储：用 int 或 vector 数组逆序存储每一位（个位在下标0）。
加法：按位相加，处理进位。
减法：按位相减，不够减向高位借位（需先判断大小保证大减小）。
乘法：多位数乘一位数（直接乘+处理进位）；多位数乘多位数（$C[i+j] += A[i] \times B[j]$）。

2. 具体例子

例子 2.1：高精度加法核心逻辑。

// c = a + b
for (int i = 0; i < max(la, lb); i++) {
    c[i] += a[i] + b[i];
    c[i+1] = c[i] / 10; // 进位
    c[i] %= 10;         // 本位
}

3. 练习巩固

【简单】填空题：在高精度计算中，为了方便进位处理，通常将字符串读入后______（正序/逆序）存储到数组中。
【中等】对错题：在执行高精度减法 A - B 之前，必须先比较 A 和 B 的大小，如果 A < B，应输出负号并计算 B - A。（）
【困难】代码阅读写结果：若 A = {2, 5}（表示 52），B = 3，执行 A[i] * B 并处理进位后，结果数组为 ______。

第三模块：线性表与链表

1. 知识点拆解

单链表：每个节点包含 data 和 next 指针。
双链表：包含 prev 和 next 指针，支持双向遍历。
循环链表：尾节点的 next 指向头节点。
优缺点：插入删除 $O(1)$，随机访问 $O(n)$。

2. 具体例子

例子 3.1：单链表删除节点（删除 p 指向的后继节点）。 p->next = p->next->next;

3. 练习巩固

【简单】单选题：链表不具备的特点是（）。 A. 随机访问 B. 动态分配内存 C. 插入无需移动元素 D. 节点地址不连续
【中等】对错题：在双链表中，删除一个节点需要修改 4 个指针方向。（）
【困难】阅读程序填空：在单链表中 $p$ 节点后插入 $s$ 节点的逻辑是： s->next = p->next; ________________;

第四模块：二分、分治与贪心

1. 知识点拆解

二分查找：在有序序列中寻找目标，每次缩小一半范围。
二分答案：当答案具有单调性时，通过二分枚举答案并用 check 函数验证。
贪心算法：每一步都采取当前状态下的局部最优解，期望达到全局最优（需证明正确性）。
分治算法：将大问题拆分为同类小问题。经典应用：归并排序（稳定）、快速排序（不稳定）。

2. 具体例子

例子 4.1：二分查找的边界处理。

while (left <= right) {
    int mid = left + (right - left) / 2; // 防止溢出
    if (a[mid] == target) return mid;
    if (a[mid] < target) left = mid + 1;
    else right = mid - 1;
}

3. 练习巩固

【简单】单选题：在一个包含 1000 个元素的有序数组中进行二分查找，最多需要比较多少次？ A. 10 B. 50 C. 100 D. 500
【中等】对错题：快速排序在最坏情况下的时间复杂度是 $O(n \log n)$。（）
【困难】阅读程序写结果：用归并排序对 {5, 2, 8, 1} 进行升序排序，最后一步“合并（Merge）”前的两个子序列分别是：____________。

第五模块：算法复杂度进阶

1. 知识点拆解

常见阶数：$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!)$。
空间复杂度：程序运行所需的额外空间。
估算技巧：1秒内大约能处理 $10^8$ 次基本运算。

2. 具体例子

例子 5.1：判断算法是否可行。若 $N = 10^5$，算法复杂度为 $O(n^2)$，则运算次数为 $10^{10}$，在 1 秒内一定会超时。此时应寻求 $O(n \log n)$ 的算法。

3. 练习巩固

【简单】单选题：以下复杂度中，增长速度最快（效率最低）的是（）。 A. $O(n^2)$ B. $O(2^n)$ C. $O(n \log n)$ D. $O(n^3)$
【中等】填空题：二分查找的时间复杂度是 __，归并排序的时间复杂度是 ____。
【困难】分析程序： cpp for(int i = 1; i <= n; i *= 2) for(int j = 1; j <= n; j++) ans++; 该程序段的时间复杂度为 ______。

教练参考答案与解析

第一模块

C。gcd(124, 52) -> gcd(52, 124%52=20) -> gcd(20, 52%20=12)。第一次调用是 (52, 20)，第二次是 (20, 12)。
对。这是线性筛的核心精髓。
6。$360 = 2^3 \times 3^2 \times 5^1$。$a=3, b=2, c=1$。$3+2+1=6$。

第二模块

逆序。
对。
{6, 5, 1}。$52 \times 3 = 156$。数组存储为 {6, 5, 1}。

第三模块

A。
对。要修改被删节点前驱的 next、后继的 prev，以及处理自身指针（如果是动态内存还需释放）。
p->next = s。

第四模块

A。$2^{10} = 1024$。
错。最坏情况（如已排序序列）会退化到 $O(n^2)$。
{2, 5} 和 {1, 8}。

第五模块

B。指数级复杂度增长极快。
$O(\log n)$；$O(n \log n)$。
$O(n \log n)$。外层循环执行 $\log n$ 次，内层 $n$ 次。

教练寄语：五级是从“码农”向“算法工程师”转化的第一步。如果你觉得高精度和数论很难，不要怕，那是你在接触计算机科学的本质。多推导公式，多手动模拟数据流。当你能熟练使用二分和贪心解决问题时，你已经跨过了 OI 最重要的一道坎！加油！

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