# 附录 A 五级考前速查与真题训练安排

五级考试中，很多失分并不来自不会算法，而是来自概念混淆、边界遗漏、代码顺序写反。考前复习时，可以用本章快速检查各知识点的常见错误。

本章适合放在讲义最后，作为考前速查内容。

---

## 一、复杂度易错点

### 1. 多层循环不一定都是 $O(n^2)$
看到两层循环时，要看每层循环的次数。
```cpp
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j *= 2) {
        cout << i << " " << j << "\n";
    }
}
```
外层 $O(n)$，内层 $O(\log n)$，总复杂度是 $O(n \log n)$。

### 2. 每次乘除常数通常是 $O(\log n)$
```cpp
for (int i = 1; i <= n; i *= 2)
    cout << i << "\n";
```
$i$ 的变化是 $1, 2, 4, 8, \dots$，循环次数是 $O(\log n)$。

### 3. $O(n^2)$ 在 $n = 10^5$ 时通常不可接受
若 $n = 10^5$， $n^2 = 10^{10}$，通常无法在时间限制内完成。遇到这种数据范围，应考虑 $O(n)$、$O(n \log n)$ 或二分、筛法、贪心等方法。

---

## 二、链表易错点

### 1. 单链表不能高效随机访问
数组可以直接访问 `a[i]`，链表通常要从头结点开始顺序走到目标位置。

### 2. 单链表插入顺序不能反
在 `cur` 后插入 `p`：
```cpp
p‐>next = cur‐>next;
cur‐>next = p;
```
如果先写：
```cpp
cur‐>next = p;
p‐>next = cur‐>next; // 错误！
```
会导致 `p->next` 指向自己，原后继结点丢失。

### 3. 删除结点前要先保存指针
```cpp
Node* del = cur‐>next;
cur‐>next = del‐>next;
delete del;
```
释放后不能再访问 `del->next`。

### 4. 哑结点用于统一处理头结点
```cpp
Node dummy;
dummy.next = head;
```
删除头结点和删除中间结点都可以转化为删除 `cur->next`。

### 5. 循环链表不能用 `nullptr` 作为正常结束条件
循环链表遍历常用：
```cpp
do {
    cout << cur‐>val << " ";
    cur = cur‐>next;
} while (cur != head);
```

### 6. 快慢指针访问前要判空
```cpp
while (fast != nullptr && fast‐>next != nullptr) {
    slow = slow‐>next;
    fast = fast‐>next‐>next;
}
```
访问 `fast->next->next` 前，要保证 `fast` 和 `fast->next` 都有效。

---

## 三、数论易错点

### 1. 1 不是质数
质数必须是大于 1，且只有 1 和自身两个正约数的整数。

### 2. 判断质数要写 `i * i <= n`
```cpp
for (int i = 2; 1ll * i * i <= n; i++)
```
不能写成：`i * i < n`，否则会漏掉平方数，例如 49。

### 3. 质因数分解后要处理剩余数
```cpp
if (n > 1)
    cout << n << " ";
```
循环结束后若剩余的 $n > 1$，它本身是最后一个质因数。

### 4. 统计不同质因数时要除干净
```cpp
if (x % p == 0) {
    cnt++;
    while (x % p == 0)
        x /= p;
}
```
否则同一种质因数可能被重复统计。

### 5. 互质不代表两个数都是质数
例如 8 和 15 都是合数，但 $\gcd(8, 15) = 1$，所以它们互质。

### 6. 唯一分解定理是质数乘积
- **正确说法：** 每个大于 1 的整数都可以唯一分解成若干个质数的乘积。
- **错误说法：** 唯一分解定理表示可以唯一分解成质数之和。

---

## 四、欧几里得算法易错点

### 1. 递归参数顺序不能写反
正确写法：
```cpp
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}
```
核心是：`gcd(b, a % b)`

### 2. 循环写法要先保存余数
```cpp
while (b != 0) {
    int t = a % b;
    a = b;
    b = t;
}
```
不能先修改 `a` 后再用原来的 `a` 取余。

### 3. 求最小公倍数优先先除后乘
```cpp
long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}
```
比直接写 `a * b / gcd(a, b)` 更能降低中间溢出的风险。

### 4. 多个数的最大公约数可以依次合并
```cpp
int g = 0;
for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    g = gcd(g, x);
}
```
利用的是 $\gcd(0, x) = x$。

---

## 五、筛法易错点

### 1. 看清布尔数组含义
- 如果数组名是 `np`（Not Prime），通常表示是否为合数：
  ```cpp
  if (!np[i]) cout << i << " ";
  ```
- 如果数组名是 `isPrime`，通常表示是否为质数：
  ```cpp
  if (isPrime[i]) cout << i << " ";
  ```
  不要只看 `true` 或 `false`，要看变量名和代码语义。

### 2. 埃氏筛不能从 `i` 开始标记
错误写法：
```cpp
for (int j = i; j <= n; j += i) // 错误！
    np[j] = true;
```
这会把质数 `i` 自己标记为合数。
常见正确写法：
```cpp
for (long long j = 1ll * i * i; j <= n; j += i)
    np[j] = true;
```

### 3. 线性筛内层条件要完整
```cpp
for (int j = 1; j <= cnt && 1ll * i * p[j] <= n; j++)
```
既要保证 `j <= cnt`，也要保证 `i * p[j] <= n`。

### 4. 线性筛的 break 不能乱删
```cpp
if (i % p[j] == 0)
    break;
```
这句保证每个合数只被它的最小质因子筛掉一次。

### 5. 线性筛不是由最大质因子标记
- **正确说法：** 每个合数只被它的最小质因子筛掉一次。

---

## 六、高精度易错点

### 1. 先判断存储方向
- **低位在前：** $1234 \implies a[1]=4, a[2]=3, a[3]=2, a[4]=1$
- **高位在前：** $1234 \implies a[0]=1, a[1]=2, a[2]=3, a[3]=4$

读代码时，先看数组下标含义，再判断进位和输出顺序。

### 2. 加法当前位和进位不能写反
```cpp
int t = a[i] + b[i] + ca;
c[i] = t % 10;
ca = t / 10;
```
`% 10` 是当前位，`/ 10` 是进位。

### 3. 减法借位方向要看存储方向
低位在前时：
```cpp
if (a[i] < b[i]) {
    a[i] += 10;
    a[i + 1]‐‐;
}
```
`a[i+1]` 是更高一位。

### 4. 乘法贡献位置是 $i + j - 1$
低位在前时：
```cpp
c[i + j ‐ 1] += a[i] * b[j];
```
之后再统一进位：
```cpp
c[i + 1] += c[i] / 10;
c[i] %= 10;
```

### 5. 除法通常从高位到低位
```cpp
for (int i = len; i >= 1; i‐‐) {
    r = r * 10 + a[i];
    c[i] = r / b;
    r %= b;
}
```
`r` 是当前余数，不能丢弃。

### 6. 去前导零要保留一位
```cpp
while (len > 1 && a[len] == 0)
    len‐‐;
```
数字 0 应输出一位 0。

---

## 七、二分易错点

### 1. 普通二分要求有序
无序数组中，`a[mid] < x` 无法说明答案在右边，因此不能直接二分。

### 2. 二分答案要求单调性
能二分的可行性通常长这样：
`false false false true true true` 或 `true true true false false false`
若没有单调性，不能直接二分。

### 3. 找第一个满足条件的位置
```cpp
while (l < r) {
    int mid = l + (r ‐ l) / 2;
    if (check(mid))
        r = mid;
    else
        l = mid + 1;
}
```
`mid` 满足时不能排除，因为它可能就是第一个满足的位置。

### 4. 找最后一个满足条件的位置
```cpp
while (l < r) {
    int mid = l + (r ‐ l + 1) / 2;
    if (check(mid))
        l = mid;
    else
        r = mid ‐ 1;
}
```
这里使用靠右中点，避免死循环。

### 5. 中点推荐安全写法
`int mid = l + (r ‐ l) / 2;` 比 `(l + r) / 2` 更稳（防止整型溢出）。

### 6. check 要说清楚含义
写二分答案前，先用一句话定义：
> `check(x)`：当答案为 $x$ 时，是否可行？

若这句话说不清，二分大概率会写乱。

---

## 八、递归易错点

### 1. 递归必须有出口
```cpp
if (n == 0) return;
```
没有出口会无限递归。

### 2. 有出口还要能接近出口
错误写法：
```cpp
int f(int n) {
    if (n == 1) return 1;
    return f(n); // 错误：参数没有变化
}
```

### 3. 输出顺序看输出语句位置
- **递归前输出：** 先输出大值。
  ```cpp
  cout << n << " ";
  f(n ‐ 1);
  ```
- **递归后输出：** 返回时输出小值到大值。
  ```cpp
  f(n ‐ 1);
  cout << n << " ";
  ```

### 4. 朴素斐波那契有大量重复计算
```cpp
int fib(int n) {
    if (n <= 1) return n;
    return fib(n ‐ 1) + fib(n ‐ 2);
}
```
很多子问题会被重复计算，复杂度很高。

### 5. 递归层数过深可能栈溢出
即使逻辑正确，调用层数过深也可能运行错误。

---

## 九、分治与排序易错点

### 1. 分治要有分解和合并
归并排序：
```cpp
mergeSort(l, mid);
mergeSort(mid + 1, r);
merge(l, mid, r);
```
前两句是分解，最后一句是合并。

### 2. 归并排序左右区间不要写错
- 左半段：`[l, mid]`
- 右半段：`[mid + 1, r]`
- 右半段剩余条件：`while (j <= r)`

### 3. 归并排序稳定性看相等时取谁
```cpp
if (a[i] <= a[j])
    tmp[k++] = a[i++];
```
相等时取左半段，可以保持稳定性。

### 4. 快速排序最坏情况是 $O(n^2)$
若每次基准值都让划分极不均衡，例如有序数组总选第一个元素为基准值，快速排序可能退化。

### 5. 快速排序通常不稳定
快速排序中元素可能被交换到很远的位置，相同关键字元素的相对顺序可能改变。

---

## 十、贪心易错点

### 1. 贪心不一定总正确
贪心每一步做当前看来最优的选择，但只有问题结构支持时，才能得到全局最优。

### 2. 区间选择按结束时间排序
```cpp
bool cmp(Seg a, Seg b) {
    return a.r < b.r;
}
```
不要按开始时间排序。

### 3. 任务安排按收益排序
```cpp
bool cmp(Task a, Task b) {
    return a.p > b.p;
}
```
然后尽量放到不超过截止时间的最晚空闲时间槽。

### 4. 过河问题每次处理最重的人
```cpp
if (w[l] + w[r] <= W)
    l++;
r‐‐;
ans++;
```
最重的人必须上船，能与最轻的人搭配就搭配。

### 5. 差值选择要看默认方案
若先假设全部选 $B$，改成 $C$ 的收益变化是：`d[i] = c[i] ‐ b[i];`。默认方案不同，差值方向也不同。

---

## 十一、考前一分钟检查表

### 概念检查
- [ ] 1 不是质数。
- [ ] 互质不代表两个数都是质数。
- [ ] 贪心不一定总能得到最优解。
- [ ] 普通二分依赖有序性。
- [ ] 二分答案依赖单调性。
- [ ] 递归要有出口，也要接近出口。
- [ ] 归并排序通常稳定。
- [ ] 快速排序通常不稳定。

### 代码检查
- [ ] 链表插入是否先接后继。
- [ ] 链表删除是否先保存待删结点。
- [ ] gcd 是否写成 `gcd(b, a % b)`。
- [ ] 最小公倍数是否先除后乘。
- [ ] 质数判断是否用 `i * i <= n`。
- [ ] 埃氏筛是否从 `i * i` 开始。
- [ ] 线性筛是否保留 `i % p[j] == 0` 的 break。
- [ ] 高精度加法 `% 10` 和 `/ 10` 是否写反。
- [ ] 高精度除法是否更新 `r %= b`。
- [ ] 二分找最大可行值是否使用靠右中点。
- [ ] 归并排序右半段是否写成 `mid + 1` 到 `r`。
- [ ] 贪心排序关键字是否选对。

---

## 十二、错题复盘模板

每道错题建议按下面格式记录：
- **题目类型：**
- **错误原因：**
- **正确知识点：**
- **关键代码：**
- **下次遇到同类题先检查：**

**示例：**
- **题目类型：** 二分答案
- **错误原因：** 把最大可行值写成了最小可行值模板
- **正确知识点：** `true true false false` 要找最后一个 `true`
- **关键代码：** `mid = l + (r ‐ l + 1) / 2`
- **下次遇到同类题先检查：** `check` 的单调方向

坚持这样复盘几轮，五级常见失分点会明显减少。

附录 A 五级考前速查与真题训练安排

五级考试中，很多失分并不来自不会算法，而是来自概念混淆、边界遗漏、代码顺序写反。考前复习时，可以用本章快速检查各知识点的常见错误。

本章适合放在讲义最后，作为考前速查内容。

一、复杂度易错点

1. 多层循环不一定都是 $O(n^2)$

看到两层循环时，要看每层循环的次数。

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j *= 2) {
        cout << i << " " << j << "\n";
    }
}

外层 $O(n)$，内层 $O(\log n)$，总复杂度是 $O(n \log n)$。

2. 每次乘除常数通常是 $O(\log n)$

for (int i = 1; i <= n; i *= 2)
    cout << i << "\n";

$i$ 的变化是 $1, 2, 4, 8, \dots$，循环次数是 $O(\log n)$。

3. $O(n^2)$ 在 $n = 10^5$ 时通常不可接受

若 $n = 10^5$， $n^2 = 10^{10}$，通常无法在时间限制内完成。遇到这种数据范围，应考虑 $O(n)$、$O(n \log n)$ 或二分、筛法、贪心等方法。

二、链表易错点

1. 单链表不能高效随机访问

数组可以直接访问 a[i]，链表通常要从头结点开始顺序走到目标位置。

2. 单链表插入顺序不能反

在 cur 后插入 p：

p‐>next = cur‐>next;
cur‐>next = p;

如果先写：

cur‐>next = p;
p‐>next = cur‐>next; // 错误！

会导致 p->next 指向自己，原后继结点丢失。

3. 删除结点前要先保存指针

Node* del = cur‐>next;
cur‐>next = del‐>next;
delete del;

释放后不能再访问 del->next。

4. 哑结点用于统一处理头结点

Node dummy;
dummy.next = head;

删除头结点和删除中间结点都可以转化为删除 cur->next。

5. 循环链表不能用 `nullptr` 作为正常结束条件

循环链表遍历常用：

do {
    cout << cur‐>val << " ";
    cur = cur‐>next;
} while (cur != head);

6. 快慢指针访问前要判空

while (fast != nullptr && fast‐>next != nullptr) {
    slow = slow‐>next;
    fast = fast‐>next‐>next;
}

访问 fast->next->next 前，要保证 fast 和 fast->next 都有效。

三、数论易错点

1. 1 不是质数

质数必须是大于 1，且只有 1 和自身两个正约数的整数。

2. 判断质数要写 `i * i <= n`

for (int i = 2; 1ll * i * i <= n; i++)

不能写成：i * i < n，否则会漏掉平方数，例如 49。

3. 质因数分解后要处理剩余数

if (n > 1)
    cout << n << " ";

循环结束后若剩余的 $n > 1$，它本身是最后一个质因数。

4. 统计不同质因数时要除干净

if (x % p == 0) {
    cnt++;
    while (x % p == 0)
        x /= p;
}

否则同一种质因数可能被重复统计。

5. 互质不代表两个数都是质数

例如 8 和 15 都是合数，但 $\gcd(8, 15) = 1$，所以它们互质。

6. 唯一分解定理是质数乘积

正确说法： 每个大于 1 的整数都可以唯一分解成若干个质数的乘积。
错误说法： 唯一分解定理表示可以唯一分解成质数之和。

四、欧几里得算法易错点

1. 递归参数顺序不能写反

正确写法：

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

核心是：gcd(b, a % b)

2. 循环写法要先保存余数

while (b != 0) {
    int t = a % b;
    a = b;
    b = t;
}

不能先修改 a 后再用原来的 a 取余。

3. 求最小公倍数优先先除后乘

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

比直接写 a * b / gcd(a, b) 更能降低中间溢出的风险。

4. 多个数的最大公约数可以依次合并

int g = 0;
for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    g = gcd(g, x);
}

利用的是 $\gcd(0, x) = x$。

五、筛法易错点

1. 看清布尔数组含义

如果数组名是 np（Not Prime），通常表示是否为合数： cpp if (!np[i]) cout << i << " ";
如果数组名是 isPrime，通常表示是否为质数： cpp if (isPrime[i]) cout << i << " "; 不要只看 true 或 false，要看变量名和代码语义。

2. 埃氏筛不能从 `i` 开始标记

错误写法：

for (int j = i; j <= n; j += i) // 错误！
    np[j] = true;

这会把质数 i 自己标记为合数。常见正确写法：

for (long long j = 1ll * i * i; j <= n; j += i)
    np[j] = true;

3. 线性筛内层条件要完整

for (int j = 1; j <= cnt && 1ll * i * p[j] <= n; j++)

既要保证 j <= cnt，也要保证 i * p[j] <= n。

4. 线性筛的 break 不能乱删

if (i % p[j] == 0)
    break;

这句保证每个合数只被它的最小质因子筛掉一次。

5. 线性筛不是由最大质因子标记

正确说法： 每个合数只被它的最小质因子筛掉一次。

六、高精度易错点

1. 先判断存储方向

低位在前： $1234 \implies a[1]=4, a[2]=3, a[3]=2, a[4]=1$
高位在前： $1234 \implies a[0]=1, a[1]=2, a[2]=3, a[3]=4$

读代码时，先看数组下标含义，再判断进位和输出顺序。

2. 加法当前位和进位不能写反

int t = a[i] + b[i] + ca;
c[i] = t % 10;
ca = t / 10;

% 10 是当前位，/ 10 是进位。

3. 减法借位方向要看存储方向

低位在前时：

if (a[i] < b[i]) {
    a[i] += 10;
    a[i + 1]‐‐;
}

a[i+1] 是更高一位。

4. 乘法贡献位置是 $i + j - 1$

低位在前时：

c[i + j ‐ 1] += a[i] * b[j];

之后再统一进位：

c[i + 1] += c[i] / 10;
c[i] %= 10;

5. 除法通常从高位到低位

for (int i = len; i >= 1; i‐‐) {
    r = r * 10 + a[i];
    c[i] = r / b;
    r %= b;
}

r 是当前余数，不能丢弃。

6. 去前导零要保留一位

while (len > 1 && a[len] == 0)
    len‐‐;

数字 0 应输出一位 0。

七、二分易错点

1. 普通二分要求有序

无序数组中，a[mid] < x 无法说明答案在右边，因此不能直接二分。

2. 二分答案要求单调性

能二分的可行性通常长这样： false false false true true true 或 true true true false false false 若没有单调性，不能直接二分。

3. 找第一个满足条件的位置

while (l < r) {
    int mid = l + (r ‐ l) / 2;
    if (check(mid))
        r = mid;
    else
        l = mid + 1;
}

mid 满足时不能排除，因为它可能就是第一个满足的位置。

4. 找最后一个满足条件的位置

while (l < r) {
    int mid = l + (r ‐ l + 1) / 2;
    if (check(mid))
        l = mid;
    else
        r = mid ‐ 1;
}

这里使用靠右中点，避免死循环。

5. 中点推荐安全写法

int mid = l + (r ‐ l) / 2; 比 (l + r) / 2 更稳（防止整型溢出）。

6. check 要说清楚含义

写二分答案前，先用一句话定义：

check(x)：当答案为 $x$ 时，是否可行？

若这句话说不清，二分大概率会写乱。

八、递归易错点

1. 递归必须有出口

if (n == 0) return;

没有出口会无限递归。

2. 有出口还要能接近出口

错误写法：

int f(int n) {
    if (n == 1) return 1;
    return f(n); // 错误：参数没有变化
}

3. 输出顺序看输出语句位置

递归前输出： 先输出大值。 cpp cout << n << " "; f(n ‐ 1);
递归后输出： 返回时输出小值到大值。 cpp f(n ‐ 1); cout << n << " ";

4. 朴素斐波那契有大量重复计算

int fib(int n) {
    if (n <= 1) return n;
    return fib(n ‐ 1) + fib(n ‐ 2);
}

很多子问题会被重复计算，复杂度很高。

5. 递归层数过深可能栈溢出

即使逻辑正确，调用层数过深也可能运行错误。

九、分治与排序易错点

1. 分治要有分解和合并

归并排序：

mergeSort(l, mid);
mergeSort(mid + 1, r);
merge(l, mid, r);

前两句是分解，最后一句是合并。

2. 归并排序左右区间不要写错

左半段：[l, mid]
右半段：[mid + 1, r]
右半段剩余条件：while (j <= r)

3. 归并排序稳定性看相等时取谁

if (a[i] <= a[j])
    tmp[k++] = a[i++];

相等时取左半段，可以保持稳定性。

4. 快速排序最坏情况是 $O(n^2)$

若每次基准值都让划分极不均衡，例如有序数组总选第一个元素为基准值，快速排序可能退化。

5. 快速排序通常不稳定

快速排序中元素可能被交换到很远的位置，相同关键字元素的相对顺序可能改变。

十、贪心易错点

1. 贪心不一定总正确

贪心每一步做当前看来最优的选择，但只有问题结构支持时，才能得到全局最优。

2. 区间选择按结束时间排序

bool cmp(Seg a, Seg b) {
    return a.r < b.r;
}

不要按开始时间排序。

3. 任务安排按收益排序

bool cmp(Task a, Task b) {
    return a.p > b.p;
}

然后尽量放到不超过截止时间的最晚空闲时间槽。

4. 过河问题每次处理最重的人

if (w[l] + w[r] <= W)
    l++;
r‐‐;
ans++;

最重的人必须上船，能与最轻的人搭配就搭配。

5. 差值选择要看默认方案

若先假设全部选 $B$，改成 $C$ 的收益变化是：d[i] = c[i] ‐ b[i];。默认方案不同，差值方向也不同。

十一、考前一分钟检查表

概念检查

[ ] 1 不是质数。
[ ] 互质不代表两个数都是质数。
[ ] 贪心不一定总能得到最优解。
[ ] 普通二分依赖有序性。
[ ] 二分答案依赖单调性。
[ ] 递归要有出口，也要接近出口。
[ ] 归并排序通常稳定。
[ ] 快速排序通常不稳定。

代码检查

[ ] 链表插入是否先接后继。
[ ] 链表删除是否先保存待删结点。
[ ] gcd 是否写成 gcd(b, a % b)。
[ ] 最小公倍数是否先除后乘。
[ ] 质数判断是否用 i * i <= n。
[ ] 埃氏筛是否从 i * i 开始。
[ ] 线性筛是否保留 i % p[j] == 0 的 break。
[ ] 高精度加法 % 10 和 / 10 是否写反。
[ ] 高精度除法是否更新 r %= b。
[ ] 二分找最大可行值是否使用靠右中点。
[ ] 归并排序右半段是否写成 mid + 1 到 r。
[ ] 贪心排序关键字是否选对。

十二、错题复盘模板

每道错题建议按下面格式记录： - 题目类型： - 错误原因： - 正确知识点： - 关键代码： - 下次遇到同类题先检查：

示例： - 题目类型： 二分答案 - 错误原因： 把最大可行值写成了最小可行值模板 - 正确知识点： true true false false 要找最后一个 true - 关键代码： mid = l + (r ‐ l + 1) / 2 - 下次遇到同类题先检查： check 的单调方向

坚持这样复盘几轮，五级常见失分点会明显减少。

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