如何对拍？
如何对拍？
dog_emperor
·
2024-01-04 20:07:40
·
科技·工程
前言
本篇只针对不会对拍的小伙伴。
OI 赛制总是挂？不知道怎么哪里错了？找不到 hack 数据？怕找错误太久耽误写其他题时间？对拍能帮你把这些困扰统统解决！
对拍简介
在比赛或做题的时候如果我们想要验证程序是否正确或者想要找到一组 hack 数据时，我们会使用一种叫做 对拍。
我们实现对拍需要准备三个程序：
想要验证的程序 std.cpp。
暴力程序 bl.cpp。
生成随机数据的程序 gen.cpp。
对拍的核心思想就是不停地利用 gen.cpp 来生成随机数据，然后运行 std.cpp 和 bl.cpp，看看结果是否相同，相同就继续，不相同就停下来。
就这样找到一组错的数据。调试完后就继续对拍。我们在比赛中把对拍一直挂在那。我们这里有两点非常重要，如下：
bl.cpp 写地程序一定是要 对的！
gen.cpp 随机出来的数据必须是不一样的！
因为如果 bl.cpp 写的是错的，std.cpp 跑出来的答案又和 bl.cpp 的一样，那只能说明 std.cpp 和 bl.cpp 错的地方一样。而如果随机出来的数据都是一样的，那只能说明对于那一个数据是对的。所以，对拍必须要保证好以上两点。
实现对拍
为了实现对拍，我们需要写一个 bat 文件，怎么写呢？首先在桌面上鼠标右键新建一个 txt 文件，再把后缀 txt 改为 bat，你会发现双击打不开，那就把 bat 文件拖到 Dev-C++ 里写，那样就可以啦！
写的内容如下：
将以上内容超好后，记得保存好 bat 文件哦！
对拍实例
如下图，是一个 01背包 的模板：
（可能有点小，建议 Ctrl + 鼠标滚轮 放大)
我们写完 bat 文件，现在就要来写 std.cpp 和 bl.cpp 啦！这里我们的 std.cpp 也就是正解我们用一个 dp 的做法，而 bl.cpp 也就是暴力的做法我们就写个暴力的会 TLE 的 dfs。
std.cpp 代码如下（01背包模板相信大家都会写，就不讲解了）：
#include
using namespace std;
int n, m, v[1001], w[1001], f[1001];
int main(){
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d%d", &v[i], &w[i]);
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; i++)
for (int j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
printf("%d\n", f[m]);
}
bl.cpp 代码如下（dfs 的就更简单了）：
#include
using namespace std;
int n, m, v[21], w[21], ans = -1;
inline void dfs(int i, int sumv, int sumw) {
if (i == n + 1) {
if (sumv <= m)
ans = max(ans, sumw);
return;
}
dfs(i + 1, sumv, sumw);
dfs(i + 1, sumv + v[i], sumw + w[i]);
}
int main(){
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d%d", &v[i], &w[i]);
dfs(1, 0, 0);
printf("%d\n", ans);
}
现在我们就要写尤为神奇的 gen.cpp 啦！怎么写呢？这是要根据题面中的输入格式的。这个 01背包 模板中先是读入两个数 n 和 m。那么我们就可以用 以下代码：
#include
using namespace std;
int main(){
int n = rand() % 1000 + 1, m = rand() % 1000 + 1;
printf("%d %d\n", n, m);
}
现在我们来看一下，rand() % 1000 + 1 的意思就是在 0 到 1000 中取个随机数，这就要看数据范围，这都题的数据范围是 1000，我们随机到 1000 就好， n 是这样，m 也是同理。最后还要输出来，看看随机到哪两个数。
然后我们再看输入格式，接下来 n 行，每行又两个数 v 和 w，和上面的 n 和 m 一样随机，如下：
#include
using namespace std;
int main(){
int n = rand() % 1000 + 1, m = rand() % 1000 + 1;
printf("%d %d\n", n, m);
for (int i = 1; i <= n; i++) {
int v = rand() % 1000 + 1, m = rand() % 1000 + 1;
printf("%d %d\n", v, w);
}
}
大家又一看，现在我们已经把输入格式里的全部搞定了，那么我们的 gen.cpp 写完了吗？当然没有！还记得我上面强调过的要保证 gen.cpp 随机出来的数据必须不一样吗？那就要再加一个 srand(time(0));！
如下：
#include
using namespace std;
int main(){
srand(time(0));
int n = rand() % 1000 + 1, m = rand() % 1000 + 1;
printf("%d %d\n", n, m);
for (int i = 1; i <= n; i++) {
int v = rand() % 1000 + 1, m = rand() % 1000 + 1;
printf("%d %d\n", v, w);
}
}
现在我们的 std.cpp，bl.cpp 和 gen.cpp 与 bat 文件已经全部搞定了，现在我们要将他们放进一个文件夹里面：
然后我们需要进行以下操作：
然后输进去 cmd，点击换行就会出现一个窗口，你在窗口里再输 g++，他会显示他不认识 g++ 这个东西。
我们该如何解决这个问题呢？请按照以下操作即可解决：
按 windows 键 + Q 搜索编辑系统环境变量，然后点一下，进去。
然后你需要找到你的 Dev-C++ 装在哪，需要把地址复制了，如下操作：
再点开里面的 bin 文件：
然后回到我们的编辑系统环境变量，把这个地址复制到新建的里面，然后点三个确定就行啦！现在大家可以试一试，电脑已经认识 g++ 啦！
然后我们想要开始对拍双击 bat 文件就可以啦！
完了吗，完了，但是
好的，直接干。
linux？
但是有些省份不支持 windows 系统，那么 linux 下的对拍呢？
首先你需要一个虚拟机（如果想在赛前用自行体验的话），然后装入 NOI2.0，具体如何装自己网上找。
还是以 01 背包为例。
具体代码就不展示了，像 std.cpp，bl.cpp，gen.cpp 都是一样的，但是对拍的文件不一样。如下，是一个后缀名为 .sh 的文件。
用的是 Code Blocks。
但是运行也和 windows 下不同，如图。
鼠标右键后会出现一个框，点击框中的最后一项，也就是 Open in Terminal。然后会出来一个框，也可以说是一个命令行。
在这里面输入 sh duipai.sh 然后再换行就可以运行了。注意！中间有空格！，像我们把 .sh 文件命名为 duipai 那就是 duipai.sh，如命名成其他也是类似的。其他的注意事项和 windows 下一样的
linux 不用像 windows 下的需要让系统认识 g++ 而去搞一系列很麻烦的事情。直接就可以运行。
提示
当你写完了对拍，可以双击 bat 文件把他一直挂在后台，拍个几小时也差不多可以算是对了。但是，也不能保证，而且对拍只针对与小数据，大数据是不知道的。因为大数据 bl.cpp 太慢了，就很有可能跑不出来。所以对拍没问题只能代表你的小数据没问题。为了保证你代码的正确性，对拍完之后，可以检查一下你的时间复杂度与爆没爆 int 啊？要不要开 long long 啊？数组过界了吗？之类的问题。
希望本篇对你有用！
