文章目录

对拍技巧详解更新日志前言原理介绍实现1. 数据生成器(gen.cpp)1. 生成 1 ~ X 之间的正整数2. 生成[L,R]范围内的整数3. 生成特定条件的数4. 一些思想上的建议

2. 暴力程序(baoLi.cpp)3. 优化后的程序4. 检验程序5.最后一步

小结

对拍技巧详解

更新日志

update on 20240803 修正了 Windows 系统下 check.bat 中驴头不对马嘴的文件名

前言

这篇文章编写不易，求你先点个赞，谢谢！

对于各位 OIers 来说，在考场上遇到一道很复杂的大模拟的题的时候，你肯定是会先写出一个能得到部分分的暴力算法，再在其基础上进行算法优化，试图取得更高的分数。

但是，你有时候不敢肯定你优化后的代码就一定是对的。

所以，到底应该怎么检验自己优化后代码的正确性呢？

这篇文章将带来一个很有用的方法：对拍！

请注意，由于这篇文章中的内容大都环环相扣，所以不建议阅读时跳过任何部分

原理介绍

我们这个对拍分为以下几步：

利用数据生成器(gen.cpp)随机生成一组不是很大的数据(data.txt)（不然你的暴力会死活都跑不出来）让你一开始写的那个暴力程序(baoLi.cpp)在读入这组数据后跑出一个结果(result1.txt)让你优化后吃不准对不对的程序(youHua.cpp)也用这组数据跑出一个结果(result2.txt)利用电脑自带的比较文件命令 去比较你的这两个结果，如果一样，说明正确，输出 AC，否则说明有误，输出WA，并终止对拍程序

非常妙吧！

实现

我是在 Mac 下进行演示的，所以

对于 Windows 用户，如果在两个操作系统下有什么不同的话，我会特殊说明的。

PS: 为了照顾到各种电脑，本教程中一律使用 C++ 中最为简朴的 freopen 来处理文件的读写，而不使用一些容易使某些电脑认不得的 < 或 > 的文件操作符号（这句话看不懂也不影响任何东西）

首先，对于使用 Mac 或 Linux 的读者你需要这么建立一个文件夹：

而对于使用 Windows 的读者，请将以上图片中的 check.cpp 改成 check.bat 来建文件夹。

然后，我们一步一步来。

我们以计算 a + b 为例，哈哈哈。

1. 数据生成器(gen.cpp)

先上对于 a + b 这题的数据生成器代码，你直接去看里面的注释就可以了

#include

using namespace std;

#define int long long

signed main()

{

freopen("data.txt","w",stdout);

// 这是为了将生成出来的数据放入 data.txt 中，方便后续读取使用

srand(time(0));

// 设置随机种子，注意：这里必须不能是定值，不然无论如何随机出来的数据都是一样的了！

// 建议使用 time(0) 即函数返回的当前时间来作为种子

int a = rand() % 50000 + 1;

// 随机一个 a 出来

/*

rand() 函数会利用 C++ 中的一个伪随机数生成算法返回一个“随机数”

加 1 的目的：

(rand() % 50000) 这个表达式的值的范围只有 0 ~ 49999（因为有取模）

而我们如果想让 a 是从 1 ~ 50000 之间随机取出的数，就应当加 1，好理解吧

*/

int b = rand() % 50000 + 1;

// 生成 b 的原理与 a 相同

cout << a << " " << b << "\n";

return 0;

}

那么除了 a + b 这道简单的题外，我有一些数据生成的技巧：

1. 生成 1 ~ X 之间的正整数

那么应当是

int a = rand() % x + 1;

这个前文有提到过为什么，这里就不再赘述

2. 生成[L,R]范围内的整数

这个相比于 1 应该更加通用，因为 1 相当于是它的一种特殊情况。

int a = rand() % (r - l + 1) + l;

那在这里 r - l + 1 就是一个偏差值，相当于是表示 a 比 l 大了多少，

rand() % (r - l + 1) 的范围在 0 ~ (r - l) 之间，

而加上 l 之后范围偏到了 l ~ r 之间，符合要求！

3. 生成特定条件的数

这里为了让你有较高的可自定义性，给出一些伪代码，提供一个思路

定义 x; // 类型可以自定义

x = [获取随机数的方法]; // 方法可以自定义

while(!(x 应符合的条件)) // 只要不满足条件就继续，（条件也可以自定义）

x = [获取随机数的方法]; // 再次进行随机

但是，如果用这个思路，你需要注意一点：如果你的条件特别苛刻，而你的随机范围又特别大，这容易导致你的这段代码特别慢，从而影响对拍效率。所以在数据生成方面也应当仔细考虑。

4. 一些思想上的建议

想想看，对拍是为了什么，它是为了让暴力程序和优化后的程序跑同一组数据后比对结果的，但是如果你的数据太大了，容易导致你的暴力程序都跑不出结果（哈哈哈），所以在定生成的数据的范围的时候，请注意不要定过大。

还有一点，对于复杂的大模拟题，随机数据其实很弱，是不一定能 hack 掉你的代码的，所以在对拍正确多组数据后，请务必不要掉以轻心，请仔细思考还有什么小点没考虑到，并依据这种特殊性质去修改 gen.cpp 来制造 hack 数据。

2. 暴力程序(baoLi.cpp)

还是对于 a + b 这题来看，暴力程序长这样：（很好懂吧

#include

using namespace std;

#define int long long

signed main()

{

freopen("data.txt","r",stdin); // 从 gen.cpp 生成的数据中读入

freopen("result1.txt","w",stdout); // 将运行结果写入 result1.txt 中

int a,b;

cin >> a >> b;

// 一下为特别暴力的做法

int ans = 0;

for(int i = 1; i <= a; i++)

ans++;

for(int j = 1; j <= b; j++)

ans++;

cout << ans << "\n";

return 0;

}

如果你看了晕，我来总结一下，说白了就是在你编写好的暴力程序的 main() 函数里的最前面加上这两行代码即可：

freopen("data.txt","r",stdin); // 从 gen.cpp 生成的数据中读入

freopen("result1.txt","w",stdout); // 将运行结果写入 result1.txt 中

3. 优化后的程序

还是对于 a + b 这道题，优化后的程序应该如此：

#include

using namespace std;

#define int long long

signed main()

{

freopen("data.txt","r",stdin); // 从 gen.cpp 生成的数据中读入

freopen("result2.txt","w",stdout); // 将运行结果写入 result2.txt 中

int a,b;

cin >> a >> b;

cout << a + b << "\n";

return 0;

}

总结一下，就是在 main() 函数里的最前面加上以下两句：

freopen("data.txt","r",stdin); // 从 gen.cpp 生成的数据中读入

freopen("result2.txt","w",stdout); // 将运行结果写入 result2.txt 中

4. 检验程序

注意了，前三个程序无论在 Mac 下还是 Windows 下都是通用的，但到了这里，这个检验程序需要调用系统指令，所以开始有了一些区别。

Mac 或 Linux 下的 cpp 检验程序（这两个操作系统都通用）：（仔细看代码里的注释，解释都在里面）

#include

using namespace std;

#define int long long

signed main()

{

system("clear"); // 为了整洁，先清空屏幕

cout << "对拍检验程序启动\n\n"; // 提示语句

cout << "开始编译数据生成器\n"; // 提示语句

system("g++ gen.cpp -o gen"); // 重新编译 gen.cpp

cout << "编译成功\n\n"; // 提示语句

cout << "开始编译暴力程序\n"; // 提示语句

system("g++ baoLi.cpp -o baoLi"); // 重新编译 baoLi.cpp

cout << "编译成功\n\n"; // 提示语句

cout << "开始编译优化程序\n"; // 提示语句

system("g++ youHua.cpp -o youHua"); // 重新编译 youHua.cpp

cout << "编译成功\n\n"; // 提示语句

cout << "开始对拍测试\n\n"; // 提示语句

int testCase = 0; // 定义测试点编号

while(true)

{

testCase++; // 每次测试点编号都加一

system("./gen"); // 生成数据

system("./baoLi"); // 运行暴力代码

int TTT = clock(); // 记录要测试的代码运行前的时间

system("./youHua"); // 运行要测试的优化后的代码

cout << "Test case #" << testCase << " Time: " << (double)(clock() - TTT) / CLOCKS_PER_SEC << "s\n";

// 将运行 youHua 后的时间减去运行 youHua 前的时间，得到这份代码跑了多久，并输出

if(system("diff result1.txt result2.txt") == 0)

// 这个 diff 是 Mac 以及 Linux 下都有的用于非常简陋地比较两个文件是否一样的指令

// diff 指令返回 0 表示一样，返回 1 表示有差异

cout << "Accepted on test case #" << testCase << "\n\n";

else

{

cout << "Wrong answer on test case #" << testCase << "\n\n";

break;

// 为了保存下来这组跑出错误的数据以便后续 debug，我们迅速终止对拍并留住这组数据

}

}

cout << "对拍结束！\n"; // 提示语句

system("rm gen baoLi youHua check");

cout << "已删除临时文件！\n\n"; // 提示语句

// 将程序编译生成的临时可执行文件删除，如果想保留可执行文件的话可以将这两行代码注释掉

return 0;

}

而 Windows 下有极大的不同！！！

由于如 diff、./、g++ ... -o ... 等指令在 Windows 系统中没有或不一定有，我们得放弃用 C++ 这门语言来写 check 了

我们要用一个批处理文件，它的名字应为 check.bat，注意后缀是 .bat！

代码长这样：

@echo off

:start

gen.exe

baoLi.exe

youHua.exe

fc result1.txt result2.txt

if not errorlevel 1 goto start

pause

go start

很明显，这个脚本会比前面 Mac 下的那个 cpp 简陋很多，但我也没什么办法

由于 bat 代码中写注释太繁琐了，咱直接一行一行讲吧：

其他东西都不用管，我就讲一下这里的核心吧

（由于我现在手头是 Mac 电脑，而这个 bat 是我很久以前写的，所以我也无法运行它看结果，只能凭之前的记忆讲一下）

第三行 gen.exe 意思就是运行数据生成器编译后产生的 .exe文件 第四行、第五行同理

所以在 Windows 下，在运行 check.bat 前，你得先用 Dev-C++ 或者任意其他 IDE 编译 gen.cpp、baoLi.cpp、youHua.cpp 这三个代码，

并且获得它们对应的可执行文件（ .exe文件）

再看第六行 fc 正是 Windows 下自带的比较文件的指令，可以理解成与 Mac 下的 diff 差不多，也是两个文件一样就返回 0，不一样返回 1，

对于第七行，它的用途是对于前一行 fc 返回回来的值，如果不是 1 说明正确，则继续对拍，不然停下，并等待（pause）。

5.最后一步

大功告成！

\huge{大功告成！}

大功告成！

你仅需编译运行 check.cpp 或运行 check.bat 即可。

Mac 运行结果如下：

你的 youHua.cpp 如果写对了，检验程序运行后会是这样（也就是每组数据都AC）：

如果写的有问题并且被检验出来了（即有一组数据 WA了），那么会是这样：

小结

对拍是一个非常实用的赛场技巧，它可能看起来步骤非常多，但是你精通对拍的概念和本质了之后，根据对拍本身的原理就可以轻松地对拍了。

这篇文章耗时将近一周（我每天抽空写一点），请务必轻按鼠标点一个赞，谢谢！

如果发现这篇文章有任何不清楚或不正确的地方，欢迎各位读者私信我或评论来提供建议，我将在看见后进行更改。