对拍

· · 个人记录

本文讲解对拍。

对拍的目的

必须在文章一开头就明确的是，对拍是为了 hack 自己写的代码。最后得到的结果是一个使你的代码输出错误的数据。至于对于数据和代码的分析，不在对拍的应用范围和本文的讨论范围内。

对拍的基本步骤

对拍程序由以下四个程序组成：

  1. 生成数据程序
  2. 一个保证完全一定绝对 100% 正确的程序
  3. 你写的待检验的程序
  4. 检查程序

1.生成数据程序

生成数据程序需要生成符合题目规范和范围的数据，这一点很重要。不然分析了半天，最后发现题目压根不会出现这种情况，那就很浪费时间了。

基本模板

#include <bits/stdc++.h>
using namespace std;
signed main()
{
    freopen("data.in","w",stdout);
    mt19937 rnd(time(0));
    // 输出数据
    int n = 5;
    for(int i = 1; i <= n; i++)
        cout << rnd() % 10 + 1<< ' ';//输出1-10的五个数
}

随机数用 mt19937 是我个人习惯，用 rand 一般也没有什么问题。

2.正确程序

最重要的一点就是一定要一定要完全正确。

基本模板

signed main()
{
    freopen("data.in","r",stdin);
    freopen("T1AC.out","w",stdout);
    // 处理并输出 
}

3.待检验程序

基本模板

int main()
{
    freopen("data.in","r",stdin);
    freopen("T1WA.out","w",stdout);
    // 处理并输出 
}

4.检查程序

基本模板

#include <iostream>
using namespace std;
signed main()
{
    int ti = 0;
    while(1)
    {
        ti++;
        cout << ti << endl;
        system("T1data.exe");// 生成数据程序
        system("T1WA.exe");// 待检验程序
        system("T1AC.exe");// 正确程序
        // 记得编译
        if(system("fc T1AC.out T1WA.out"))
            return 0;
    }
}

这里有几个要点：

  1. ti 是检查程序运行了几次，可以用来估测待测程序正确概率。（并不是对拍必需的东西，但是加上最好，可以通过对拍的次数估测待检测程序的正确性）
  2. system("") 语句执行一个exe程序。
  3. system("fc T1AC.out T1WA.out") 对比 T1AC.out 和 T1WA.out 这两个文件的内容是否相同，有布尔类型的返回值，文件不同时会返回 ture，否则返回 false，无论是否相同都会有输出信息。

文件内容相同时输出如下：

不同时，会输出内容差异，如下：

  1. 执行的三个程序是生成数据程序，正确程序，待检验程序，要写相应文件名，并且记得一定要先生成数据再运行其他两个程序。

运行执行程序就可以了。当出现内容不同的时候会自动停下，此时 data.in 文件里就是 hack 数据。可以打开 -Ofast 加快速度，就是调试的时候记得关（

其他

关于一些数据的构造和随机数内容，详见这里。