对拍技巧

对拍技巧

前言

久仰大名,前来学习。

1. 为什么对拍

在 OI 这样的玄学比赛中,程序样例(包括官方给的大样例)全对但没有 AC 的情况十分常见,这时候进行一下对拍就可以帮助我们找到一些不容易发现的 bug(或是在心理上稳定,避免影响后续的做题)。

2. 对拍的原理

其实就是自己造数据自己评测的过程。

3. 如何对拍

对拍必须有如下几个文件:暴力程序,对拍目标程序,数据生成器,评测程序。

其中暴力程序必须保证给出的答案正确。时间,空间不重要。

在 windows 中以上程序中均不需要 freopen,文件读写在评测程序由 windows 控制台命令统一执行。(Linux 用到了再说)。

示例针对 windows 环境。

以给高精度除法程序对拍为例,首先写好暴力程序:

#define rd read()

#include

using namespace std;

typedef long long ll;

ll read(){

ll x=0,f=1;

char c=getchar();

while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}

while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}

return x*f;

}

int main(){

ll a,b;

a=rd;

b=rd;

cout<

return 0;

}

编译运行一遍这个程序,生成一个 .exe 文件,放到一个单独的文件夹中。

把要对拍的程序文件也放到这个文件夹中,同样编译运行一遍这个程序,生成一个 .exe 文件。

制作数据生成器

一般使用 rand() 函数来生成随机数,使用 random_shuffle(.begin(),.end()) 函数生成随机序列。

但是,rand()函数的随机数生成需要一个种子,相同的种子生成的“随机数”是一样的。因此,我们一般使用时间来作为随机数种子。

传统方法是使用 time(0) 函数传入时间作为种子。但是此函数以秒为单位返回时间,这导致在同一秒内运行时随机数种子相同,进而导致随机数相同,如下图:

这时一般使用 windows.h 库中的 Sleep() 函数使程序强制暂停 1s 来生成不同的随机数,如下图:

但在某些结论题中往往数据量小,这样的 1s 会造成很多的时间浪费。

因此我们可以选择以 ms 为单位传入时间。

C++ 我们准备好了一个结构体 _timeb,其成员 millitm 可以获得现实时间一秒中所处的毫秒。(即返回一个无符号整数x,其中 \(0\le x\le 999\))。

配合 ftime() 函数更新时间,我们就有了 1000 组的不同数据。

对于某些程序来说可能组数比较少,但是速度快。

使用 time(0) 生成随机数的代码:

int main(){

srand(time(0));//引入时间作为随机数种子

cout<

}

使用 _timeb 生成随机数的代码:

int main(){

struct _timeb T;//创建 T 对象

_ftime(&T);//使用 _ftime 更新时间(内部的值)

srand(T.millitm);//给予种子

cout<

}

但是,rand() 函数的数据范围是 \(0\le rand() \le 32767\) (windows 环境中)。

想要生成大数,可以使用四个 rand() 相乘获得。

想要限制数据范围,可以用取模的性质实现,有这样的公式:

\[0+k\le rand() \bmod (m+1) +k \le m+k

\]

生成一些区间,一棵树,一个图,一条链的方法看这里。

制作评测程序

windows 的控制台命令可以让我们在外部控制 .exe 文件的输入输出,语法如下:

A.exe > Aout.txt 表示运行相对路径下的可运行程序 A.exe 并将其输出放到同一目录下的 Aout.txt 文件中(没有会自行创建)。

A.exe < Ainput.txt > Aout.txt 表示运行 A.exe 并将 Ainput.txt 作为输入数据(此文件必须存在),其输出放到同一目录下的 Aout.txt 文件中(没有会自行创建)。

fc Aout.txt Bout.txt 表示对 Aout.txt 和 Bout.txt 进行全文比对,如果有不同返回 true,相同返回 false。

以上三条控制台命令在 C++ 中可以用 system() 函数执行,即:

system("A.exe > Aout.txt");

system("A.exe < Ainput.txt > Aout.txt");

system(fc Aout.txt Bout.txt);

于是评测程序的一般步骤为:

运行数据生成文件 rans.exe,将输出放到 in.txt 文件中作为输入数据。

以 in.txt 为数据运行暴力程序 std.exe 并将其返回的正确答案放到 stdans.txt 文件中。

以 in.txt 为数据运行自己的程序 div.exe 并将其返回的正确答案放到 ans.txt 文件中。此过程中可以计算时间,空间等。

全文比较 stdans.txt 和 ans.txt 根据返回值判断正误并返回时间,空间等信息。

可以写出这样的代码:

int main(){

system("rans.exe > in.txt");//数据

system("std.exe < in.txt > stdans.txt");//暴力计算答案

system("div.exe < in.txt > ans.txt");//自己的程序计算答案

if(system("fc stdans.txt ans.txt")){//全文比较,判断正误

cout<<"Wrong Answer"<<'\n';

}

else{

cout<<"Accepted"<<'\n';

}

}

在外面套一个循环就可以不停对拍了。

关于时间空间计算

在调用自己写的程序前使用 clock() 函数获取浮点数时间,同样在调用后也获取一次,两者相减就是程序所用的时间,单位为 ms。

示例:

double beg=clock();

system("addit.exe < in.txt > ans.txt");

double ends=clock();

...

cout<<"Accepted "<

看空间的方法暂时没找到qwq。

迁移自洛谷

相关推荐

微信限额怎么提升额度 微信限额提升额度方法【教程】
目睹的解释及意思
bt365体育在线备用

目睹的解释及意思

11-20 👁️ 7190
LOL新号玩多久才能到7级
bet·365官方网站

LOL新号玩多久才能到7级

09-14 👁️ 1623
厨下净水器选购指南:立升与美而浦的全面对比
bet·365官方网站

厨下净水器选购指南:立升与美而浦的全面对比

12-28 👁️ 5931