附录 F：调试指南——常见 Bug 及修复方法

💡 为什么要有这份附录？ 即便算法思路完全正确，只要一个 Bug 溜进代码，结果就会出错。本指南系统地整理了竞赛 C++ 代码中最常见的 Bug，按类别分类，方便快速定位。当你的解答出现 WA（Wrong Answer）、TLE（Time Limit Exceeded）、RE（Runtime Error）或 MLE（Memory Limit Exceeded）时，请先来这里查找原因。

用下面这张分类图快速判断你的 Bug 属于哪个类别：

拿到错误判决后，按照这个系统化的调试流程来排查：

F.1 整数溢出

C++ 中 Wrong Answer 最常见的根源。

问题：int 太小了

int 的最大值约为 2.1 × 10⁹（≈ 2 × 10⁹）。很多题目的中间值会超出这个范围。

// ❌ 错误：n=10^5 时，n*n 会溢出
int n = 100000;
int result = n * n;  // = 10^10 → 超出 int 范围（最大 ~2×10^9）！

// ✅ 正确：乘之前先转成 long long
long long result = (long long)n * n;  // = 10^10，在 long long 范围内
// 或：
long long n_ll = n;
long long result2 = n_ll * n_ll;

什么时候该用 long long

危险操作举例

// ❌ 溢出示例：
int a = 1e9, b = 1e9;
cout << a + b;     // 溢出（结果 > INT_MAX）
cout << a * 2;     // 溢出
cout << a * a;     // 灾难性溢出

// ❌ 比较时溢出：
if (a * b > 1e18) ...  // a*b 本身可能已经溢出了！

// ✅ 安全版本：
cout << (long long)a + b;
cout << (long long)a * 2;
cout << (long long)a * a;
if ((long long)a * b > (long long)1e18) ...  // 用 long long 比较

INF 值的选择

// ❌ 错误：在 Dijkstra 中用 INT_MAX 作为无穷大
const int INF = INT_MAX;
if (dist[u] + w < dist[v]) ...  // dist[u] + w 在 dist[u]=INT_MAX 时溢出！

// ✅ 正确：使用安全的哨兵值
const long long INF = 1e18;   // 用于 long long 距离
const int INF_INT = 1e9;       // 用于 int 距离（留有加法空间）

F.2 差一错误（Off-By-One）

WA 第二常见的根源。

数组下标

// ❌ 错误：访问 A[n] 越界
int A[n];
for (int i = 0; i <= n; i++) cout << A[i];  // A[n] 未定义！

// ✅ 正确
for (int i = 0; i < n; i++) cout << A[i];   // 下标 0..n-1
// 或（1-indexed）：
for (int i = 1; i <= n; i++) cout << A[i];  // 下标 1..n

前缀和公式

// ❌ 错误：区间和差一
// sum(L, R) 应该是 P[R] - P[L-1]，而不是 P[R] - P[L]
cout << P[R] - P[L];    // 少了 A[L]！

// ✅ 正确
cout << P[R] - P[L-1];  // P[0]=0 正确处理 L=1 的边界情况

二分查找边界

// 查找第一个 A[i] >= target 的下标（lower_bound 行为）：

// ❌ 错误：常见二分查找写法错误
int lo = 0, hi = n - 1;
while (lo < hi) {
    int mid = (lo + hi) / 2;
    if (A[mid] < target) lo = mid;      // BUG：应为 lo = mid + 1
    else hi = mid - 1;                   // BUG：应为 hi = mid
}

// ✅ 正确：标准 lower_bound 模板
int lo = 0, hi = n;  // hi = n（而非 n-1），以允许"未找到"的情况
while (lo < hi) {
    int mid = (lo + hi) / 2;
    if (A[mid] < target) lo = mid + 1;  // target 在 [mid+1, hi]
    else hi = mid;                       // target 在 [lo, mid]
}
// lo = hi = 第一个 A[i] >= target 的下标；lo=n 表示未找到

循环边界

// ❌ 常见错误：循环多跑或少跑一次
for (int i = 1; i < n; i++) ...    // 若本意是 i=0 到 n-1，则漏了 i=0
for (int i = 0; i <= n-1; i++) ... // 正确但写法混乱；推荐 i < n

// DP 表格填充：注意递推是否访问了 i-1
// ❌ 如果 dp[i] 用到 dp[i-1]，而 i 从 0 开始，则 dp[-1] 未定义！
for (int i = 0; i <= n; i++) {
    dp[i] = dp[i-1] + ...;  // BUG：i=0 时访问 dp[-1]！
}

// ✅ 从 i=1 开始，或单独初始化 dp[0] 作为边界条件
dp[0] = BASE_CASE;
for (int i = 1; i <= n; i++) {
    dp[i] = dp[i-1] + ...;  // 安全：dp[i-1] 始终有效
}

F.3 未初始化的变量

// ❌ 错误：dp 数组未初始化
int dp[1005][1005];  // 在 C++ 中包含垃圾值！
// dp[i][j] 可能因上一个测试用例或操作系统内存而非零

// ✅ 正确方式：
// 方式一：memset（按字节填充，用 0 或 0x3f 模拟正无穷）
memset(dp, 0, sizeof(dp));          // 全部置 0
memset(dp, 0x3f, sizeof(dp));       // 置为 ~1.06e9（适合用作 int 的"无穷大"）

// 方式二：vector 显式初始化
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

// 方式三：fill
fill(dp, dp + n, 0);

// ⚠️ 警告：memset(dp, -1, sizeof(dp)) 将每个字节置为 0xFF
// 对 int：0xFFFFFFFF = -1（可用于"未访问"标记）
// 对 long long：0xFFFFFFFFFFFFFFFF = -1（同样有效）
// 但 memset(dp, 1, sizeof(dp)) 得到 0x01010101 = 16843009，而不是 1！

全局变量 vs 局部变量

// C++ 中全局数组默认初始化为零
// 局部（栈）数组则不会初始化

int globalArr[100005];     // ✅ 初始化为 0
int globalDP[1005][1005];  // ✅ 初始化为 0

int main() {
    int localArr[1000];    // ❌ 未初始化（含垃圾值）
    int localDP[100][100]; // ❌ 未初始化
    
    // 建议：将大数组声明为全局变量，既避免栈溢出又保证初始化
}

F.4 栈溢出（递归过深）

// C++ 默认栈大小通常为 1~8 MB
// 递归层数过深会超出限制 → 运行时错误（段错误）

// ❌ 危险：在深度为 10^5 的树上递归 DFS
void dfs(int u) { dfs(children[u]); }  // 长链场景下会栈溢出！

// ✅ 解法一：用显式栈改写为迭代
void dfs_iterative(int start) {
    stack<int> st;
    st.push(start);
    while (!st.empty()) {
        int u = st.top(); st.pop();
        for (int v : children[u]) st.push(v);
    }
}

// ✅ 解法二：增大栈大小（平台相关，竞赛评测机通常允许）
// Linux 下编译并运行：ulimit -s unlimited && ./sol

// 经验法则：
// 递归深度 ≤ ~10^4：通常安全
// 递归深度 ~10^5：有风险，考虑迭代
// 递归深度 ~10^6：几乎必定栈溢出 → 必须用迭代

F.5 模运算 Bug

// 当题目要求输出 mod 10^9+7 时：
const int MOD = 1e9 + 7;

// ❌ 错误：忘记取模，long long 溢出
long long dp = 1;
for (int i = 0; i < n; i++) dp *= A[i];  // ~18 次大数乘法后溢出！

// ❌ 错误：减法下溢（结果为负的模）
long long ans = (a - b) % MOD;  // a < b 时，C++ 返回负数！

// ✅ 正确：减法取模前加上 MOD
long long ans = ((a - b) % MOD + MOD) % MOD;  // 保证非负

// ❌ 错误：DP 中忘记对中间值取模
dp[i][j] = dp[i-1][j] + dp[i][j-1];  // 迭代次数多时可能溢出

// ✅ 正确：每次加法后立即取模
dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD;

// ✅ 正确的模意义快速幂：
long long modpow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;  // ← 每次乘法后取模！
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

F.6 图/BFS/DFS Bug

// ❌ BFS：忘记在入队之前标记已访问
// 这会导致同一节点被处理多次！
queue<int> q;
q.push(src);
while (!q.empty()) {
    int u = q.front(); q.pop();
    visited[u] = true;  // ❌ 出队后才标记 → 同一节点可能多次入队
    for (int v : adj[u]) if (!visited[v]) q.push(v);
}

// ✅ 正确：入队时立即标记已访问
visited[src] = true;
queue<int> q;
q.push(src);
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u]) {
        if (!visited[v]) {
            visited[v] = true;  // ✅ 入队前标记
            q.push(v);
        }
    }
}

// ❌ DFS：多个测试用例之间忘记重置 visited
// 多测问题中，每次测试用例开始前必须重新初始化 visited[]！
memset(visited, false, sizeof(visited));

// ❌ Dijkstra：距离数组用 int 而非 long long
int dist[MAXN];  // ❌ 边权最大 10^9 时，累加后溢出！
long long dist[MAXN];  // ✅

F.7 I/O Bug

// ❌ 错误：大量输入时未加 ios_base::sync_with_stdio(false)
// 不加此行，cin/cout 与 C 标准 I/O 同步 → 速度极慢！
// N = 10^6 的输入量下，可能是 AC 与 TLE 的差距。

// ✅ 每道竞赛题的 main() 开头都应加上：
ios_base::sync_with_stdio(false);
cin.tie(NULL);

// ❌ 错误：使用 endl（每行都刷新缓冲区 → 很慢）
for (int i = 0; i < n; i++) cout << ans[i] << endl;  // 慢！

// ✅ 正确：用 "\n" 代替
for (int i = 0; i < n; i++) cout << ans[i] << "\n";  // 快

// ❌ 错误：关闭同步后混用 cin 与 scanf/printf
ios_base::sync_with_stdio(false);
scanf("%d", &n);  // BUG：解除同步后混用 C 和 C++ I/O！

// ✅ 正确：选一种方式并坚持使用
// 要么只用 cin/cout，要么只用 scanf/printf

// USACO 文件 I/O（有时题目要求）：
freopen("problem.in", "r", stdin);
freopen("problem.out", "w", stdout);
// 加上这两行后，cin/cout 会自动读写文件

F.8 二维数组越界与方向

// 网格 BFS：边界检查差一错误
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

// ❌ 错误（实际上下面这种写法是正确的——只是确保四个条件都写到）
for (int d = 0; d < 4; d++) {
    int nx = x + dx[d], ny = y + dy[d];
    if (nx >= 0 && ny >= 0 && nx < n && ny < m) // ✅ 这个边界检查是正确的！
    // 确保四个条件都写全
}

// ❌ 错误：弄混行列（转置了行和列）
// 若网格是 N 行 × M 列：
// A[row][col]：row 取值 0..N-1，col 取值 0..M-1
// 边界条件：row < N，col < M（不能写成 row < M！）

// ❌ 错误：多源 BFS 计算距离时，同一格子被多次访问（忘记距离检查）
if (!visited[nx][ny]) {  // ✅ 只访问未访问的格子
    visited[nx][ny] = true;
    dist[nx][ny] = dist[x][y] + 1;
    q.push({nx, ny});
}

F.9 DP 专项 Bug

// ❌ 错误：0/1 背包内层循环方向错了
// 必须从高到低遍历容量，防止物品被重复使用！
for (int i = 0; i < n; i++) {
    for (int j = W; j >= weight[i]; j--) {  // ✅ 从高到低
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}
// 若从低到高遍历：
for (int j = weight[i]; j <= W; j++) {  // ❌ 从低到高 = 完全背包！
    dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}

// ❌ 错误：LIS 二分查找时混淆 upper_bound 与 lower_bound
// 严格递增 LIS：用 lower_bound（找第一个 >= x 的位置，替换）
// 非严格递减 LIS：用 upper_bound（找第一个 > x 的位置，替换）
auto it = lower_bound(tails.begin(), tails.end(), x);  // 严格递增
auto it = upper_bound(tails.begin(), tails.end(), x);  // 非严格递减

// ❌ 错误：忘记初始化边界条件
// dp[0] 或 dp[i][0] 或 dp[0][j] 必须在主循环之前显式赋值
dp[0][0] = 0;  // 始终初始化边界条件！

F.10 内存超限（MLE）

// 常见的 MLE 原因：

// ❌ 数组过大
int dp[10005][10005];  // = 10^8 个 int = 400MB → 超出典型的 256MB 限制！

// 计算方式：N × M × sizeof(类型) 字节
// int：4 字节，long long：8 字节
// 256MB = 256 × 10^6 字节
// int 数组最多约 6400 万个元素
// long long 数组最多约 3200 万个元素

// ✅ 一维 DP 的空间优化：
// 若 dp[i] 只依赖 dp[i-1]，使用滚动数组：
vector<long long> dp(2, 0);  // dp[cur] 和 dp[prev]
for (int i = 0; i < n; i++) {
    dp[1 - cur] = f(dp[cur]);  // 在 0 和 1 之间交替
    cur = 1 - cur;
}

// ✅ 二维 DP 的空间优化（背包类）：
// 若 dp[i][j] 只依赖 dp[i-1][...]，只保留两行
vector<int> prev_row(W+1, 0), curr_row(W+1, 0);

F.11 对拍——随机数据 + 暴力验证

💡 为什么需要它？ 看完 F.1–F.10，你会发现 Bug 往往不在你手算的样例上出现，而藏在你想不到的边界数据里。与其盯着代码发呆，不如让机器替你造数据、跑程序、比答案——这就是对拍（stress testing）。这是竞赛选手从「能过样例」到「能过所有数据」最重要的工具。

对拍三件套

对拍由三个程序加一个循环脚本组成：

循环脚本不断执行：生成数据 → 两个程序各跑一遍 → 比较输出。一旦不一致，就找到了一组「杀人数据」——把它保存下来，用 cerr 打印中间值调试（见 F 章末尾的专业建议）。

随机数据生成器

生成器的唯一原则：和题目输入格式完全一致，且能随机到边界。推荐用 mt19937 + 时间种子（比老的 rand() 周期更长、分布更均匀）。

生成器 1：随机树（第 5.5 章树题对拍必备。技巧：节点 i 的父亲在 [1, i-1] 中随机，天然保证无环）

// gen_tree.cpp —— 随机树：节点 1..n，第 i 个节点的父亲在 [1, i-1] 中均匀随机
#include <bits/stdc++.h>
#include <random>
using namespace std;
int main(int argc, char* argv[]) {
    // 时间种子：每次运行产生不同数据
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    if (argc > 1) rng.seed(stoi(argv[1]));   // 可选：固定种子，复现某组数据

    int n = 1 + rng() % 200000;              // 1 <= n <= 2*10^5（按题目范围改）
    cout << n << "\n";
    for (int i = 2; i <= n; i++) {
        int parent = 1 + rng() % (i - 1);    // 父亲编号 < i，保证无环
        cout << parent << " " << i << "\n";
    }
    return 0;
}

生成器 2：随机区间（区间 DP、差分约束、线段树题常用）

// gen_interval.cpp —— n 个随机区间 [l, r]
#include <bits/stdc++.h>
#include <random>
using namespace std;
int main() {
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    int LIMIT = 1000000;
    int n = 1 + rng() % 100000;
    cout << n << "\n";
    for (int i = 0; i < n; i++) {
        long long l = 1 + (long long)(rng() % LIMIT);
        long long r = l + rng() % 100;       // 保证 l <= r
        cout << l << " " << r << "\n";
    }
    return 0;
}

生成器 3：随机排列（注意：对 1..n 循环「随机交换」不是均匀分布，用 shuffle 才是）

// gen_perm.cpp —— 1..n 的均匀随机排列
#include <bits/stdc++.h>
#include <random>
using namespace std;
int main() {
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    int n = 1 + rng() % 200000;
    vector<int> a(n);
    iota(a.begin(), a.end(), 1);
    shuffle(a.begin(), a.end(), rng);        // 均匀随机排列 ✅
    cout << n << "\n";
    for (int i = 0; i < n; i++)
        cout << a[i] << " \n"[i == n - 1];
    return 0;
}

对拍脚本

macOS / Linux（bash）：

#!/bin/bash
# stress.sh —— 用法：chmod +x stress.sh && ./stress.sh
g++ -O2 -std=c++17 gen.cpp -o gen
g++ -O2 -std=c++17 brute.cpp -o brute
g++ -O2 -std=c++17 main.cpp -o main

i=1
while true; do
    ./gen > in.txt                       # 1. 生成随机数据
    ./brute < in.txt > out_brute.txt     # 2. 跑暴力
    ./main   < in.txt > out_main.txt     # 3. 跑正解
    if diff -q out_brute.txt out_main.txt > /dev/null; then
        echo "Test $i: OK"
    else
        echo "Test $i: MISMATCH! 数据已存入 in.txt"
        break                            # ⚠️ 必须停！否则杀人数据被下一轮覆盖
    fi
    i=$((i + 1))
done

Windows（记事本另存为 stress.bat，ANSI/GBK 编码，双击运行）：

@echo off
g++ -O2 -std=c++17 gen.cpp -o gen.exe
g++ -O2 -std=c++17 brute.cpp -o brute.exe
g++ -O2 -std=c++17 main.cpp -o main.exe

:loop
gen.exe > in.txt
brute.exe < in.txt > out1.txt
main.exe   < in.txt > out2.txt
fc out1.txt out2.txt > nul
if errorlevel 1 (
    echo MISMATCH! 数据已存入 in.txt
    pause
    goto :end
)
goto :loop
:end

⚠️ 对拍的五大常见错误

1. 种子没随机。 用了 mt19937 rng(42) 这种固定种子——每次对拍跑的都是同一组数据，跑一万遍等于跑一遍。用 chrono::steady_clock::now().time_since_epoch().count() 做种子；反过来，发现杀人数据后记得用固定种子复现它（见 gen_tree 的 argv[1] 参数）。
2. 数据范围没对齐题目边界。 题目说 1 ≤ n ≤ 10⁵，生成器却只造小 n；或者忘了生成 n=1、全部元素相等、极大值 10⁹、负数、空图这类边界。对拍的价值恰恰在边界——每类边界至少固定造一组，再随机。
3. diff 发现不同后忘了 break。 脚本继续循环，in.txt 被下一轮覆盖，杀人数据丢了，白拍。bash 版用 break，bat 版 goto :end。
4. Windows 换行符（CRLF）。 在 Windows 上用旧编辑器写的文件换行是 \r\n，两个程序输出一个带 \r 一个不带，diff/fc 误报不一致。建议输出统一用 "\n"；跨平台比较时用 diff --strip-trailing-cr。
5. 暴力程序本身写错。 暴力错了，对拍只会把正确程序「冤枉」到怀疑人生。暴力要写得越笨越好——直接枚举、不加任何优化，简单到不需要验证；若两个程序都能对上小样例，可信度就足够了。

什么时候对拍？

• 写完暴力但不确定正解时：先交暴力保底，同时开拍验证正解——这是性价比最高的时机。
• 提交前 5 分钟：交卷前跑几百组小数据，比多检查一遍代码的收益高得多。经验法则：AC 之前永远值得再拍 100 组。

💡 一句话总结： gen 造数据、brute 保正确、main 待检验，脚本循环 diff 直到找到杀人数据——把「我看起来没错」变成「机器证明我没错」。

快速诊断清单

拿到 WA/RE/TLE 时，按这个清单逐项检查：

Wrong Answer（WA）：

• 整数溢出？（增加 long long 强制转换或更换类型）
• 数组边界、循环边界、区间和公式差一？
• 数组未初始化？（添加 memset 或用带初始化的 vector）
• DP 递推方向错误？（0/1 背包：必须从高到低）
• 二分查找模板错误？（在 [1,2,3] 中搜索 2 验证一下）
• 边界情况：空输入、N=0、N=1、全部相等的元素？

Runtime Error（RE）：

• 数组越界？（添加边界检查或改用 vector）
• 递归过深导致栈溢出？（改写为迭代）
• 空指针/无效指针解引用？
• 除以零？

Time Limit Exceeded（TLE）：

• 缺少 ios_base::sync_with_stdio(false); cin.tie(NULL);？
• N=10⁵ 时用了 O(N²) 算法，应该用 O(N log N)？
• DP 中重复计算？（需要记忆化）
• BFS 中同一节点被多次访问？（入队前标记已访问）

Memory Limit Exceeded（MLE）：

• 二维数组过大？（计算 N × M × sizeof 字节数）
• 递归 DFS 的隐式调用栈过深？
• 在循环中动态分配内存？

💡 专业建议： 打印中间值！cerr << "DEBUG: dp[3] = " << dp[3] << "\n"; cerr 输出到标准错误流（而非标准输出），不会影响竞赛评测机上的输出。提交前记得删除所有 cerr 调试行。