# C++ STL 算法竞赛常用用法讲义

**C++ 标准模板库 (STL, Standard Template Library)** 是包含常用数据结构与算法模板的 C++ 软件库。它主要包含四个组件：**容器 (Containers)、算法 (Algorithms)、迭代器 (Iterators)、仿函数 (Functors)**。

*   **算法示例**：`sort(a.begin(), a.end())`
*   **容器示例**：`priority_queue<int> pque`
*   **仿函数示例**：`greater<int>()`
*   **迭代器示例**：`vector<int>::iterator it = a.begin()`

---

## 1. 前言

STL 在算法竞赛中运用极其广泛。灵活且正确地使用 STL 可以节省大量解题时间。这不仅是因为可以直接调用现成的数据结构，更是因为其良好的封装性能让代码更具可读性、思路更清晰，从而减少调试阶段的失误。

但在实际竞赛中，需要权衡 STL 的利弊。由于 STL 考虑了通用性与安全性，其运行效率在某些极端情况下可能不如针对特定题目手写的数据结构（如手写栈、手写双指针等）。因此，**STL 的使用有时是用运行常数换取编程效率**，具体的取舍需要结合题目时限与个人经验来决定。

---

## 2. 常用容器

### 2.1 内容总览
下表列出了算法竞赛中常见的容器。标记 `[x]` 的为本讲义详细讲解的核心容器。

---

### 2.2 向量 `vector`
`#include <vector>`  
基于连续内存的顺序存储结构（类似动态数组），支持动态扩容。

#### 2.2.1 常用方法
##### 1) 构造函数
*   `vector<类型> arr(长度, [初值])`  
*   **时间复杂度**：$O(N)$

```cpp
vector<int> arr;         // 构造一个空数组
vector<int> arr(100);    // 构造初始长度为 100 的数组，默认初值为 0
vector<int> arr(100, 1); // 构造初始长度为 100 的数组，初值均设为 1

vector<vector<int>> mat(100, vector<int>());       // 构造 100 行，列数动态的二维数组
vector<vector<int>> mat(100, vector<int>(666, -1)); // 构造 100 行 666 列的二维数组，初值为 -1
```

*   **注意（避坑写法）：**

```cpp
vector<int> arr[100];         // 正确：构造了 100 个 vector 对象组成的静态数组，常用于邻接表存图
vector<int> arr[100](100, 1); // 语法错误！
```

##### 2) 尾接与尾删
*   `.push_back(元素)`：在 vector 尾部插入一个元素，数组长度增加 1。
*   `.pop_back()`：删除 vector 尾部的一个元素，数组长度减少 1。
*   **时间复杂度**：均摊 $O(1)$

```cpp
// 初始化: arr = []
arr.push_back(1); // arr = [1]
arr.push_back(2); // arr = [1, 2]
arr.pop_back();   // arr = [1]
```

##### 3) 中括号运算符 `[]`
*   支持通过下标随机访问元素，与普通静态数组一致。
*   **时间复杂度**：$O(1)$

##### 4) 获取长度与判空
*   `.size()`：获取当前元素数量。**时间复杂度**：$O(1)$
*   `.empty()`：若为空返回 `true`，否则返回 `false`。**时间复杂度**：$O(1)$

##### 5) 清空
*   `.clear()`：清空容器内所有元素。
*   **时间复杂度**：$O(N)$（因为需要析构容器内的元素）

##### 6) 改变长度
*   `.resize(新长度, [默认值])`：修改 vector 的长度。  
    *   若新长度小于当前长度，则截断多余元素。
    *   若新长度大于当前长度，则用默认值填充新位置（旧元素保持不变）。
    *   **时间复杂度**：$O(N)$

#### 2.2.2 适用情形
*   在多数场景下可以替代普通数组（除非题目对时空常数有极其苛刻的要求）。
*   **解决稀疏矩阵或大内存问题**：例如面对一个 $N \times M$ 的矩阵，若 $N, M \le 10^5$ 且实际有效元素（非零元素或总查询）数量较少。直接开静态二维数组 `int mat[100010][100010]` 会导致内存超限 (MLE)。此时使用 `vector<vector<int>>` 或邻接表方式可动态按需分配空间。
*   `vector` 申请的空间在堆上，不容易出现局部静态数组导致的栈溢出。

#### 2.2.3 注意事项
1.  **提前指定长度**：若已知所需的数组长度，建议直接在构造函数中指定，或使用 `.reserve(容量)` 提前保留空间。避免因频繁 `.push_back()` 导致底层数组频繁重新分配内存和拷贝。

```cpp
// 优化前: 耗时约 522ms
vector<int> a;
for (int i = 0; i < 1e8; i++)
    a.push_back(i);

// 优化后: 耗时约 259ms
vector<int> a(1e8);
for (int i = 0; i < a.size(); i++)
    a[i] = i;
```

2.  **小心 `size_t` 溢出**：`.size()` 返回的是 `size_t` 类型（无符号整数）。在 32 位环境下，其最大值为 $2^{32}-1$。

```cpp
vector<int> a(65536);
// a.size() * a.size() 会在 size_t 范围内计算，由于 65536 * 65536 = 2^32，直接溢出变成 0
long long area = a.size() * a.size(); 
```

---

### 2.3 栈 `stack`
`#include <stack>`  
通过封装底层容器（默认是 `std::deque`），实现后进先出 (LIFO) 的数据结构。

#### 2.3.1 常用方法
| 作用 | 用法 | 示例 | 时间复杂度 |
| :--- | :--- | :--- | :--- |
| **构造** | `stack<类型> stk` | `stack<int> stk;` | $O(1)$ |
| **入栈** | `.push(元素)` | `stk.push(1);` | $O(1)$ |
| **出栈** | `.pop()` | `stk.pop();` | $O(1)$ |
| **取栈顶** | `.top()` | `int val = stk.top();` | $O(1)$ |
| **判空** | `.empty()` | `stk.empty();` | $O(1)$ |
| **大小** | `.size()` | `stk.size();` | $O(1)$ |

#### 2.3.2 适用情形
*   用于括号匹配、单调栈、深度优先搜索（非递归 DFS）等场景。
*   如果不卡常数，可以直接使用。也可以直接用 `vector` 模拟栈：`vector` 的 `.back()` 相当于 `.top()`，`.push_back()` 相当于 `.push()`，`.pop_back()` 相当于 `.pop()`。

#### 2.3.3 注意事项
*   **不可随机访问或遍历内部元素**：以下用法均为编译错误。
```cpp
for (int i = 0; i < stk.size(); i++) cout << stk[i] << endl; // 错误！
for (auto ele : stk) cout << ele << endl;                   // 错误！
```

---

### 2.4 队列 `queue`
`#include <queue>`  
基于先进先出 (FIFO) 原理的数据结构。

#### 2.4.1 常用方法
| 作用 | 用法 | 示例 | 时间复杂度 |
| :--- | :--- | :--- | :--- |
| **构造** | `queue<类型> que` | `queue<int> que;` | $O(1)$ |
| **入队** | `.push(元素)` | `que.push(1);` | $O(1)$ |
| **出队** | `.pop()` | `que.pop();` | $O(1)$ |
| **取队首** | `.front()` | `int val = que.front();` | $O(1)$ |
| **取队尾** | `.back()` | `int val = que.back();` | $O(1)$ |
| **判空** | `.empty()` | `que.empty();` | $O(1)$ |
| **大小** | `.size()` | `que.size();` | $O(1)$ |

#### 2.4.2 适用情形
*   常用于广度优先搜索 (BFS) 算法。

#### 2.4.3 注意事项
*   同样**不可遍历内部元素**：
```cpp
for (int i = 0; i < que.size(); i++) cout << que[i] << endl; // 错误！
for (auto ele : que) cout << ele << endl;                   // 错误！
```

---

### 2.5 优先队列 `priority_queue`
`#include <queue>`  
底层基于二叉堆实现，支持在 $O(\log N)$ 时间内插入/删除元素，并在 $O(1)$ 时间内查询最值（堆顶元素）。

#### 2.5.1 常用方法
##### 1) 构造函数
`priority_queue<类型, 容器, 比较器>`
*   **类型**：存储的数据类型
*   **容器**：底层的存储容器（竞赛中一般用默认的 `vector<类型>`）
*   **比较器**：确定优先级的规则。默认是 `less<类型>`（即**大顶堆**，最大值在堆顶）；若指定为 `greater<类型>` 则为**小顶堆**（最小值在堆顶）。
```cpp
priority_queue<int> pque1;                            // 大顶堆
priority_queue<int, vector<int>, greater<int>> pque2; // 小顶堆
```

##### 2) 成员函数
| 作用 | 用法 | 示例 | 时间复杂度 |
| :--- | :--- | :--- | :--- |
| **入堆** | `.push(元素)` | `pque.push(1);` | $O(\log N)$ |
| **出堆** | `.pop()` | `pque.pop();` | $O(\log N)$ |
| **取堆顶** | `.top()` | `int a = pque.top();` | $O(1)$ |
| **大小** | `.size()` | `pque.size();` | $O(1)$ |
| **判空** | `.empty()` | `pque.empty();` | $O(1)$ |

#### 2.5.2 适用情形
*   **持续维护动态有序性**：需要频繁插入大小不定的元素，且随时需要取出其中最大/最小的元素。
*   常用于 Dijkstra 堆优化算法、贪心算法、动态维护中位数等。

#### 2.5.3 注意事项
1.  **仅堆顶可读**：无法通过下标访问中间元素。
2.  **堆中元素不可直接修改**：
```cpp
pque[1] = 2;   // 错误！
pque.top() = 1; // 错误！只读。
```
若确需修改堆顶元素，需要取出、修改后重新入堆：
```cpp
int tp = pque.top(); pque.pop();
pque.push(tp + 1);
```

---

### 2.6 集合 `set`
`#include <set>`  
底层基于**红黑树**（自平衡二叉搜索树）实现，提供对数时间内插入、删除与查找的高效集合。

#### 2.6.1 集合特性对比
| 集合类型 | 互异性 (去重) | 有序性 (自动排序) | 底层结构 | 增删查复杂度 |
| :--- | :--- | :--- | :--- | :--- |
| `set` | ✔ 有 | ✔ 有（默认从小到大） | 红黑树 | $O(\log N)$ |
| `multiset` | ❌ 无 (可存重复值) | ✔ 有（默认从小到大） | 红黑树 | $O(\log N)$ |
| `unordered_set` | ✔ 有 | ❌ 无 | 哈希表 | 平均 $O(1)$，最坏 $O(N)$ |

#### 2.6.2 常用方法
##### 1) 构造函数
```cpp
set<int> st1;               // 默认从小到大
set<int, greater<int>> st2; // 显式设定从大到小
```

##### 2) 遍历方式
*   **基于迭代器遍历：**
```cpp
for (set<int>::iterator it = st.begin(); it != st.end(); ++it)
    cout << *it << endl;
```
*   **基于范围的 `for` 循环（C++11 推荐）：**
```cpp
for (auto &ele : st)
    cout << ele << endl;
```

#### 2.6.3 适用情形
*   数据去重与自动排序。
*   **大值域标记**：当元素取值范围极大（如 $10^9$）且比较稀疏，无法使用 `vis` 数组标记是否出现过时，可使用 `set`。

#### 2.6.4 注意事项
1.  **无下标索引**：无法使用 `st[0]` 访问元素。
2.  **元素只读**：`set` 的迭代器返回的是 `const` 引用，无法直接修改其值。若需要修改，必须先 `erase` 原有元素，再 `insert` 新元素。
3.  **不可用迭代器进行下标距离运算**：`set` 的迭代器是非随机访问迭代器，不支持 `it - st.begin()` 这种减法操作。若需要求距离，必须使用 `std::distance(st.begin(), it)`（其复杂度为 $O(N)$，需谨慎使用）。

---

### 2.7 映射 `map`
`#include <map>`  
底层基于**红黑树**实现的有序键值对 (key-value) 容器。

#### 2.7.1 映射特性对比
| 映射类型 | 键互异性 | 有序性 (按键排序) | 底层结构 | 增删查改复杂度 |
| :--- | :--- | :--- | :--- | :--- |
| `map` | ✔ 有 | ✔ 有（默认键从小到大） | 红黑树 | $O(\log N)$ |
| `multimap` | ❌ 无 (可重复键) | ✔ 有（默认键从小到大） | 红黑树 | $O(\log N)$ |
| `unordered_map` | ✔ 有 | ❌ 无 | 哈希表 | 平均 $O(1)$，最坏 $O(N)$ |

#### 2.7.2 常用方法
##### 1) 遍历方式
*   **传统迭代器遍历：**
```cpp
for (map<int, int>::iterator it = mp.begin(); it != mp.end(); ++it)
    cout << it->first << ' ' << it->second << endl; // first为键，second为值
```
*   **结构化绑定 + 范围遍历（C++17 推荐）：**
```cpp
for (auto &[key, val] : mp)
    cout << key << ' ' << val << endl;
```

##### 2) 常用成员函数
| 作用 | 用法 | 示例 | 时间复杂度 |
| :--- | :--- | :--- | :--- |
| **增/改/查** | 中括号 `[]` | `mp[1] = 2;` | $O(\log N)$ |
| **查找(返回迭代器)** | `.find(键)` | `auto it = mp.find(1);` | $O(\log N)$ |
| **删除** | `.erase(键)` | `mp.erase(2);` | $O(\log N)$ |
| **判断键是否存在** | `.count(键)` | `if(mp.count(3))` | $O(\log N)$ |

#### 2.7.3 适用情形
*   建立并维护复杂的映射关系。
*   例如统计各种字符串（其长度可能很长）的出现次数：`map<string, int> mp`。

#### 2.7.4 注意事项
1.  **中括号访问会触发默认插入**：若使用 `mp[key]` 访问一个不存在的键，`map` 会自动插入该键，并将对应的值初始化为默认值（如数值类型初始化为 `0`）。
```cpp
map<char, int> mp;
cout << mp.count('a') << endl; // 输出 0
mp['a'];                       // 触发了默认插入，等价于 mp['a'] = 0
cout << mp.count('a') << endl; // 输出 1
```
为了避免不必要的插入，查找键是否存在时应使用 `.count()` 或 `.find()`。
2.  **不支持迭代器下标减法**：与 `set` 一致，`map` 迭代器不能直接相减求下标。

---

### 2.8 字符串 `string`
`#include <string>`  
C++ 对传统字符数组 `char[]` 的高级封装，提供了安全且丰富的字符串操作。

#### 2.8.1 常用方法
##### 1) 构造函数
```cpp
string s1;           // 构造空字符串
string s2 = "awa!";  // 直接赋值构造
string s3(10, '6');  // 构造包含 10 个 '6' 的字符串，即 "6666666666"
```

##### 2) 输入输出
*   **C++ 风格流输入输出：**
```cpp
string s;
cin >> s;
cout << s;
```
*   **与 C 风格输入输出对接（在需要高速 I/O 时）：**
```cpp
string s;
char buf[100];
scanf("%s", buf);
s = buf;
printf("%s\n", s.c_str()); // 使用 .c_str() 转换成 const char*
```

##### 3) 成员函数与操作
| 作用 | 用法 | 示例 | 时间复杂度 |
| :--- | :--- | :--- | :--- |
| **随机访问字符** | `[]` | `s[1] = 'a';` | $O(1)$ |
| **判断相等** | `==` | `if (s1 == s2)` | $O(N)$ |
| **拼接字符/串** | `+=` | `s += "awa";` | 均摊 $O(M)$ |
| **拼接(产生临时量)** | `+` | `string s3 = s1 + s2;` | $O(N + M)$ |
| **提取子串** | `.substr(pos, len)` | `string sub = s.substr(2, 5);` | $O(len)$ |
| **查找子串** | `.find(str, pos)` | `int idx = s.find("awa");` | $O(N \times M)$（暴力实现） |

#### 2.8.2 适用情形
*   所有涉及字符串操作的场景。建议优先使用 `string`，其自动扩容与安全管理能有效规避数组越界等问题。

#### 2.8.3 注意事项
1.  **拼接字符串首选 `+=`**：`s += "a"` 是原地追加；而 `s = s + "a"` 会先生成一个临时的 `string` 对象进行拷贝，在长字符串或高频循环中极易导致时间超限 (TLE)。

```cpp
// 优化前：耗时约 15139ms
string s;
for (int i = 0; i < 5e5; i++)
    s = s + "a";

// 优化后：耗时 < 1ms
string s;
for (int i = 0; i < 5e5; i++)
    s += "a";
```

2.  **`.substr(pos, len)` 参数的意义**：第二个参数是**子串的长度**，而不是结束位置的下标，请注意与 Java/Go 等语言作区分。
3.  **`.find()` 的复杂度**：标准库的 `.find()` 属于高常数暴力匹配，最坏时间复杂度为 $O(N \times M)$。若面临严苛的单串匹配，需手写 KMP 或 Aho-Corasick 自动机。

---

### 2.9 二元组 `pair`
`#include <utility>`  
用于将两个不同或相同类型的值绑定在一起。

#### 2.9.1 常用方法
##### 1) 构造与赋值
```cpp
pair<int, char> p1 = make_pair(1, 'a'); // C++98 经典写法
pair<int, char> p2 = {1, 'a'};           // C++11 列表初始化
```

##### 2) 获取元素
*   **标准访问**：通过 `.first` 和 `.second` 访问：
```cpp
pair<int, char> pr = {1, 'a'};
int a = pr.first;
char b = pr.second;
```
*   **结构化绑定（C++17 推荐）**：
```cpp
auto &[a, b] = pr;
```

##### 3) 比较运算
*   默认支持 `==`, `!=`, `<`, `>`, `<=`, `>=`。
*   **比较规则**：先比较 `first`，若 `first` 相等，则比较 `second`。

#### 2.9.2 适用场景
*   需要将两个有关联的变量组合在一起时（例如坐标点 $(x, y)$，带权图的边权与邻接点 `pair<weight, to>` 等）。

---

## 3. 迭代器简介

### 3.1 迭代器是什么？
迭代器 (Iterator) 是一种行为类似于指针的对象，它提供了一种通用的方式来访问容器中的元素，而无需暴露容器的内部表示。

```cpp
// 1. 通过下标遍历 vector
for (int i = 0; i < a.size(); i++)
    cout << a[i] << endl;

// 2. 通过迭代器遍历 vector
for (vector<int>::iterator it = a.begin(); it != a.end(); ++it)
    cout << *it << endl;
```
*   `a.begin()` 指向容器中第一个元素。
*   `a.end()` 指向容器中**最后一个元素的下一个位置**（通常称为哨兵位，不可解引用）。
*   通过 `*it` 对迭代器解引用，即可获取其指向的元素。

### 3.2 为什么需要迭代器？
非线性结构（如基于红黑树的 `set` / `map`）由于内存不连续且不具备下标概念，无法通过 `a[i]` 遍历。此时迭代器便充当了统一的访问接口。
```cpp
for (set<int>::iterator it = st.begin(); it != st.end(); ++it)
    cout << *it << endl;
```

### 3.3 常用迭代器操作
针对 `vector` 等随机访问容器，迭代器支持的操作最为丰富：
*   `it + n` / `it - n`：迭代器向后/向前移动 $n$ 个位置。
*   `it1 - it2`：计算两个迭代器之间的元素距离。
*   `prev(it)` / `next(it)`：获取 `it` 的前驱或后继迭代器。

### 3.4 常见避坑点
1.  **`.end()` 指向的位置不可读写**：它是不含有效数据的哨兵，解引用会导致未定义行为。
2.  **迭代器失效**：在遍历容器的过程中，若对容器进行了插入或删除操作，当前的迭代器可能会失效，导致运行时错误（RE）。
```cpp
// 错误示例：擦除元素后迭代器失效，且 it 递增跳过了紧随其后的元素
vector<int> a{1, 2, 3, 4};
for (auto it = a.begin(); it != a.end(); ++it) {
    if (*it == 2 || *it == 3)
        a.erase(it); // 调用 erase 会使 it 失效，且下一轮循环 ++it 可能会越界
}
```
*   **建议**：若无必要，尽量避免在遍历过程中直接用迭代器修改/删除容器元素。如果确需删除，应使用 `erase` 返回的下一个有效迭代器更新当前迭代器。

---

## 4. 常用算法

### 4.1 交换 `swap()`
交换两个变量的内容。
*   **时间复杂度**：$O(1)$
```cpp
int a = 0, b = 1;
swap(a, b); // a = 1, b = 0
```
*   **注意**：参数为引用传递，无需显式取地址。

---

### 4.2 排序 `sort()`
对随机访问序列进行排序。
*   **时间复杂度**：$O(N \log N)$
```cpp
vector<int> arr{1, 9, 1, 9, 8, 1, 0};
sort(arr.begin(), arr.end()); // 默认升序：[0, 1, 1, 1, 8, 9, 9]

// 使用 greater 比较器进行降序排序
sort(arr.begin(), arr.end(), greater<int>()); // [9, 9, 8, 1, 1, 1, 0]
```

##### 自定义比较器
比较器必须满足 **严格弱序 (Strict Weak Ordering)**。即：若 `a == b`，比较器必须返回 `false`。
```cpp
// 规则：第二关键字升序，若第二关键字相同，则第一关键字降序
bool cmp(pair<int, int> a, pair<int, int> b) {
    if (a.second != b.second)
        return a.second < b.second;
    return a.first > b.first;
}

int main() {
    vector<pair<int, int>> arr{{1, 9}, {2, 9}, {8, 1}, {0, 0}};
    sort(arr.begin(), arr.end(), cmp);
    // 排序后: [(0, 0), (8, 1), (2, 9), (1, 9)]
}
```

---

### 4.3 二分查找 `lower_bound()` / `upper_bound()`
在**已升序排序**的容器内应用二分查找。若找不到目标值，返回指向合适插入位置的迭代器。
*   `lower_bound()`: 寻找 **首个大于等于 ($\ge$)** 目标值的元素位置。
*   `upper_bound()`: 寻找 **首个严格大于 ($>$)** 目标值的元素位置。
*   **时间复杂度**：$O(\log N)$

```cpp
vector<int> arr{0, 1, 1, 1, 8, 9, 9};
// 查找 7 的下界，得到的是元素 8 的位置
int idx = lower_bound(arr.begin(), arr.end(), 7) - arr.begin(); // idx = 4
```

##### 快捷速查（针对升序序列）：
*   大于等于 $x$ 的第一个元素下标：`lower_bound(..., x) - begin()`
*   大于 $x$ 的第一个元素下标：`upper_bound(..., x) - begin()`
*   小于等于 $x$ 的最后一个元素下标：`upper_bound(..., x) - begin() - 1`
*   小于 $x$ 的最后一个元素下标：`lower_bound(..., x) - begin() - 1`

---

### 4.4 反转 `reverse()`
原地反转一个容器或数组的部分区间。
*   **时间复杂度**：$O(N)$
```cpp
vector<int> arr{1, 2, 3, 4, 5};
reverse(arr.begin(), arr.end()); // arr = [5, 4, 3, 2, 1]
```

---

### 4.5 最值 `max()` / `min()`
返回参数中的最大值/最小值。
*   **时间复杂度**：$O(1)$
```cpp
// C++11 支持通过初始化列表一次性传入多个元素
int mx = max({1, 5, 3, 9, 2}); // mx = 9
```

---

### 4.6 邻域去重 `unique()`
消除数组中**相邻**的重复元素。常用于**离散化（Coordinate Compression）**。
*   **注意**：`unique` 不会缩减容器的物理长度，而是将重复元素移到末尾，并返回一个指向“去重后有效区域结尾”的迭代器。
*   **时间复杂度**：$O(N)$

##### 标准离散化去重写法：
```cpp
vector<int> arr{1, 2, 1, 4, 5, 4, 4};
sort(arr.begin(), arr.end()); // 先排序，确保重复元素相邻
arr.erase(unique(arr.begin(), arr.end()), arr.end()); // 擦除多余无效数据
// 去重后 arr = [1, 2, 4, 5]
```

---

### 4.7 数学函数 `<cmath>`
以下函数的参数与返回值通常为浮点数类型（如 `double`）。

| 函数 | 功能 | 示例 |
| :--- | :--- | :--- |
| `abs(x)` | 绝对值 | `abs(-1.5)` $\rightarrow 1.5$ |
| `exp(x)` | 指数 $e^x$ | `exp(1)` $\rightarrow 2.71828...$ |
| `log(x)` | 自然对数 $\ln(x)$ | `log(2.71828)` $\rightarrow 1$ |
| `pow(x, y)` | 幂运算 $x^y$ | `pow(2, 3)` $\rightarrow 8.0$ |
| `sqrt(x)` | 平方根 $\sqrt{x}$ | `sqrt(4)` $\rightarrow 2.0$ |
| `ceil(x)` | 向上取整 | `ceil(2.1)` $\rightarrow 3.0$ |
| `floor(x)` | 向下取整 | `floor(2.9)` $\rightarrow 2.0$ |
| `round(x)` | 四舍五入 (C++11) | `round(2.5)` $\rightarrow 3.0$ |

#### ⚠️ 竞赛避坑防 WA 指南（整型运算代替浮点运算）
浮点数运算存在精度误差，在整数问题中，应尽量避免使用浮点数学函数：
1.  **向下整除**：
    *   *别用*：`floor(1.0 * a / b)`
    *   *应写为*：`a / b` (若 $a, b > 0$)
2.  **向上整除**：
    *   *别用*：`ceil(1.0 * a / b)`
    *   *应写为*：`(a + b - 1) / b` (若 $a, b > 0$)
3.  **开平方根取整**：
    *   *别用*：`(int)sqrt(a)` （因为误差可能导致 $4$ 开方得到 $1.999999$，强转变为 $1$）
    *   *应写为*：整数二分查找，或利用极其微小的偏差校正：`int r = sqrt(a) + 0.5; if (r * r > a) r--;`
4.  **快速幂**：
    *   *别用*：`pow(a, b)`
    *   *应手写*：快速幂算法（支持大数取模，且绝无精度失真）
5.  **求二进制最高有效位**（以 2 为底的对数）：
    *   *别用*：`log2(a)`
    *   *应写为*：GCC 内置函数 `__lg(a)`（速度极快）或 C++20 `std::bit_width`

---

### 4.8 最大公因数与最小公倍数 `gcd()` / `lcm()` (C++17)
`#include <numeric>`  
*   在 C++17 中，标准库提供了快速求最大公约数与最小公倍数的函数：
```cpp
int x = gcd(8, 12); // x = 4
int y = lcm(8, 12); // y = 24
```
*   **兼容性**：若编译器不支持 C++17，但在 GNU (g++) 环境下，可以使用内置函数 `__gcd(a, b)`。
*   **备用手写方案**：
```cpp
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b) {
    return a / gcd(a, b) * b; // 先除后乘，防止中间结果溢出
}
```

C++ STL 算法竞赛常用用法讲义

C++ 标准模板库 (STL, Standard Template Library) 是包含常用数据结构与算法模板的 C++ 软件库。它主要包含四个组件：容器 (Containers)、算法 (Algorithms)、迭代器 (Iterators)、仿函数 (Functors)。

算法示例：sort(a.begin(), a.end())
容器示例：priority_queue<int> pque
仿函数示例：greater<int>()
迭代器示例：vector<int>::iterator it = a.begin()

1. 前言

但在实际竞赛中，需要权衡 STL 的利弊。由于 STL 考虑了通用性与安全性，其运行效率在某些极端情况下可能不如针对特定题目手写的数据结构（如手写栈、手写双指针等）。因此，STL 的使用有时是用运行常数换取编程效率，具体的取舍需要结合题目时限与个人经验来决定。

2. 常用容器

2.1 内容总览

下表列出了算法竞赛中常见的容器。标记 [x] 的为本讲义详细讲解的核心容器。

分类	容器名称	竞赛推荐度
顺序容器	`[x] vector` (向量)	必学
	`[ ] deque` (双端队列) / `list` (双向链表)	了解即可
关联容器	`[x] set` (集合) / `[x] map` (映射)	必学
	`[ ] multiset` (多重集合) / `multimap`	建议掌握
无序关联容器	`[ ] unordered_set` / `unordered_map`	建议掌握 (常数小但最坏 $O(N)$)
容器适配器	`[x] stack` (栈) / `[x] queue` (队列)	必学
	`[x] priority_queue` (优先队列/堆)	必学
字符串	`[x] string` (字符串)	必学
元组	`[x] pair` (二元组) / `[ ] tuple` (多元组)	必学

2.2 向量 `vector`

#include <vector>
基于连续内存的顺序存储结构（类似动态数组），支持动态扩容。

2.2.1 常用方法

1) 构造函数

vector<类型> arr(长度, [初值])
时间复杂度：$O(N)$

vector<int> arr;         // 构造一个空数组
vector<int> arr(100);    // 构造初始长度为 100 的数组，默认初值为 0
vector<int> arr(100, 1); // 构造初始长度为 100 的数组，初值均设为 1

vector<vector<int>> mat(100, vector<int>());       // 构造 100 行，列数动态的二维数组
vector<vector<int>> mat(100, vector<int>(666, -1)); // 构造 100 行 666 列的二维数组，初值为 -1

注意（避坑写法）：

vector<int> arr[100];         // 正确：构造了 100 个 vector 对象组成的静态数组，常用于邻接表存图
vector<int> arr[100](100, 1); // 语法错误！

2) 尾接与尾删

.push_back(元素)：在 vector 尾部插入一个元素，数组长度增加 1。
.pop_back()：删除 vector 尾部的一个元素，数组长度减少 1。
时间复杂度：均摊 $O(1)$

// 初始化: arr = []
arr.push_back(1); // arr = [1]
arr.push_back(2); // arr = [1, 2]
arr.pop_back();   // arr = [1]

3) 中括号运算符 `[]`

支持通过下标随机访问元素，与普通静态数组一致。
时间复杂度：$O(1)$

4) 获取长度与判空

.size()：获取当前元素数量。时间复杂度：$O(1)$
.empty()：若为空返回 true，否则返回 false。时间复杂度：$O(1)$

5) 清空

.clear()：清空容器内所有元素。
时间复杂度：$O(N)$（因为需要析构容器内的元素）

6) 改变长度

.resize(新长度, [默认值])：修改 vector 的长度。
- 若新长度小于当前长度，则截断多余元素。
- 若新长度大于当前长度，则用默认值填充新位置（旧元素保持不变）。
- 时间复杂度：$O(N)$

2.2.2 适用情形

在多数场景下可以替代普通数组（除非题目对时空常数有极其苛刻的要求）。
解决稀疏矩阵或大内存问题：例如面对一个 $N \times M$ 的矩阵，若 $N, M \le 10^5$ 且实际有效元素（非零元素或总查询）数量较少。直接开静态二维数组 int mat[100010][100010] 会导致内存超限 (MLE)。此时使用 vector<vector<int>> 或邻接表方式可动态按需分配空间。
vector 申请的空间在堆上，不容易出现局部静态数组导致的栈溢出。

2.2.3 注意事项

提前指定长度：若已知所需的数组长度，建议直接在构造函数中指定，或使用 .reserve(容量) 提前保留空间。避免因频繁 .push_back() 导致底层数组频繁重新分配内存和拷贝。

// 优化前: 耗时约 522ms
vector<int> a;
for (int i = 0; i < 1e8; i++)
    a.push_back(i);

// 优化后: 耗时约 259ms
vector<int> a(1e8);
for (int i = 0; i < a.size(); i++)
    a[i] = i;

小心 size_t 溢出：.size() 返回的是 size_t 类型（无符号整数）。在 32 位环境下，其最大值为 $2^{32}-1$。

vector<int> a(65536);
// a.size() * a.size() 会在 size_t 范围内计算，由于 65536 * 65536 = 2^32，直接溢出变成 0
long long area = a.size() * a.size();

2.3 栈 `stack`

#include <stack>
通过封装底层容器（默认是 std::deque），实现后进先出 (LIFO) 的数据结构。

2.3.1 常用方法

作用	用法	示例	时间复杂度
构造	`stack<类型> stk`	`stack<int> stk;`	$O(1)$
入栈	`.push(元素)`	`stk.push(1);`	$O(1)$
出栈	`.pop()`	`stk.pop();`	$O(1)$
取栈顶	`.top()`	`int val = stk.top();`	$O(1)$
判空	`.empty()`	`stk.empty();`	$O(1)$
大小	`.size()`	`stk.size();`	$O(1)$

2.3.2 适用情形

用于括号匹配、单调栈、深度优先搜索（非递归 DFS）等场景。
如果不卡常数，可以直接使用。也可以直接用 vector 模拟栈：vector 的 .back() 相当于 .top()，.push_back() 相当于 .push()，.pop_back() 相当于 .pop()。

2.3.3 注意事项

不可随机访问或遍历内部元素：以下用法均为编译错误。

for (int i = 0; i < stk.size(); i++) cout << stk[i] << endl; // 错误！
for (auto ele : stk) cout << ele << endl;                   // 错误！

2.4 队列 `queue`

#include <queue>
基于先进先出 (FIFO) 原理的数据结构。

2.4.1 常用方法

作用	用法	示例	时间复杂度
构造	`queue<类型> que`	`queue<int> que;`	$O(1)$
入队	`.push(元素)`	`que.push(1);`	$O(1)$
出队	`.pop()`	`que.pop();`	$O(1)$
取队首	`.front()`	`int val = que.front();`	$O(1)$
取队尾	`.back()`	`int val = que.back();`	$O(1)$
判空	`.empty()`	`que.empty();`	$O(1)$
大小	`.size()`	`que.size();`	$O(1)$

2.4.2 适用情形

常用于广度优先搜索 (BFS) 算法。

2.4.3 注意事项

同样不可遍历内部元素：

for (int i = 0; i < que.size(); i++) cout << que[i] << endl; // 错误！
for (auto ele : que) cout << ele << endl;                   // 错误！

2.5 优先队列 `priority_queue`

#include <queue>
底层基于二叉堆实现，支持在 $O(\log N)$ 时间内插入/删除元素，并在 $O(1)$ 时间内查询最值（堆顶元素）。

2.5.1 常用方法

1) 构造函数

priority_queue<类型, 容器, 比较器> * 类型：存储的数据类型 * 容器：底层的存储容器（竞赛中一般用默认的 vector<类型>） * 比较器：确定优先级的规则。默认是 less<类型>（即大顶堆，最大值在堆顶）；若指定为 greater<类型> 则为小顶堆（最小值在堆顶）。

priority_queue<int> pque1;                            // 大顶堆
priority_queue<int, vector<int>, greater<int>> pque2; // 小顶堆

2) 成员函数

作用	用法	示例	时间复杂度
入堆	`.push(元素)`	`pque.push(1);`	$O(\log N)$
出堆	`.pop()`	`pque.pop();`	$O(\log N)$
取堆顶	`.top()`	`int a = pque.top();`	$O(1)$
大小	`.size()`	`pque.size();`	$O(1)$
判空	`.empty()`	`pque.empty();`	$O(1)$

2.5.2 适用情形

持续维护动态有序性：需要频繁插入大小不定的元素，且随时需要取出其中最大/最小的元素。
常用于 Dijkstra 堆优化算法、贪心算法、动态维护中位数等。

2.5.3 注意事项

仅堆顶可读：无法通过下标访问中间元素。
堆中元素不可直接修改：

pque[1] = 2;   // 错误！
pque.top() = 1; // 错误！只读。

若确需修改堆顶元素，需要取出、修改后重新入堆：

int tp = pque.top(); pque.pop();
pque.push(tp + 1);

2.6 集合 `set`

#include <set>
底层基于红黑树（自平衡二叉搜索树）实现，提供对数时间内插入、删除与查找的高效集合。

2.6.1 集合特性对比

集合类型	互异性 (去重)	有序性 (自动排序)	底层结构	增删查复杂度
`set`	✔ 有	✔ 有（默认从小到大）	红黑树	$O(\log N)$
`multiset`	❌ 无 (可存重复值)	✔ 有（默认从小到大）	红黑树	$O(\log N)$
`unordered_set`	✔ 有	❌ 无	哈希表	平均 $O(1)$，最坏 $O(N)$

2.6.2 常用方法

1) 构造函数

set<int> st1;               // 默认从小到大
set<int, greater<int>> st2; // 显式设定从大到小

2) 遍历方式

基于迭代器遍历：

for (set<int>::iterator it = st.begin(); it != st.end(); ++it)
    cout << *it << endl;

基于范围的 for 循环（C++11 推荐）：

for (auto &ele : st)
    cout << ele << endl;

3) 常用成员函数

作用	用法	示例	时间复杂度
插入	`.insert(元素)`	`st.insert(1);`	$O(\log N)$
删除指定值	`.erase(元素)`	`st.erase(2);`	$O(\log N)$
删除指定迭代器	`.erase(迭代器)`	`st.erase(st.begin());`	$O(1)$（均摊）
查找元素	`.find(元素)`	`auto it = st.find(1);`（未找到返回 `st.end()`）	$O(\log N)$
计数/判断存在	`.count(元素)`	`if(st.count(3))`	$O(\log N)$

2.6.3 适用情形

数据去重与自动排序。
大值域标记：当元素取值范围极大（如 $10^9$）且比较稀疏，无法使用 vis 数组标记是否出现过时，可使用 set。

2.6.4 注意事项

无下标索引：无法使用 st[0] 访问元素。
元素只读：set 的迭代器返回的是 const 引用，无法直接修改其值。若需要修改，必须先 erase 原有元素，再 insert 新元素。
不可用迭代器进行下标距离运算：set 的迭代器是非随机访问迭代器，不支持 it - st.begin() 这种减法操作。若需要求距离，必须使用 std::distance(st.begin(), it)（其复杂度为 $O(N)$，需谨慎使用）。

2.7 映射 `map`

#include <map>
底层基于红黑树实现的有序键值对 (key-value) 容器。

2.7.1 映射特性对比

映射类型	键互异性	有序性 (按键排序)	底层结构	增删查改复杂度
`map`	✔ 有	✔ 有（默认键从小到大）	红黑树	$O(\log N)$
`multimap`	❌ 无 (可重复键)	✔ 有（默认键从小到大）	红黑树	$O(\log N)$
`unordered_map`	✔ 有	❌ 无	哈希表	平均 $O(1)$，最坏 $O(N)$

2.7.2 常用方法

1) 遍历方式

传统迭代器遍历：

for (map<int, int>::iterator it = mp.begin(); it != mp.end(); ++it)
    cout << it->first << ' ' << it->second << endl; // first为键，second为值

结构化绑定 + 范围遍历（C++17 推荐）：

for (auto &[key, val] : mp)
    cout << key << ' ' << val << endl;

2) 常用成员函数

作用	用法	示例	时间复杂度
增/改/查	中括号 `[]`	`mp[1] = 2;`	$O(\log N)$
查找(返回迭代器)	`.find(键)`	`auto it = mp.find(1);`	$O(\log N)$
删除	`.erase(键)`	`mp.erase(2);`	$O(\log N)$
判断键是否存在	`.count(键)`	`if(mp.count(3))`	$O(\log N)$

2.7.3 适用情形

建立并维护复杂的映射关系。
例如统计各种字符串（其长度可能很长）的出现次数：map<string, int> mp。

2.7.4 注意事项

中括号访问会触发默认插入：若使用 mp[key] 访问一个不存在的键，map 会自动插入该键，并将对应的值初始化为默认值（如数值类型初始化为 0）。

map<char, int> mp;
cout << mp.count('a') << endl; // 输出 0
mp['a'];                       // 触发了默认插入，等价于 mp['a'] = 0
cout << mp.count('a') << endl; // 输出 1

为了避免不必要的插入，查找键是否存在时应使用 .count() 或 .find()。 2. 不支持迭代器下标减法：与 set 一致，map 迭代器不能直接相减求下标。

2.8 字符串 `string`

#include <string>
C++ 对传统字符数组 char[] 的高级封装，提供了安全且丰富的字符串操作。

2.8.1 常用方法

1) 构造函数

string s1;           // 构造空字符串
string s2 = "awa!";  // 直接赋值构造
string s3(10, '6');  // 构造包含 10 个 '6' 的字符串，即 "6666666666"

2) 输入输出

C++ 风格流输入输出：

string s;
cin >> s;
cout << s;

与 C 风格输入输出对接（在需要高速 I/O 时）：

string s;
char buf[100];
scanf("%s", buf);
s = buf;
printf("%s\n", s.c_str()); // 使用 .c_str() 转换成 const char*

3) 成员函数与操作

作用	用法	示例	时间复杂度
随机访问字符	`[]`	`s[1] = 'a';`	$O(1)$
判断相等	`==`	`if (s1 == s2)`	$O(N)$
拼接字符/串	`+=`	`s += "awa";`	均摊 $O(M)$
拼接(产生临时量)	`+`	`string s3 = s1 + s2;`	$O(N + M)$
提取子串	`.substr(pos, len)`	`string sub = s.substr(2, 5);`	$O(len)$
查找子串	`.find(str, pos)`	`int idx = s.find("awa");`	$O(N \times M)$（暴力实现）

4) 数值与字符串互转 (C++11)

转换方向	目标类型	函数
数值 $\rightarrow$ `string`	`string`	`to_string(val)`
`string` $\rightarrow$ 数值	`int`	`stoi(s)`
	`long long`	`stoll(s)`
	`float`	`stof(s)`
	`double`	`stod(s)`

2.8.2 适用情形

所有涉及字符串操作的场景。建议优先使用 string，其自动扩容与安全管理能有效规避数组越界等问题。

2.8.3 注意事项

拼接字符串首选 +=：s += "a" 是原地追加；而 s = s + "a" 会先生成一个临时的 string 对象进行拷贝，在长字符串或高频循环中极易导致时间超限 (TLE)。

// 优化前：耗时约 15139ms
string s;
for (int i = 0; i < 5e5; i++)
    s = s + "a";

// 优化后：耗时 < 1ms
string s;
for (int i = 0; i < 5e5; i++)
    s += "a";

.substr(pos, len) 参数的意义：第二个参数是子串的长度，而不是结束位置的下标，请注意与 Java/Go 等语言作区分。
.find() 的复杂度：标准库的 .find() 属于高常数暴力匹配，最坏时间复杂度为 $O(N \times M)$。若面临严苛的单串匹配，需手写 KMP 或 Aho-Corasick 自动机。

2.9 二元组 `pair`

#include <utility>
用于将两个不同或相同类型的值绑定在一起。

2.9.1 常用方法

1) 构造与赋值

pair<int, char> p1 = make_pair(1, 'a'); // C++98 经典写法
pair<int, char> p2 = {1, 'a'};           // C++11 列表初始化

2) 获取元素

标准访问：通过 .first 和 .second 访问：

pair<int, char> pr = {1, 'a'};
int a = pr.first;
char b = pr.second;

结构化绑定（C++17 推荐）：

auto &[a, b] = pr;

3) 比较运算

默认支持 ==, !=, <, >, <=, >=。
比较规则：先比较 first，若 first 相等，则比较 second。

2.9.2 适用场景

需要将两个有关联的变量组合在一起时（例如坐标点 $(x, y)$，带权图的边权与邻接点 pair<weight, to> 等）。

3. 迭代器简介

3.1 迭代器是什么？

迭代器 (Iterator) 是一种行为类似于指针的对象，它提供了一种通用的方式来访问容器中的元素，而无需暴露容器的内部表示。

// 1. 通过下标遍历 vector
for (int i = 0; i < a.size(); i++)
    cout << a[i] << endl;

// 2. 通过迭代器遍历 vector
for (vector<int>::iterator it = a.begin(); it != a.end(); ++it)
    cout << *it << endl;

a.begin() 指向容器中第一个元素。
a.end() 指向容器中最后一个元素的下一个位置（通常称为哨兵位，不可解引用）。
通过 *it 对迭代器解引用，即可获取其指向的元素。

3.2 为什么需要迭代器？

非线性结构（如基于红黑树的 set / map）由于内存不连续且不具备下标概念，无法通过 a[i] 遍历。此时迭代器便充当了统一的访问接口。

for (set<int>::iterator it = st.begin(); it != st.end(); ++it)
    cout << *it << endl;

3.3 常用迭代器操作

针对 vector 等随机访问容器，迭代器支持的操作最为丰富： * it + n / it - n：迭代器向后/向前移动 $n$ 个位置。 * it1 - it2：计算两个迭代器之间的元素距离。 * prev(it) / next(it)：获取 it 的前驱或后继迭代器。

3.4 常见避坑点

.end() 指向的位置不可读写：它是不含有效数据的哨兵，解引用会导致未定义行为。
迭代器失效：在遍历容器的过程中，若对容器进行了插入或删除操作，当前的迭代器可能会失效，导致运行时错误（RE）。

// 错误示例：擦除元素后迭代器失效，且 it 递增跳过了紧随其后的元素
vector<int> a{1, 2, 3, 4};
for (auto it = a.begin(); it != a.end(); ++it) {
    if (*it == 2 || *it == 3)
        a.erase(it); // 调用 erase 会使 it 失效，且下一轮循环 ++it 可能会越界
}

建议：若无必要，尽量避免在遍历过程中直接用迭代器修改/删除容器元素。如果确需删除，应使用 erase 返回的下一个有效迭代器更新当前迭代器。

4. 常用算法

4.1 交换 `swap()`

交换两个变量的内容。 * 时间复杂度：$O(1)$

int a = 0, b = 1;
swap(a, b); // a = 1, b = 0

注意：参数为引用传递，无需显式取地址。

4.2 排序 `sort()`

对随机访问序列进行排序。 * 时间复杂度：$O(N \log N)$

vector<int> arr{1, 9, 1, 9, 8, 1, 0};
sort(arr.begin(), arr.end()); // 默认升序：[0, 1, 1, 1, 8, 9, 9]

// 使用 greater 比较器进行降序排序
sort(arr.begin(), arr.end(), greater<int>()); // [9, 9, 8, 1, 1, 1, 0]

自定义比较器

比较器必须满足 严格弱序 (Strict Weak Ordering)。即：若 a == b，比较器必须返回 false。

// 规则：第二关键字升序，若第二关键字相同，则第一关键字降序
bool cmp(pair<int, int> a, pair<int, int> b) {
    if (a.second != b.second)
        return a.second < b.second;
    return a.first > b.first;
}

int main() {
    vector<pair<int, int>> arr{{1, 9}, {2, 9}, {8, 1}, {0, 0}};
    sort(arr.begin(), arr.end(), cmp);
    // 排序后: [(0, 0), (8, 1), (2, 9), (1, 9)]
}

4.3 二分查找 `lower_bound()` / `upper_bound()`

在已升序排序的容器内应用二分查找。若找不到目标值，返回指向合适插入位置的迭代器。 * lower_bound(): 寻找 首个大于等于 ($\ge$) 目标值的元素位置。 * upper_bound(): 寻找 首个严格大于 ($>$) 目标值的元素位置。 * 时间复杂度：$O(\log N)$

vector<int> arr{0, 1, 1, 1, 8, 9, 9};
// 查找 7 的下界，得到的是元素 8 的位置
int idx = lower_bound(arr.begin(), arr.end(), 7) - arr.begin(); // idx = 4

快捷速查（针对升序序列）：

大于等于 $x$ 的第一个元素下标：lower_bound(..., x) - begin()
大于 $x$ 的第一个元素下标：upper_bound(..., x) - begin()
小于等于 $x$ 的最后一个元素下标：upper_bound(..., x) - begin() - 1
小于 $x$ 的最后一个元素下标：lower_bound(..., x) - begin() - 1

4.4 反转 `reverse()`

原地反转一个容器或数组的部分区间。 * 时间复杂度：$O(N)$

vector<int> arr{1, 2, 3, 4, 5};
reverse(arr.begin(), arr.end()); // arr = [5, 4, 3, 2, 1]

4.5 最值 `max()` / `min()`

返回参数中的最大值/最小值。 * 时间复杂度：$O(1)$

// C++11 支持通过初始化列表一次性传入多个元素
int mx = max({1, 5, 3, 9, 2}); // mx = 9

4.6 邻域去重 `unique()`

消除数组中相邻的重复元素。常用于离散化（Coordinate Compression）。 * 注意：unique 不会缩减容器的物理长度，而是将重复元素移到末尾，并返回一个指向“去重后有效区域结尾”的迭代器。 * 时间复杂度：$O(N)$

标准离散化去重写法：

vector<int> arr{1, 2, 1, 4, 5, 4, 4};
sort(arr.begin(), arr.end()); // 先排序，确保重复元素相邻
arr.erase(unique(arr.begin(), arr.end()), arr.end()); // 擦除多余无效数据
// 去重后 arr = [1, 2, 4, 5]

4.7 数学函数 `<cmath>`

以下函数的参数与返回值通常为浮点数类型（如 double）。

函数	功能	示例
`abs(x)`	绝对值	`abs(-1.5)` $\rightarrow 1.5$
`exp(x)`	指数 $e^x$	`exp(1)` $\rightarrow 2.71828...$
`log(x)`	自然对数 $\ln(x)$	`log(2.71828)` $\rightarrow 1$
`pow(x, y)`	幂运算 $x^y$	`pow(2, 3)` $\rightarrow 8.0$
`sqrt(x)`	平方根 $\sqrt{x}$	`sqrt(4)` $\rightarrow 2.0$
`ceil(x)`	向上取整	`ceil(2.1)` $\rightarrow 3.0$
`floor(x)`	向下取整	`floor(2.9)` $\rightarrow 2.0$
`round(x)`	四舍五入 (C++11)	`round(2.5)` $\rightarrow 3.0$

⚠️ 竞赛避坑防 WA 指南（整型运算代替浮点运算）

浮点数运算存在精度误差，在整数问题中，应尽量避免使用浮点数学函数： 1. 向下整除： * 别用：floor(1.0 * a / b) * 应写为：a / b (若 $a, b > 0$) 2. 向上整除： * 别用：ceil(1.0 * a / b) * 应写为：(a + b - 1) / b (若 $a, b > 0$) 3. 开平方根取整： * 别用：(int)sqrt(a) （因为误差可能导致 $4$ 开方得到 $1.999999$，强转变为 $1$） * 应写为：整数二分查找，或利用极其微小的偏差校正：int r = sqrt(a) + 0.5; if (r * r > a) r--; 4. 快速幂： * 别用：pow(a, b) * 应手写：快速幂算法（支持大数取模，且绝无精度失真） 5. 求二进制最高有效位（以 2 为底的对数）： * 别用：log2(a) * 应写为：GCC 内置函数 __lg(a)（速度极快）或 C++20 std::bit_width

4.8 最大公因数与最小公倍数 `gcd()` / `lcm()` (C++17)

#include <numeric>
* 在 C++17 中，标准库提供了快速求最大公约数与最小公倍数的函数：

int x = gcd(8, 12); // x = 4
int y = lcm(8, 12); // y = 24

兼容性：若编译器不支持 C++17，但在 GNU (g++) 环境下，可以使用内置函数 __gcd(a, b)。
备用手写方案：

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b) {
    return a / gcd(a, b) * b; // 先除后乘，防止中间结果溢出
}

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