【对拍】笔记

liruizhou_lihui · 2025-05-04 17:34:42 · Algo. & Theory

理论

对拍是广泛运用于 NOI 系列赛事的一种 debug 方式，原理为写一个绝对正确的暴力程序与自己要测试的时间复杂度正确程序进行输出比对。具体过程如下：

• 由makeExample（构造样例）程序构造出一个符合题目的样例。
• 传入样例获取到testCode（测试程序） 的输出。
• 传入样例获取到correctCode（正确程序） 的输出。
• 比对。
  • 一样：回到第一步。
  • 不一样：结束。

写对拍

创建一个文件夹，名字叫做对拍。

在文件夹中创建一个记事本，后缀改为.bat，建议用 check.bat。编辑里面的文本改为：

makeExample.exe > testCode.in
testCode < testCode.in > testCode.out
correctCode < testCode.in > correctCode.out
fc testCode.out correctCode.out
if errorlevel==1 pause
%0

意思是：

• 将随机生成的样例传入测试代码的输入文件中。
• 传入样例获取到testCode（测试程序） 的输出。
• 传入样例获取到correctCode（正确程序） 的输出。
• 比对。
  • 一样：回到第一步。
  • 不一样：结束。

创建三个cpp文件，名字分别为testCode,correctCode,makeExample。分别写上你要测试的代码，正确的暴力代码，样例构造代码。

这时候的文件夹是这样的：

查错

双击cheeck.bat，就会开始对拍，直到出现错误时就会停下并且会显示输入与两个代码的输出。

举例

用分解质因数举例：给一个数 n(1\le n\le 10^9) 分解质因数，用乘号连接。

写样例构造程序：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e9;
int n;
int main()
{
    mt19937 gen(time(nullptr)+random_device{}());
    uniform_int_distribution<>dis(1,MAXN);//随机数初始化
    int n=dis(gen);
    cout<<n<<'\n';
    return 0;
}

写一个暴力正确代码与错误代码：

• 暴力正确代码：

#include<bits/stdc++.h>
using namespace std;
void fen(int n)
{
    int a=n;
    bool flag = 0;
    if(n==1)
    {
        cout<<1;
        return ;
    }
    for(int i=2;i*i<=a;i++)
    {
        while(a%i==0)
        {
            cout<<i;
            a/=i;
            if(a!=1)
            {
                cout<<"*";
            }
        }
    }
    if(a>1)
    {
        if(flag == 1)cout<<"*";
        cout<<a;
    }
}
int main()
{
    int n;
    cin>>n;
    fen(n);
}

• 错误代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n;
    cin >> n;
    if(n==1) cout<<1;
    else{
        for(int i=2;i<=sqrt(n);i++)
        {
            while(n%i==0)
            {
                if(n!=i) cout<<i<<"*"; 
                else cout<<i; 
                n/=i;
            }
        }
       if(n!=1)cout<<"*"<<n;
    }
}

开始运行check.bat开始对拍。

出现差异：

上面显示测试代码的输出是*268729，正确代码是268729。这时候找到差异，再看输入文件：

也就是说，在样例为 268729 时两个程序产生了差异，根据差异来修改代码即可。写完了可以再拍。

注意：样例构造函数不可以使用ios::sync_with_stdio(0);与cin.tie(0);。