附录 A：C++ 速查手册

本附录是你的备忘单，在练习时随时参考。这里的所有内容在书中都已涵盖，这是精简的参考形式。

A.1 竞赛模板

📄 查看代码：A.1 竞赛模板 
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("problem.in", "r", stdin);   // 文件 I/O 时取消注释（使用实际题目名称）
    // freopen("problem.out", "w", stdout);  // 文件 I/O 时取消注释

    // 你的代码

    return 0;
}

A.2 常用数据类型

类型大小范围使用场景
int32 位±2.1 × 10^9默认整数
long long64 位±9.2 × 10^18大数、乘积
double64 位~15 位有效数字小数
bool1 字节true/false标志
char8 位-128 到 127单字符
string可变任意长度文本

安全最大值：

INT_MAX   = 2,147,483,647   ≈ 2.1 × 10^9
LLONG_MAX = 9,223,372,036,854,775,807 ≈ 9.2 × 10^18

A.3 STL 容器——操作速查

vector<T>

📄 查看代码：vector 
vector<int> v;              // 空向量
vector<int> v(n, 0);        // n 个零
vector<int> v = {1,2,3};    // 从列表初始化

v.push_back(x);     // 尾部追加——O(1) 均摊
v.pop_back();       // 删除最后——O(1)
v[i]                // 访问下标 i——O(1)
v.front()           // 第一个元素
v.back()            // 最后一个元素
v.size()            // 元素个数
v.empty()           // 空则返回 true
v.clear()           // 删除所有元素
v.resize(k, val)    // 调整为 k 个，新元素填充 val
v.insert(v.begin()+i, x)  // 在下标 i 处插入——O(n)
v.erase(v.begin()+i)      // 删除下标 i——O(n)

pair<A,B>

pair<int,int> p = {3, 5};
p.first             // 3
p.second            // 5
make_pair(a, b)     // 创建 pair
// 比较：先比 .first，再比 .second

map<K,V>

map<string,int> m;
m[key] = val;           // 插入/更新——O(log n)
m[key]                  // 访问（不存在时创建！）——O(log n)
m.find(key)             // 迭代器；未找到返回 .end()——O(log n)
m.count(key)            // 0 或 1——O(log n)
m.erase(key)            // 删除——O(log n)
m.size()                // 条目数
for (auto &[k,v] : m)   // 按键有序遍历

set<T>

set<int> s;
s.insert(x)             // 添加——O(log n)
s.erase(x)              // 删除所有 x——O(log n)
s.count(x)              // 0 或 1——O(log n)
s.find(x)               // 迭代器——O(log n)
s.lower_bound(x)        // 第一个 >= x 的元素
s.upper_bound(x)        // 第一个 > x 的元素
*s.begin()              // 最小元素
*s.rbegin()             // 最大元素

stack<T>

stack<int> st;
st.push(x)      // 压入——O(1)
st.pop()        // 弹出（无返回值！）——O(1)
st.top()        // 查看顶部——O(1)
st.empty()      // 空则返回 true
st.size()       // 元素数

queue<T>

queue<int> q;
q.push(x)       // 入队——O(1)
q.pop()         // 出队（无返回值！）——O(1)
q.front()       // 队首元素——O(1)
q.back()        // 队尾元素——O(1)
q.empty()
q.size()

priority_queue<T>（最大堆）

priority_queue<int> pq;                               // 最大堆
priority_queue<int, vector<int>, greater<int>> pq2;   // 最小堆

pq.push(x)      // 插入——O(log n)
pq.pop()        // 删除顶部——O(log n)
pq.top()        // 查看顶部（最大值）——O(1)
pq.empty()
pq.size()

unordered_map<K,V> / unordered_set<T>

接口与 map/set 相同，但平均 O(1)（无有序迭代）。

A.4 STL 算法速查

📄 查看代码：A.4 STL 算法速查 
// 全部假设 #include <bits/stdc++.h>

// 排序
sort(v.begin(), v.end());                          // 升序
sort(v.begin(), v.end(), greater<int>());          // 降序
sort(v.begin(), v.end(), [](int a, int b){...});   // 自定义

// 二分查找（需要已排序容器）
binary_search(v.begin(), v.end(), x)               // bool：存在吗？
lower_bound(v.begin(), v.end(), x)                 // 第一个 >= x 的迭代器
upper_bound(v.begin(), v.end(), x)                 // 第一个 > x 的迭代器

// 最小/最大值
min(a, b)               // 两者最小
max(a, b)               // 两者最大
min({a, b, c})          // 多个中最小（C++11）
*min_element(v.begin(), v.end())   // 容器最小
*max_element(v.begin(), v.end())   // 容器最大

// 累加
accumulate(v.begin(), v.end(), 0LL)   // 求和（long long 用 0LL）

// 填充
fill(v.begin(), v.end(), x)           // 全部填充 x
memset(arr, 0, sizeof(arr))           // 清零 C 数组（快速）

// 反转
reverse(v.begin(), v.end())           // 原地反转

// 统计
count(v.begin(), v.end(), x)          // 统计 x 的出现次数

// 去重（删除连续重复——先排序！）
auto it = unique(v.begin(), v.end());
v.erase(it, v.end());

// 交换
swap(a, b)              // 交换两个值

// 全排列（暴力时有用）
sort(v.begin(), v.end());
do {
    // 处理当前排列
} while (next_permutation(v.begin(), v.end()));

// GCD / LCM（C++17）
gcd(a, b)                           // 最大公约数——来自 <numeric> 的 std::gcd
lcm(a, b)                           // 最小公倍数——来自 <numeric> 的 std::lcm
// 旧版（C++17 之前）：__gcd(a, b)  // 仍然有效，但推荐用 std::gcd

A.5 时间复杂度参考表

图示：复杂度与 N 参考

Complexity Table

上面的彩色表格能让你一眼看出可行性。读题时，找到列中的 N 和行中的算法复杂度，看它是否能在 1 秒内通过。

N最大可行复杂度算法层级
N ≤ 12O(N! × N)所有排列
N ≤ 20O(2^N × N)所有子集 + 线性操作
N ≤ 500O(N³)3 重嵌套循环、区间 DP
N ≤ 5000O(N²)2 重嵌套循环、O(N²) DP
N ≤ 10^5O(N log N)排序、BFS、二分查找
N ≤ 10^6O(N)线性扫描、前缀和
N ≤ 10^8O(N) 或 O(N / 32)纯循环或位集

A.6 常见陷阱

整数溢出

📄 查看代码：整数溢出 
// 错误
int a = 1e9, b = 1e9;
int product = a * b;  // 溢出！

// 正确
long long product = (long long)a * b;

// 错误
int n = 1e5;
int arr[n * n];  // n*n = 10^10，太大了

// 检查：若中间值可能超过 2 × 10^9，用 long long

差一错误

// 错误：访问 arr[n]
for (int i = 0; i <= n; i++) cout << arr[i];

// 正确
for (int i = 0; i < n; i++) cout << arr[i];   // 0-indexed
for (int i = 1; i <= n; i++) cout << arr[i];  // 1-indexed

// 前缀和：P[i] = 前 i 个元素之和
// 查询 [L, R] 的和（1-indexed）：P[R] - P[L-1]
// 不是 P[R] - P[L]  ← 差一！

遍历时修改容器

// 错误
for (auto it = s.begin(); it != s.end(); ++it) {
    if (*it % 2 == 0) s.erase(it);  // 迭代器失效！
}

// 正确
set<int> toErase;
for (int x : s) if (x % 2 == 0) toErase.insert(x);
for (int x : toErase) s.erase(x);

map 访问时创建条目

map<string,int> m;
if (m["missing_key"])  // 创建值为 0 的 "missing_key"！

// 正确：先检查
if (m.count("missing_key") && m["missing_key"])  // 安全
// 或：
auto it = m.find("missing_key");
if (it != m.end() && it->second) { ... }

浮点数比较

double a = 0.1 + 0.2;
if (a == 0.3)  // 因浮点精度可能为 false！

// 正确：用 epsilon 比较
const double EPS = 1e-9;
if (abs(a - 0.3) < EPS) { ... }

深度递归导致栈溢出

// 大图上的 DFS 可能导致栈溢出
// 对 N = 10^5 个节点排成链的树，递归深度 = 10^5
// 修复：增大栈大小，或用迭代 DFS

// 在 Linux/Mac 上增大栈：
// ulimit -s unlimited
// 或编译时：g++ -DLOCAL ... 并手动设置栈大小

A.7 常用 #define 和 typedef

📄 查看代码：A.7 常用 #define 和 typedef 
// 常用缩写（个人喜好——不要过度使用）
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

#define pb push_back
#define all(v) (v).begin(), (v).end()
#define sz(v) ((int)(v).size())

// 用法示例：
ll x = 1e18;
pii p = {3, 5};
vi v = {1, 2, 3};
sort(all(v));

A.8 C++17 实用特性

📄 查看代码：A.8 C++17 实用特性 
// 结构化绑定——简洁地解包 pair/tuple
auto [x, y] = make_pair(3, 5);
for (auto [key, val] : mymap) { ... }

// 带初始化器的 if
if (auto it = m.find(key); it != m.end()) {
    // 使用 it->second
}

// gcd 和 lcm
int g = gcd(12, 8);   // C++17：使用 <numeric> 中的 std::gcd
int l = lcm(4, 6);    // C++17：使用 <numeric> 中的 std::lcm

// 编译：g++ -std=c++17 -O2 -o sol sol.cpp