[技巧]对拍与数据制作

对拍到底是什么东西?
就是用你自己的程序和正确的暴力或者算法比较数据,来判断自己的数据是否出错。
平时自己感觉上Accept的代码去到OnlineJudge上就无辜RE,WA呢,大的数据调不出来,考场上急需验证自己的程序有没有写错,自己出来题目想测试一下标程有没有出错。这样子就用得上对拍了!我们可以制作小的数据,用暴力和正解比较,查出错误,尽管小数据出错几率很小,但是对拍程序可以一直重复运行,帮我们比较,直到查出错误。
那么需要对拍的我们需要准备多少东西呢?其实真的不多
1. 你需要对拍的程序
2. 自己打的暴力或找到的正解
3. 一个数据制作器
4. 一个对拍程序

前面两个其实都很容易就得到得了,那么对拍程序和数据制作器到底怎么弄呢。
那么我们先从数据制作器开始说吧。

数据制作

数据制作就是我们利用程序或者手出数据给程序测试了。
但是数据制作还是有很多的技巧的。

随机数

随机数作为随机数据制作的基础当然十分重要啦,但是不同平台的随机数也是不一样的。
数据生成以C++作为演示,以后有空谢谢Python毕竟Python写数据生成比C++的好
随机数生成需要头文件cstdlib,随机函数为rand(),在不同系统的rand()随机出来的数据大小也是不一样的,在linux下最大为2147483647,但是在windows底下最大为32767,在Windows下我们可以通过两个或者三个随机数首尾结合在一起来创造一个更大的随机数,如果简单点也可以两个随机数乘起来,但是这样会偶数随机出来的概率会比较多。
rand()函数还有叫一个随机种子的的东西,不同的种子生成出来的随机数也不一样,但是种子默认为0所以我们可以通过srand(x)来给定一个种子x让系统生成随机数。
假如我想每次生成都不一样呢?
我们需要头文件ctime,里面有一个函数time(0)表示返回目前时间代表是时间数字,以秒为单位,那么我们可以用时间来做种子生产随机数,srand(time(0))
那么我们定义一个函数random(x)表示一个随机数模上x的值,我们要生成一个比较大的整数。那么我们就一位一位拆解。

为什么要叠加四次呢,因为那个啥rand()最多5位,long long最多20位,为了防止溢出,我们就最多取3次,有需求的话也可以取4次。为什么不用int为了防止中途叠加时溢出咯。
但是如果要一个实数呢?
我们就生成一个大整数再随机除以10^X就好了,这个的代码就交给你们了。
这样我们就完美解决了随机数的问题。
其他的话各种生成图生成树我也就不在这里多啰嗦了,我一句话总结一下,自己试试咯哈。
1. 图的话随机连接两个点就好
2. 树的话用n-1条边链接点,记得用并查集判环。
3. 区间的话生成两个整数x,y,然后swap使得x \lg y
4. 对于上面的可以使用random_shuffle(E+1,E+n+1)打乱数组。

数据规模

对于每一次的随机数据都要确定好随机规模,对于对拍的程序,最好做到不大不小手工调试也可以调试的那种数据。对于出题的数据的话就要注意一下特殊构造,生成一些极限数据。
这里需要自己实验啦,这个只可意会不可言传
可能是我太菜了吧,有能力时会补回来的

对拍

了解对拍的过程对于了解对拍是十分重要的
1. 调用数据制作程序制作数据
2. 调用标程或暴力取得正确的答案
3. 调用需要队排得程序并取得需要比较的答案
4. 比较两个答案
5. 若相同跳去第一步继续运行,若不返回错误答案

在对拍中,如果我们的数据制作器把数据输出到文件,记得对拍程序加文件输入,对拍和暴力一定要加文件输出或者Vio.exe >Data.ans
具体的我们可以通过DOS批处理命令,也就是所说的cmd或者bat实现
那么我们用A+BProblem进行示范,与我程序对拍的是标程。
那么我们先来膜哈一下对拍,rem是注释行的意思

然后就可以开心的见到

这样就是对拍的结果
假如对拍出错误了?就会

这样告诉你你跟标准输出有多少差异。
这样我们就可以开心取验证自己的程序到底有没有错误了呢。

发表评论

电子邮件地址不会被公开。 必填项已用*标注