2126 字
11 分钟
对拍技巧
2026-01-03
教程
博客

在信息学竞赛中，有这样一句俗话：“不写对拍的算法比赛，就像没有测过的程序上生产。”

许多选手在考场上写出了复杂度极其优秀的算法，在自己手写的几个小样例上完美通过，但提交后却只拿到了 WA（Wrong Answer）。原因往往是漏掉了某些极端边界情况（Corner Cases）。

如何在考场上确定自己的“正解”程序没有 Bug？答案就是——对拍！

本文将为你全面讲解对拍的原理、四大核心要素、实战代码实现以及高级数据生成技巧。

一、什么是“对拍”？#

对拍，简单来说就是用一个“绝对正确”但运行较慢的程序（暴力程序），来验证一个“速度很快”但可能存在隐藏 Bug 的程序（待测程序）。

其基本工作流程如下：

  1. 生成随机数据：写一个数据生成器，按照题目要求生成一组随机输入数据。
  2. 运行两个程序：把这组输入数据同时喂给“待测程序”和“暴力程序”。
  3. 比对输出结果：使用脚本自动比较两个程序的输出文件。
    • 如果输出一致，继续生成下一组数据。
    • 如果输出不一致（发现 Hacker 数据！），程序立即停止。此时保留的这组输入数据，就是让你代码崩溃的反例（Hack 样例）！

二、对拍的四大核心要素#

要完成一次完整的对拍，你需要准备 4 个文件：

文件名称作用特点
my.cpp待测程序运行速度快，但可能存在逻辑 Bug
bf.cpp暴力程序逻辑简单极其不容易写错，但运行慢
gen.cpp随机数据生成器负责按照题目格式生成合法的随机数据
check.cpp / 脚本对拍控制脚本负责循环编译运行上述三者，并比对答案

三、实战：手把手搭建对拍环境#

假设我们遇到了一道题目：求一个序列的最大子段和。

  • 你的正解：my.cpp（用 O(N)O(N) 动态规划写，可能写错状态转移）。
  • 你的暴力：bf.cpp（用 O(N3)O(N^3) 三层循环暴力枚举，绝不可能写错）。

下面一步步搭建对拍：

1. 编写暴力程序 bf.cpp#

// bf.cpp - 绝对可靠的暴力程序
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];


    long long max_sum = -1e18;
    // O(N^3) 暴力枚举区间
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            long long current_sum = 0;
            for (int k = i; k <= j; k++) {
                current_sum += a[k];
            }
            max_sum = max(max_sum, current_sum);
        }
    }
    cout << max_sum << endl;
    return 0;
}

2. 编写待测程序 my.cpp#

// my.cpp - 你的“正解”程序（故意留个 Bug 演示对拍）
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];


    long long max_sum = 0; // 【Bug 所在】：如果全为负数，初始为 0 会导致错误！
    long long current_sum = 0;


    for (int i = 0; i < n; i++) {
        current_sum += a[i];
        if (current_sum > max_sum) max_sum = current_sum;
        if (current_sum < 0) current_sum = 0;
    }


    cout << max_sum << endl;
    return 0;
}

3. 编写数据生成器 gen.cpp#

在 C++11 中，推荐使用 <random> 库中的 mt19937 配合随机种子生成高强度数据。

// gen.cpp - 随机数据生成器
#include <iostream>
#include <random>
#include <chrono>


using namespace std;


int main() {
    // 使用当前微秒级时间作为随机种子
    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


    // 生成 N (数据范围故意设小一点，方便快速暴露问题和手动验证)
    int n = rnd() % 10 + 1; // 1 ~ 10 的随机整数
    cout << n << "\n";


    // 生成 N 个随机数 (包含负数)
    for (int i = 0; i < n; i++) {
        int val = rnd() % 100 - 50; // -50 ~ 49 之间的数
        cout << val << (i == n - 1 ? "" : " ");
    }
    cout << "\n";


    return 0;
}

4. 编写对拍脚本#

方式一：C++ 跨平台对拍程序 check.cpp（强烈推荐，全平台通用）#

不用记 CMD 或 Linux Shell 的语法，直接写一个简单的 C++ 程序来调控！

// check.cpp - C++ 跨平台对拍脚本
#include <iostream>
#include <cstdlib>
#include <ctime>


using namespace std;


int main() {
    // 1. 先编译三个程序
    cout << "Compiling programs..." << endl;
    system("g++ -O2 gen.cpp -o gen");
    system("g++ -O2 my.cpp -o my");
    system("g++ -O2 bf.cpp -o bf");
    cout << "Compilation finished. Start testing...\n" << endl;


    int test_cnt = 0;
    while (true) {
        test_cnt++;


        // 2. 运行数据生成器，重定向到 input.in
        system("./gen > input.in"); // Windows 系统下可去掉 ./


        // 3. 运行两个程序，读入 input.in，分别输出到 my.out 和 bf.out
        system("./my < input.in > my.out");
        system("./bf < input.in > bf.out");


        // 4. 比对输出文件
        // Windows 用 "fc my.out bf.out > nul"
        // Linux / macOS 用 "diff my.out bf.out > /dev/null"
#ifdef _WIN32
        int status = system("fc my.out bf.out > nul");
#else
        int status = system("diff my.out bf.out > /dev/null");
#endif


        if (status != 0) {
            cout << "【Wrong Answer!】 Failed on test #" << test_cnt << endl;
            cout << "Input data saved in 'input.in'." << endl;
            break; // 发现反例，停止对拍
        } else {
            cout << "Test #" << test_cnt << ": Accepted!" << endl;
        }
    }
    return 0;
}

方式二：Windows 批处理脚本（duipai.bat）#

如果你在 Windows 环境下（如 Dev-C++ / VSCode），可以新建一个 duipai.bat 文件：

Terminal window
@echo off
:loop
gen.exe > input.in
my.exe < input.in > my.out
bf.exe < input.in > bf.out


fc my.out bf.out > nul
if errorlevel 1 goto wa
echo Accepted!
goto loop


:wa
echo Wrong Answer!
pause

方式三：Linux / macOS Shell 脚本（duipai.sh）#

在 Linux（如 NOI Linux）赛场环境下：

#!/bin/bash
while true; do
    ./gen > input.in
    ./my < input.in > my.out
    ./bf < input.in > bf.out


    if diff my.out bf.out; then
        echo "Accepted"
    else
        echo "Wrong Answer!"
        exit 0
    fi
done

四、数据生成器的高级技巧#

对拍的效果，80% 取决于数据生成器的质量。如果数据生成得太随性，很难覆盖到边界卡点。

1. 产生指定范围 [L,R][L, R] 的随机数#

int randRange(int L, int R, mt19937& rnd) {
    return rnd() % (R - L + 1) + L;
}

2. 生成随机排列（Permutation）#

常用于生成无重元素的数组或编号：

vector<int> p(n);
for (int i = 0; i < n; i++) p[i] = i + 1;
shuffle(p.begin(), p.end(), rnd); // C++11 随机打乱

3. 生成随机树（Tree）#

生成一棵包含 nn 个节点、n−1n-1 条边的连通无向无环图（树）：

// 节点从 2 到 n，每个节点随机连向编号比它小的节点，保证连通且无环
for (int i = 2; i <= n; i++) {
    int u = i;
    int v = rnd() % (i - 1) + 1; // 在 1 ~ i-1 之间随机选父节点
    cout << u << " " << v << "\n";
}

4. 生成随机区间 [l,r][l, r]#

经常遇到询问区间 [l,r][l, r] (1≤l≤r≤n1 \le l \le r \le n) 的题目：

int l = rnd() % n + 1;
int r = rnd() % n + 1;
if (l > r) swap(l, r); // 确保 l <= r

五、考场对拍的避坑指南与经验总结#

  1. 暴力程序一定要保证“绝对正确”
    • 宁可写 O(N3)O(N^3) 甚至 O(2N)O(2^N) 的搜索，也绝不要为了追求速度而在 bf.cpp 里加未验证的优化。
  2. 对拍时缩小数据范围
    • 不要一开始就生成 N=105N=10^5 的数据，因为暴力程序跑不动！
    • 将数据范围限制在 N=10∼1000N=10 \sim 1000 之间，不仅运行速度极快（1 秒能跑成百上千组），而且只要逻辑有漏洞，小数据极大概率也能触发。
  3. 针对性地构造边界测试（Corner Cases）
    • 你的数据生成器不能只产生“完全随机”的数据。
    • 特例测试：尝试让数据生成器产生全 0、全负数、极大值、全相等序列、极深单链树等特殊数据，许多隐藏 Bug（如溢出 long long、数组越界）往往藏在这些边缘情况中。
  4. 保留反例现场
    • 一旦对拍出 Wrong Answer，脚本会自动停下。此时打开 input.in，直接拿这组数据去单步调试（Debug）你的 my.cpp，定位问题将变得极其轻松！

六、总结#

在信息学竞赛中，“写出代码”只完成了一半，通过“对拍”验证代码才算真正拿到了分数。

养成良好的对拍习惯：

  • 考场前 2 小时：攻克正解，写出 my.cpp；
  • 考场第 3 小时：写出暴力 bf.cpp 保底（顺便拿暴力分）；
  • 最后 1 小时：搭起 gen.cpp 和对拍脚本，让机器自动帮你测几千组数据。

当你看着控制台上满屏滚动的 Accepted 时，那种心里踏实的感觉，就是你赛场上稳拿高分的最好保障！

CSP-J/S比赛时间分配
VSCode环境配置指南
© 2026 oirush. 保留所有权利