附录 C：C++ 竞赛编程技巧
本附录收集了竞赛程序员每天使用的最有用的 C++ 技巧、宏、模板和代码片段，可以在竞赛中节省大量时间并让代码运行更快。
C.1 快速 I/O
对 I/O 密集型题目最重要的性能优化：
// 始终在 main() 开头加上这两行
ios_base::sync_with_stdio(false); // 断开 C 和 C++ I/O 流的同步
cin.tie(NULL); // 解除 cin 和 cout 的绑定
// 为什么有效：
// sync_with_stdio(false)：默认情况下 C++ 与 C I/O（printf/scanf）
// 同步以保持兼容性，关闭后 cin/cout 快得多。
// cin.tie(NULL)：默认情况下 cin 在每次读取前清空 cout，
// 解除绑定消除这个不必要的清空。
性能差异很显著——这两行应该出现在每个解法中：
文件 I/O（USACO 传统题）：
freopen("problem.in", "r", stdin); // 将 cin 重定向到文件（将 "problem" 替换为实际名称）
freopen("problem.out", "w", stdout); // 将 cout 重定向到文件
// 这两行之后 cin/cout 正常使用但读写文件
C.2 常用宏和 typedef
📄 查看代码：C.2 常用宏和 typedef
// 较短的类型名
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
// 缩写操作
#define pb push_back
#define pf push_front
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define sz(v) ((int)(v).size())
#define fi first
#define se second
// 循环宏（谨慎使用——可能影响可读性）
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
// 最小/最大值缩写
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)
// 使用示例：
// vi v; v.pb(5); → v.push_back(5)
// sort(all(v)); → sort(v.begin(), v.end())
// cout << sz(v) << "\n";→ cout << (int)v.size() << "\n"
// FOR(i, 1, n+1) { ... }→ for(int i = 1; i < n+1; i++) { ... }
C.3 GCC 编译指令提速
📄 查看代码：C.3 GCC 编译指令提速
// 这些 pragma 在 GCC 编译器（USACO 评测机使用）上可提速 2-4 倍
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt")
// 放在 #include 之前
// 警告：O3 和 avx2 可能导致微妙的数值差异
// （整数题通常没问题，浮点数要小心）
// 更安全的版本（只有 O2，无向量指令）：
#pragma GCC optimize("O2")
// 带 pragma 的完整竞赛模板：
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
// ... 你的代码
C.4 实用数学：GCD、LCM、模运算
📄 查看代码：C.4 实用数学：GCD、LCM、模运算
#include <bits/stdc++.h>
using namespace std;
// ─── GCD 和 LCM ──────────────────────────────────────────────────────────────
// C++17：来自 <numeric> 的 std::gcd 和 std::lcm
#include <numeric>
int g = gcd(12, 8); // 4
int l = lcm(4, 6); // 12
// C++14 及以前：来自 <algorithm> 的 __gcd
int g2 = __gcd(12, 8); // 4
// 自定义 GCD（辗转相除法）：
ll mygcd(ll a, ll b) { return b ? mygcd(b, a%b) : a; }
ll mylcm(ll a, ll b) { return a / mygcd(a,b) * b; } // 先除防溢出！
// ─── 模运算 ──────────────────────────────────────────────────────────────────
const ll MOD = 1e9 + 7; // 标准 USACO/Codeforces 模数
// 加法：(a + b) % MOD
ll addmod(ll a, ll b) { return (a + b) % MOD; }
// 减法：(a - b + MOD) % MOD ← 取模前总要加 MOD 防负数
ll submod(ll a, ll b) { return (a - b + MOD) % MOD; }
// 乘法：(a * b) % MOD
ll mulmod(ll a, ll b) { return (a % MOD) * (b % MOD) % MOD; }
// 快速幂：a^b mod MOD，O(log b)
ll power(ll base, ll exp, ll mod = MOD) {
ll result = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) result = result * base % mod; // 奇数指数
base = base * base % mod; // 平方
exp >>= 1; // 减半指数
}
return result;
}
// 模逆元（a^{-1} mod p，p 为质数）：
ll modinv(ll a, ll mod = MOD) { return power(a, mod-2, mod); }
// 这使用费马小定理：a^{p-1} ≡ 1 (mod p)，p 为质数
// 所以 a^{-1} ≡ a^{p-2} (mod p)
// 模除法：(a / b) mod p = (a * b^{-1}) mod p
ll divmod(ll a, ll b) { return mulmod(a, modinv(b)); }
// 预计算阶乘后的组合数 C(n, k) mod p
const int MAXN = 200001;
ll fact[MAXN], inv_fact[MAXN];
void precompute_factorials() {
fact[0] = 1;
for (int i = 1; i < MAXN; i++) fact[i] = fact[i-1] * i % MOD;
inv_fact[MAXN-1] = modinv(fact[MAXN-1]);
for (int i = MAXN-2; i >= 0; i--) inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
}
ll C(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD;
}
C.5 实用代码片段
并查集（DSU）模板
📄 查看代码：并查集（DSU）模板
// DSU——带大小追踪的完整模板
struct DSU {
vector<int> parent, sz;
DSU(int n) : parent(n+1), sz(n+1, 1) {
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]); // 路径压缩
return parent[x];
}
bool unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return false;
if (sz[x] < sz[y]) swap(x, y); // 按大小合并
parent[y] = x;
sz[x] += sz[y];
return true;
}
bool connected(int x, int y) { return find(x) == find(y); }
int size(int x) { return sz[find(x)]; } // x 所在分量的大小
};
// 使用：
DSU dsu(n);
dsu.unite(1, 2);
cout << dsu.connected(1, 3) << "\n"; // 0（假）
cout << dsu.size(1) << "\n"; // 2
线段树（单点更新，区间查询）
📄 查看代码：线段树（单点更新，区间查询）
// 线段树——支持：
// point_update(i, val)：设置位置 i 为 val
// query(l, r)：[l, r] 的和
// 所有操作 O(log N)
struct SegTree {
int n;
vector<ll> tree;
SegTree(int n) : n(n), tree(4*n, 0) {}
void update(int node, int start, int end, int idx, ll val) {
if (start == end) {
tree[node] = val;
return;
}
int mid = (start + end) / 2;
if (idx <= mid) update(2*node, start, mid, idx, val);
else update(2*node+1, mid+1, end, idx, val);
tree[node] = tree[2*node] + tree[2*node+1];
}
ll query(int node, int start, int end, int l, int r) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) return tree[node];
int mid = (start + end) / 2;
return query(2*node, start, mid, l, r)
+ query(2*node+1, mid+1, end, l, r);
}
void update(int i, ll val) { update(1, 1, n, i, val); }
ll query(int l, int r) { return query(1, 1, n, l, r); }
};
BFS 模板
📄 查看代码：BFS 模板
// 网格 BFS——无权网格中的最短路径
int bfs_grid(vector<string>& grid, int sr, int sc, int er, int ec) {
int R = grid.size(), C = grid[0].size();
vector<vector<int>> dist(R, vector<int>(C, -1));
queue<pair<int,int>> q;
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
dist[sr][sc] = 0;
q.push({sr, sc});
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < R && nc >= 0 && nc < C
&& grid[nr][nc] != '#' && dist[nr][nc] == -1) {
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
}
return dist[er][ec];
}
二分答案模板
📄 查看代码：二分答案模板
// 二分答案——最大化满足 check(X) 为真的 X
// 前提：check 是单调的（false...false...true...true）
template<typename T, typename F>
T binary_search_ans(T lo, T hi, F check) {
T ans = lo;
while (lo <= hi) {
T mid = lo + (hi - lo) / 2;
if (check(mid)) { ans = mid; lo = mid + 1; }
else { hi = mid - 1; }
}
return ans;
}
// 使用示例：找最大 D 使 canPlace(D) 为真
int result = binary_search_ans(1, maxDist, canPlace);
C.6 值得了解的内置函数
📄 查看代码：C.6 值得了解的内置函数
// ─── 整数操作 ─────────────────────────────────────────────────────────────────
__builtin_popcount(x) // 统计 x 中置位数（int）
__builtin_popcountll(x) // 统计 x 中置位数（long long）
__builtin_clz(x) // 统计前导零数（int，x > 0）
__builtin_ctz(x) // 统计尾零数（int，x > 0）
// 示例：
__builtin_popcount(0b1011) == 3 // 三个 1 位
__builtin_ctz(0b1000) == 3 // 三个尾零
(31 - __builtin_clz(x)) // floor(log2(x))
// ─── 位运算技巧 ──────────────────────────────────────────────────────────────
// 检查 x 是否是 2 的幂：
bool isPow2 = (x > 0) && !(x & (x-1));
// 提取最低置位：
int lsb = x & (-x);
// 清除最低置位：
x = x & (x-1);
// 枚举位掩码的所有子集（用于状压 DP）：
for (int sub = mask; sub > 0; sub = (sub-1) & mask) {
// 处理 mask 的子集 sub
}
// ─── 实用 STL 函数 ────────────────────────────────────────────────────────────
// next_permutation：遍历所有排列
sort(v.begin(), v.end()); // 从有序开始
do {
// v 是当前排列
} while (next_permutation(v.begin(), v.end()));
C.7 完整竞赛模板
📄 查看代码：C.7 完整竞赛模板
// ────────────────────────────────────────────────────────────────────────────
// 竞赛编程模板——C++17
// ────────────────────────────────────────────────────────────────────────────
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
// 类型别名
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())
#define fi first
#define se second
// 常量
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const int MAXN = 200005;
// 快速幂取模
ll power(ll base, ll exp, ll mod = MOD) {
ll res = 1; base %= mod;
for (; exp > 0; exp >>= 1) {
if (exp & 1) res = res * base % mod;
base = base * base % mod;
}
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// 文件 I/O 时取消注释：
// freopen("problem.in", "r", stdin);
// freopen("problem.out", "w", stdout);
// ── 你的解法 ──
return 0;
}
C.8 常用模式和惯用法
📄 查看代码：C.8 常用模式和惯用法
// ─── 读取 N 个整数到向量 ──────────────────────────────────────────────────────
int n; cin >> n;
vi a(n);
for (int &x : a) cin >> x;
// ─── 二维向量初始化 ──────────────────────────────────────────────────────────
int R, C;
vector<vector<int>> grid(R, vector<int>(C, 0));
// ─── 自定义条件排序 ──────────────────────────────────────────────────────────
sort(all(v), [](const auto &a, const auto &b) {
return a.weight < b.weight; // 按重量升序排序
});
// ─── 带下标的最小/最大值 ─────────────────────────────────────────────────────
auto maxIt = max_element(all(v));
int maxVal = *maxIt;
int maxIdx = maxIt - v.begin();
// ─── 从有序向量删除重复 ──────────────────────────────────────────────────────
sort(all(v));
v.erase(unique(all(v)), v.end());
// ─── 整数平方根（精确，无浮点问题）──────────────────────────────────────────
ll isqrt(ll n) {
ll r = sqrtl(n);
while (r*r > n) r--;
while ((r+1)*(r+1) <= n) r++;
return r;
}
// ─── 检查数是否为质数 ─────────────────────────────────────────────────────────
bool isPrime(ll n) {
if (n < 2) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
for (ll i = 3; i * i <= n; i += 2) {
if (n % i == 0) return false;
}
return true;
}
// ─── 埃拉托斯特尼筛法（N 以内所有质数）───────────────────────────────────────
vector<bool> sieve(int N) {
vector<bool> is_prime(N+1, true);
is_prime[0] = is_prime[1] = false;
for (int i = 2; i * i <= N; i++) {
if (is_prime[i]) {
for (int j = i*i; j <= N; j += i)
is_prime[j] = false;
}
}
return is_prime;
}
C.9 调试技巧
📄 查看代码：C.9 调试技巧
// 用 cerr 调试输出（评测机通常忽略标准错误）
#ifdef DEBUG
#define dbg(x) cerr << #x << " = " << x << "\n"
#define dbgv(v) cerr << #v << ": "; for(auto x:v) cerr << x << " "; cerr << "\n"
#else
#define dbg(x)
#define dbgv(v)
#endif
// 调试模式编译：g++ -DDEBUG -o sol sol.cpp （启用调试输出）
// 正常编译： g++ -o sol sol.cpp （移除调试输出）
// 使用：
int x = 42;
dbg(x); // 打印：x = 42（仅调试模式）
vi v = {1,2,3};
dbgv(v); // 打印：v: 1 2 3（仅调试模式）
// 用消毒器检测内存错误和未定义行为：
// g++ -fsanitize=address,undefined -O1 -o sol sol.cpp
// 非常适合发现：
// - 数组越界访问
// - 整数溢出（带 -fsanitize=signed-integer-overflow）
// - 使用未初始化内存
// - 空指针解引用
树状数组（BIT）——带更新的前缀和
树状数组使用最低置位技巧实现 O(log N) 的前缀和查询和更新。下标 i 负责范围 [i - lowbit(i) + 1, i]，其中 lowbit(i) = i & (-i)。
📄 C++ 完整代码
// 树状数组 / BIT——O(log N) 更新和前缀查询
struct BIT {
int n;
vector<long long> tree;
BIT(int n) : n(n), tree(n + 1, 0) {}
// 在位置 i 添加 val（1-indexed）
void update(int i, long long val) {
for (; i <= n; i += i & (-i))
tree[i] += val;
}
// 前缀和 [1..i]
long long query(int i) {
long long sum = 0;
for (; i > 0; i -= i & (-i))
sum += tree[i];
return sum;
}
// 区间和 [l..r]
long long query(int l, int r) { return query(r) - query(l - 1); }
};