序言

竞赛中，我们经常会遇到这样的情况：程序在样例上跑得好好的，提交上去却 WA 了（不出意外听听 WA 声一片）。这时候，我们需要找到那个让程序出错的数据点。手工构造测试数据？太慢了。随机生成几组数据测试？运气不好可能测不出来。

又或者是，我觉得我的算法是对的，但总觉得哪里不对劲，想要验证一下？

这时候，对拍就派上用场了。

对拍是一种自动化测试技术，通过生成大量随机数据，让你的程序和一个已知正确的程序（一般就是写个暴力程序）同时运行，然后比较两者的输出。一旦发现输出不同，就说明你的程序在这组数据上出错了。

对拍的核心思想：用时间换正确。暴力程序虽然慢，但正确性有保证；你的程序虽然快，但可能有 bug。通过对拍，我们可以快速找到出错的数据。 ~~而且反正对拍也是在你本地跑的，你还能干别的，还能找到错误，不挺好的吗~~

（虽然已经有好几篇对拍文章了，但是感觉都比较口语化，这里还是详细介绍一下吧）

什么是对拍

对拍是一种程序测试方法，主要包含以下步骤。

数据生成器：随机生成符合题目要求的测试数据。
标准程序：通常是暴力算法，保证正确但可能很慢。
待测程序：你要提交的程序，速度快但可能有 bug。
循环测试：
- 生成一组随机数据。
- 分别用标准程序和待测程序运行。
- 比较两者的输出。
- 如果输出不同，保存这组数据并停止。
- 如果输出相同，继续下一组测试。

通过这种方法，我们可以在短时间内测试成千上万组数据，大大提高找到 bug 的效率。

对拍的组成部分

一个完整的对拍系统通常包含四个部分。

数据生成器

数据生成器负责生成随机的、符合题目要求的测试数据。

示例：生成一个包含 $n$ 个整数的数组。

#include <bits/stdc++.h>
using namespace std;

int main() {
    srand(time(0));  // 使用时间作为随机种子，注意：每秒内运行多次是一样的

    int n = rand() % 100 + 1;  // 随机生成 1~100 之间的 n
    cout << n << endl;

    for (int i = 0; i < n; i++) {
        cout << rand() % 1000 + 1;  // 生成 1~1000 的随机数
        if (i < n - 1) cout << " ";
    }
    cout << endl;

    return 0;
}

注意事项：

使用 time(0) 作为随机种子，确保每次运行生成不同的数据（每秒内多次运行可能生成相同的种子）。
数据范围要符合题目要求。
对于有特殊限制的题目（尤其是图论），需要特别注意生成合法的数据，避免生成非法测试用例导致误判。

标准程序

标准程序通常是暴力算法，虽然时间复杂度高，但正确性有保证。

示例：找数组中的最大值（暴力）。

#include <bits/stdc++.h>
using namespace std;

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

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

    cout << maxVal << endl;
    return 0;
}

待测程序

这是你要提交的程序，可能使用了更优的算法。

示例：找数组中的最大值。

#include <bits/stdc++.h>
using namespace std;

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

    cout << *max_element(a.begin(), a.end()) << endl;
    return 0;
}

对拍脚本

对拍脚本负责自动化整个测试流程，下面分别给出 Windows 和 Linux/macOS 的常见实现。

Windows 下的对拍实现

在 Windows 系统中，我们可以使用批处理脚本来实现对拍。

创建一个 duipai.bat 文件。

@echo off
echo Compiling programs...
g++ generator.cpp -o generator.exe -O2 -std=c++14
g++ std.cpp -o std.exe -O2 -std=c++14
g++ my.cpp -o my.exe -O2 -std=c++14

if errorlevel 1 (
    echo Compilation failed!
    pause
    exit
)

echo Compilation successful!

:: 对拍循环
set /a count=0
:loop
set /a count+=1
echo Testing case %count%...

:: 生成数据
generator.exe > data.in

:: 运行两个程序
std.exe < data.in > std.out
my.exe < data.in > my.out

:: 比较输出
fc std.out my.out > nul

if errorlevel 1 (
    echo ========================================
    echo Found different output at case %count%!
    echo ========================================
    echo Input data saved in: data.in
    echo Standard output saved in: std.out
    echo Your output saved in: my.out
    pause
    exit
) else (
    echo Case %count% passed.
)

goto loop

脚本解释：

@echo off：关闭命令显示。
g++ ... -O2 -std=c++14：编译程序。
generator.exe > data.in：运行数据生成器，将输出重定向到 data.in。
std.exe < data.in > std.out：从 data.in 读取输入，将输出重定向到 std.out。
fc std.out my.out > nul：比较两个文件（fc 是 Windows 里用于比较的工具），> nul 表示不显示比较详情。
if errorlevel 1：如果文件不同（不同的时候 fc 返回非零），则找到了错误。

Linux/macOS 下的对拍实现

在 Linux 或 macOS 系统中，我们通常使用 Shell 脚本来实现对拍。

创建一个 duipai.sh 文件。

#!/bin/bash

echo "Compiling programs..."
g++ generator.cpp -o generator -O2 -std=c++14
g++ std.cpp -o std -O2 -std=c++14
g++ my.cpp -o my -O2 -std=c++14

if [ $? -ne 0 ]; then
    echo "Compilation failed!"
    exit 1
fi

echo "Compilation successful!"

count=0
while true; do
    count=$((count + 1))
    echo "Testing case $count..."
    ./generator > data.in
    ./std < data.in > std.out
    ./my < data.in > my.out
    if ! diff -q std.out my.out > /dev/null; then
        echo "========================================"
        echo "Found different output at case $count!"
        echo "========================================"
        echo "Input data saved in: data.in"
        echo "Standard output saved in: std.out"
        echo "Your output saved in: my.out"
        exit 0
    else
        echo "Case $count passed."
    fi
done

使用方法：

运行 chmod +x duipai.sh 添加执行权限。
运行 ./duipai.sh 启动对拍脚本。

Bash 写法的参考资料可以查看： https://www.runoob.com/linux/linux-shell.html。

实战案例

给定一个长度为 $n$ 的数组，求最大子段和。

generator.cpp（数据生成器）

#include <bits/stdc++.h>
using namespace std;

int main() {
    srand(time(0));

    int n = rand() % 20 + 1;  // 生成 1~20 的 n
    cout << n << endl;

    for (int i = 0; i < n; i++) {
        // 生成 -10~10 的随机数
        int val = rand() % 21 - 10;
        cout << val;
        if (i < n - 1) cout << " ";
    }
    cout << endl;

    return 0;
}

std.cpp（标准程序 - 暴力枚举）

 #include <bits/stdc++.h>
using namespace std;

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

    int maxSum = INT_MIN;
    // O(n^3) 暴力
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int sum = 0;
            for (int k = i; k <= j; k++) {
                sum += a[k];
            }
            maxSum = max(maxSum, sum);
        }
    }

    cout << maxSum << endl;
    return 0;
}

my.cpp（待测程序，有 bug）

#include <bits/stdc++.h>
using namespace std;

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

    int maxSum = 0;  // 初始化不对
    int currentSum = 0;

    for (int i = 0; i < n; i++) {
        currentSum += a[i];
        maxSum = max(maxSum, currentSum);
        if (currentSum < 0) {
            currentSum = 0;
        }
    }

    cout << maxSum << endl;
    return 0;
}

运行对拍

运行对拍脚本后，很快就会发现错误。

Testing case 1...
Case 1 passed.
Testing case 2...
Case 2 passed.
Testing case 3...
...
========================================
Found different output at case 77!
========================================
Input data saved in: data.in
Standard output saved in: std.out
Your output saved in: my.out

查看 data.in：

2 -7 -5

查看 std.out：

-5

查看 my.out：

问题分析：
当所有数都是负数时，标准程序正确地输出了最大值 $- 5$ ，而我们的程序由于 maxSum 初始化为 $0$ ，输出了错误的 $0$ 。

修复后的 my.cpp：

#include <bits/stdc++.h>
using namespace std;

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

    int maxSum = a[0];  // 用第一个元素初始化
    int currentSum = 0;

    for (int i = 0; i < n; i++) {
        currentSum += a[i];
        maxSum = max(maxSum, currentSum);
        if (currentSum < 0) {
            currentSum = 0;
        }
    }

    cout << maxSum << endl;
    return 0;
}

高级技巧

Special Judge（SPJ）

有些题目的答案不唯一（如输出任意一组合法方案），这时需要编写 Special Judge 来检查答案的合法性。

SPJ 示例：

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char* argv[]) {
    // argv[1] 是输入文件
    // argv[2] 是标准程序输出
    // argv[3] 是待测程序输出

    ifstream fin(argv[1]);
    ifstream fstd(argv[2]);
    ifstream fmy(argv[3]);

    // 读取输入
    int n;
    fin >> n;

    // 读取两个程序的输出
    int std_ans, my_ans;
    fstd >> std_ans;
    fmy >> my_ans;

    // 检查答案是否合法
    if (my_ans < 0 || my_ans > n) {
        return 1;  // 答案不合法
    }

    return 0;  // 答案合法
}

在对拍脚本中使用 SPJ 的示例（Windows 批处理）：

spj.exe data.in std.out my.out
if errorlevel 1 (
    echo Wrong Answer!
    goto error
)

多组测试点

对于需要大量测试的情况，可以先生成多组数据，然后批量测试。

#!/bin/bash

# 生成 1000 组数据
for i in {1..1000}; do
    ./generator > data/$i.in
    ./std < data/$i.in > data/$i.out
done

echo "Generated 1000 test cases."

# 测试
for i in {1..1000}; do
    ./my < data/$i.in > my.out
    if ! diff -q data/$i.out my.out > /dev/null; then
        echo "Failed on test case $i"
        exit 1
    fi
done

echo "All tests passed!"

性能测试

除了正确性，我们还可以用对拍来测试程序的性能。

@echo off
set /a count=0
set start=%time%

:loop
set /a count+=1
if %count% GTR 100 goto end

generator.exe > data.in
my.exe < data.in > my.out

goto loop

:end
set end=%time%
echo Tested %count% cases
echo Start: %start%
echo End: %end%
pause

常见问题与解决方案

数据生成器的质量

问题：随机生成的数据可能无法覆盖所有边界情况。
解决方案：

增加特殊数据的生成概率（如空数组、全部相同、递增/递减序列）。
分阶段生成：小数据、大数据、边界数据。
使用多个数据生成器。

精度问题

问题：浮点数比较可能因精度问题导致误判。
解决方案：在 SPJ 中比较浮点数时使用容差，例如：

const double EPS = 1e-6;
if (fabs(std_ans - my_ans) < EPS) {
    // 认为相等
}

输出格式不一致

问题：多余的空格、换行导致对拍失败。
解决方案：

统一输出格式（使用相同的输出方式）。
编写专门的比较程序，忽略格式差异。

忽略空白字符的比较示例：

// 忽略空白字符的比较
bool compareOutput(string file1, string file2) {
    ifstream f1(file1), f2(file2);
    string s1, s2;
    vector<string> v1, v2;

    while (f1 >> s1) v1.push_back(s1);
    while (f2 >> s2) v2.push_back(s2);

    return v1 == v2;
}