对拍

约 290 个字 71 行代码 预计阅读时间 2 分钟

作用

用程序判断你的程序答案是否正确，有运气成分

步骤

编写正解（你认为的），暴力，数据生成器，对拍器

编译前4个程序，编译运行对拍器，输出对拍结果

不适用

1. TLE和MLE，对拍只能保证正确性
2. 正解就是暴力的题目，你可能暴力写不对
3. corner case，指输入上的边界情况（最大最小数据）和输出上的边界情况（通常出现在构造题，不能套用通解解决，但是确实有可行解）

注意事项

所有文件需在同一文件夹的同一层里

编数据时最好不要用原题数据，暴力会卡死，毕竟只是保证正确性，数据小一点就好

修改文件后需要重新编译，因为调用的是exe

实践

以斐波那契数列为例，这里设递归为暴力，迭代为正解

正解

#include<fstream>
#include<iostream>
using namespace std;
void solve(int n)
{
    int res=0;
    for(int i=1;n>=1;--n)
    {
        res=res+i;
        i=res-i;
    }
    return res;
}
int main()
{
    ifstream in;
    in.open("data.in");
    int n;
    in>>n;
    cout<<solve(n);
    return 0;
}

暴力

#include<fstream>
#include<iostream>
using namespace std;
void solve(int n)
{
    if(n<2)
        return n;
    return solve(n-1)+solve(n-2);
}
int main()
{
    ifstream in;
    in.open("data.in");
    int n;
    in>>n;
    cout<<solve(n);
    return 0;
}

数据生成

#include<fstream>
#include<chrono>
#include<random>
using namespace std;
int main()
{
    ofstream out;
    cout.open("data.in");
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    cout<<rng()%(1e6);
    return 0;
}

检查

system函数是windows操作系统下发出一个DOS命令

fc是file compare的缩写,当两个文件不同时输出1，否则0

#include<cstdlib>
#include<iostream>
using namespace std;
int main()
{
    for(int kase=1;kase<=10;++kase)
    {
        system("dataGenerator.exe > data.in");
        system("Solution.exe < data.in > 1.out");
        system("bruteForce.exe < data.in > 2.out");
        if(system("fc 1.out 2.out"))
        {
            cout<<"Errors found.";
            return 0;
        }
    }
    cout<<"No errors were found.";
    return 0;
}