对拍是什么
对拍,是一个比较实用的工具。它能够非常方便地对于两个程序的输出文件进行比较,可以帮助我们实现一些自动化的比较输出结果的问题。
众所周知,几乎每一道编程题目,都会有某种正解能拿到满分;当我们想不出正解时,我们往往可以打暴力代码来获取部分分数。
但是,当我们觉得有思路写正解,但又担心自己正解写的不对,而恰好,我们又有一个能够暴力骗分的代码。这个时候就可以用到对拍。 暴力骗分代码必须保证正确性,只是超出时间限制,不能出现答案错误的情况。
这样,我们可以造多组数据,让暴力骗分的程序跑一遍,再让我们自己写的正解跑一遍,二者进行多次对比。如果多组数据都显示二者的输出结果一样,那么这个正解大概率没问题。相反地,如果两组数据不同,我们就找到了一组错误数据,方便调试,找到正解哪里出了问题。
这便是对拍。其作用也在上文提出。
利用 timeb 生成毫秒级别随机数
众所周知,重复打开相同的可执行文件,想要输出的数不同,往往需要以时间作为随机种子。
如:
点击查看代码
#include <bits/stdc++.h>
using namespace std;
void solve()
{
srand(time(0));
int a=rand();
cout<<a<<endl;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)solve();
return 0;
}
制作数据生成器#
前置知识:利用 timeb 生成毫秒级别随机数
我们制作的数据要求格式和上面两份代码的输入格式一样。
根据上面,我们可以知道输入的数据为 2 个数,中间有空格分隔。那么,我们的数据生成器就要输出 2 个数,中间也要用空格分隔。
创建一个新的源代码
点击查看代码
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int a=rand(),b=rand();
cout<<a<<" "<<b<<endl;
}
int main()
{
int n;
cin>>n;
struct _timeb T;
_ftime(&T);
srand(T.millitm);
for(int i=1;i<=n;i++)solve();
return 0;
}
这里有个小问题。Windows 系统下 rand() 生成的随机数的范围在 0~32767 之间。如果我们想要得到比 32767 更大的随机数怎么办呢?除了换 Unix 系统外,我还有一个小办法,很实用。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
ll Random(ll mod)
{
ll ans = 2147483647;
return ans = ans * rand() % mod + 1;
}
int main()
{
struct _timeb T;
_ftime(&T);
srand(T.millitm);
ll n;
while (1)
{
n = Random(1000000);
printf("%lld\n", n);
}
return 0;
}