分享关于Windows系统下的C++对拍写法
对拍是什么
对拍是一种用于检查我们所写程序的正确性的方法
对拍干什么
在比赛中,我们打出的”正解程序”在遇上大样例时不一定对,但简单易写的暴力算法又很有可能TLE.对拍的作用是同时运行两个程序,以自创的样例(通过随机数)来检验”正解”的正确性
对拍怎么写——最重要的部分
以下面这道题为例:
输入n个数,询问第x个数到第y个数的和是多少
输入:
第一行,一个整数N(1<=N<=100000),表示数的个数
第二行,N个整数a(-10000<=a<=10000)，表示这N个数
第三行,一个整数M(1<=M<=100000),表示询问个数
接下来M行,每行两个整数x y,表示询问区间
输出:
M行,对于每个询问,输出第x个数到第y个数的和
输入样例:
5
1 2 3 5 4
5
1 2
2 3
1 4
2 4
1 5
输出样例:
3
4
11
10
15
1.写出”正解程序”, 明显是前缀和,并命名为”ZhengJie.cpp” (cpp是c++文件后缀名)
//ZhengJie.cpp
#include <cstdio>
using namespace std;
const int N = 1e5 + 5;
int n;
int m;
int sum[N];
int main ()
{
freopen ("Data.in", "r", stdin);
freopen ("ZhengJie.out", "w", stdout);
//这两句等会儿讲
scanf ("%d", &n);
for (int i = 1; i <= n; i ++)
{
int a;
scanf ("%d", &a);
sum[i] = sum[i - 1] + a;
}
scanf ("%d", &m);
for (int i = 1; i <= m; i ++)
{
int l, r;
scanf ("%d %d", &l, &r);
printf ("%d\n", sum[r] - sum[l - 1]);
}
return 0;
}
2.可是,这个”正解程序”是否正确呢?这时我们写出我们的暴力程序,并命名为”BaoLi.cpp”, 暴力程序不必追求时间复杂度,只需要程序结果正确即可
//BaoLi.cpp
#include <cstdio>
using namespace std;
const int N = 1e5 + 5;
int n;
int m;
int a[N];
int main ()
{
freopen ("Data.in", "r", stdin);
freopen ("BaoLi.out", "w", stdout);
scanf ("%d", &n);
for (int i = 1; i <= n; i ++)
scanf ("%d", &a[i]);
scanf ("%d", &m);
for (int i = 1; i <= m; i ++)
{
int l, r, ans = 0;
scanf ("%d %d", &l, &r);
for (int j = l; j <= r; j ++)
ans += a[j];
printf ("%d\n", ans);
}
return 0;
}
3.这时,就需要去构造样例了手动构造样例显然不现实,于是我们可以用c++中的rand函数构造样例, 并命名为MakeData.cpp
//MakeData.cpp
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <algorithm>
using namespace std;
inline int random (int n)
{
return (unsigned long long) rand * rand () % n;
}
int main ()
{
freopen ("Data.in", "w", stdout);
//把数据放入Data.in里面,"ZhengJie"和"BaoLi"将会从里面读入
srand (time (NULL));
int n = random (1e5) + 1;
printf ("%d\n", n);
//构造N
for (int i = 1; i <= n; i ++)
printf ("%d ", random (20000) - 10000);
//构造a,-10000 < a < 10000
printf ("\n");
int m = random (1e5) + 1;
printf ("%d\n", m);
//构造m
for (int i = 1; i <= m; i ++)
{
int l = random (n) + 1;
int r = random (n) + 1;
if (l > r)
swap (l, r);
//保证l <= r
printf ("%d %d\n", l, r);
}
return 0;
}
这也是最难理解的部分,对于不同的题目,构造的随机数也不同,需要随机应变,具体我会在下一篇里讲
4.在桌面上新建一个文本文档,在里面输入
@ echo off
:loop
MakeData.exe
ZhengJie.exe
BaoLi.exe
fc ZhengJie.out BaoLi.out
if not errorlevel 1 goto loop
pause
:end
然后把文本文档保存,重命名为”对拍.bat”(如果没有.txt后缀,就打开计算机->组织->文件夹和搜索选项->查看->关闭”隐藏已知类型文件的扩展名”->应用->确定)
5.运行步骤123里的所有代码(目的是创建.exe文件),再双击”对拍.bat”
6.然后你将会看到两种情景:
①”正解”正确,其答案与暴力得到的答案完全正确
②”正解”错误
%%% tql