对拍和调试

前言

对拍什么的大家都会，但我今天要来展示一下炒鸡对拍！

你们普通的对拍无非就是从蓝书上学来的，可是那样的生成数据并不是均匀的！

举个简单的例子：

你使用 rand 生成了两个集合：

$(1，2)$ 和 $(1, 2)$，它们相乘能组成的数只有：

$$(1, 2, 4)$$

也就是说你根本就没找出 3 这个数来！

如此一来，你生成的数并不均匀，所以这样对拍是可能锅掉的。

那么我们就要使用我们的……

炒鸡对拍了！

ps：以下方法仅使用于 C++ 版本不低于 C++11 的方法，不过现在 CCF 都给你 C++14 了……

生成数据

首先我们要知道 STL 里边的一个新类型：

mt19937

这个到底是什么呢？因为探讨它和 OI 关系不大我们就不说了（好吧就是我不知道）。

然后我们这么写就会有一个生成函数：

mt19937 rd(time(0));

现在有了生成函数，我们去写一个生成一大堆均匀的数的东西吧：

uniform_int_distribution <int> range(1, 1e5);

什么你记不住？会读就会写。

然后我们完成了我们呢的生成方法，现在去按要求构造数据即可，比如我们构造个 A + B 的：

cout << range(rd) << " " << range(rd);

整体：

#include <cstdio>
#include <algorithm>
#include <ctime>
#include <iostream>
#include <random>
#include <cstdlib>
using namespace std;

mt19937 rd(time(0));

int main() {
    uniform_int_distribution <int> range(1, 1e5);
    cout << range(rd) << " " << range(rd);
    return 0;
}

然后我们构造部分就解决了。

对拍

首先我们需要去写一个一定正确的朴素程序，确保答案一定正确。

然后写一份我们自己的程序。

接下来我们要写一个检查程序。

我建议大家学学命令行，这里有奇效！

C++ 里有一个强大的函数叫 system，用这个东西可以用来在 C++ 里边执行我们的命令行。

我们在 C++ 中这么写便会执行一次编译：

system("g++ sol.cpp -o sol -std=c++14");

解释一下，前面 4 个部分是用来编译你的文件的，后面这句是在 C++14 的标准下编译运行。如果你电脑上没有 C++14 那这句话是失效的，可以换个更高版本的 Dev 来解决问题。

如果你要吸氧，只需要在 std=c++14 后边加个空格再加个 -O2 即可，注意 O 要大写！不然你就会跟 L_fire 一样每次编译都会跳出个 2.exe 来。

刚才那句编译命令编译好了我们自己的程序，那么让我们把要编译的都编译下吧：

system("g++ brute.cpp -o brute -std=c++14")
system("g++ gen.cpp -o gen -std=c++14")

上面两句编译了朴素程序和数据生成程序。

那么怎么对拍呢？我们要将生成的数据分别丢进两个程序里，观察它们的输出结果是否一致。

for(int i=l; i <= r; i++) { // 这里的 l，r 是你需要测定的数据范围
    system("gen > data.in"); // 将生成的数据放入一个输入文件中
    system("sol < data.in > data,out"); // 将数据放入自己的程序中并将结果放入一个输出文件中
    system("brute < data.in > data.ans"); // 同上，由于文件不能重名我们改成 .ans
    
    if(system("fc data.out data.ans")) { // 比对两个输出结果，用 fc 命令进行对比，如果相同返回 0，不相同则返回 1
        cout << "WA on#" << i << endl;
        return 0; // 找到了错误数据返回，然后退出程序去看错误的数据
    } else {
        cout << "AC on#" << i << endl； // 这里就是为了防止干等用的
    }
}

整体的 Code 如下：

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    system("g++ sol.cpp -o sol -std=c++14");
    system("g++ brute.cpp -o brute -std=c++14");
    system("g++ gen.cpp -o gen -std=c++14");
    
    for(int i = 1; i <= 1e5; i++) {
        system("gen > data.in");
        system("sol < data.in > data.out");
        system("brute < data.in > data.ans");
        
        if(system("fc data.out data.ans")) {
            cout << "WA on#" << i << endl;
            return 0;
        } else
            cout << "AC on#" << i << endl;
    }
    return 0;
}

效果如下：

现在我们的炒鸡对拍就完活了。

我们发现找出了错误的数据，明显要调试了，怎么调试呢？

调试大多离不开这几条：

1. 静态查错，按照你的代码逻辑看一遍，如果发现了奇妙的失误可以随手改掉。
2. 输出语句非常好用
3. 减少对调试工具的依赖，否则您将浪费时间。
4. 尝试多构造一些边界数据，看看是否需要特殊判断。

好了，快去愉快地对拍和调试吧！