详解—对拍

对拍

定义：

什么是对拍？当我们的程序过了样例，是否意味着它一定能AC呢？显然大多数情况下都是不行的。所以我们需要自己设计一些数据来测试我们的程序，但有的题目数据很大，我们肉眼无法看出程序计算的结果是否正确，手工计算又非常耗时，在紧张的比赛中，我们该怎么应对呢？于是有了对拍。对拍简单的说就是当你写完一个题目的程序以后，再写一个暴力求解该题目的程序，然后自己生成一些测试数据，看同样的数据，两个程序输出的结果是否相同，不同意味着被对拍的程序有问题。以此来帮助你修改程序，提高通过率的方法，我们称为对拍。

对拍的例子1

【题目描述】

输入n个整数,现在有m个形如[x,y]的提问，即问第x个数到第y个数之和是多少？现在需要你写一程序对每个提问做出快速回答。 1<=n<=100000 1<=m<=50000

输入格式：第一行，两个整数n和m 第二行，n个空格间隔的整数,每个整数的范围在[-10000,10000]之间接下来m行，每行两个整数x和y，表示一次询问的区间(x<=y)

输出格式： m行，每行一个整数，对应一次提问的答案

输入样例： 5 3 1 3 2 7 9 1 2 2 5 3 4

输出样例： 4 21 9

第一步：此题显然是前缀和，于是写代表正解的程序（ZhengJie.cpp）

 1 int Sum[100005];
 2 int main()
 3 {
 4     freopen("data.in","r",stdin);                  //从文件data.in中读入数据
 5     freopen("ZhengJie.out","w",stdout);    //输出的结果存在ZhengJie.out文件中
 6     int i,n,m,tmp,x,y;
 7     scanf("%d%d",&n,&m);
 8     for(i=1;i<=n;i++)
 9     {
10           scanf("%d",&tmp);
11           Sum[i]=Sum[i-1]+tmp;
12     }
13     for(i=1;i<=m;i++)
14     {
15          scanf("%d%d",&x,&y);
16          printf("%d
",Sum[y]-Sum[x-1]);
17     }
18 }
19 
20 /*
21    我们把这个程序保存为ZhengJie.cpp,但这个程序是否正确呢？
22    我们再写一个暴力程序来验证它
23 */

第二步：写一个暴力程序，这里我写的是暴力枚举(BaoLi.cpp)

 1 int a[100005];
 2 int main()
 3 {
 4     freopen("data.in","r",stdin);            //注意，暴力程序读入的数据仍然是data.in
 5     freopen("BaoLi.out","w",stdout);    //暴力程序输出的结果是BaoLi.out
 6     int n,m,i,j,x,y,ans;
 7                scanf("%d%d",&n,&m);
 8                for(i=1;i<=n;i++)scanf("%d",&a[i]);
 9                for(i=1;i<=m;i++)
10                {
11                       scanf("%d%d",&x,&y);
12                       ans=0;
13                       for(j=x;j<=y;j++)ans+=a[j];
14                       printf("%d
",ans);
15                }
16 }
17    我们把这个程序保存为BaoLi.cpp   注意：我们不在乎暴力程序效率，只需要保证它的结果是正确的就行了。

第3步：我们还需要一个生成随机数据的程序（MakeData.cpp）

 1 //该程序按照题目给定的格式生成随机数据。
 2 #include<cstdlib>                                         //加入这个包才能使用随机函数rand()
 3 #include<cstdio>
 4 #include<ctime>                                           //加入这个包就能以时间为种子初始化随机函数
 5 #include<iostream>
 6 using namespace std;
 7 int main()
 8 {
 9     freopen("data.in","w",stdout);                        //注意：该程序生成的数据到data.in中
10     srand(time(NULL));                                          //重要：初始化随机函数，以时间为种子
11     int n=rand()%10000+1;                                 //生成一个1到10000之间的随机整数n
12     int m=rand()%10000+1;
13     printf("%d %d
",n,m);
14     for(int i=1;i<=n;i++)printf("%d ",rand()%20000-rand()%10000);//生成-10000到10000间的数字
15     printf("
");
16     for(int i=1;i<=m;i++)
17     {
18            int x=rand()%n+1;                                     //保证生成的数据是x<=y
19            int y=x+rand()%n+1;
20            if(y>n)y=n;
21            printf("%d %d
",x,y);
22     }
23 }
24 注意：
25 rand()只能生成0到32767之间的随机整数，如果要生成1到50000之间的整数，可以写成：
26 rand()%30000+rand()%20000+1

第4步：写windows对拍文件(对拍.bat)

注意：今天学的是在Windows下的对拍！全国比赛是在linux系统里写程序，linux下的对拍我们以后再谈！

这里提供两种比较麻烦的数据生成模板

树

#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;
int main()
{
    //节点数量 
    int n=100000;
    //文件名 
    char file_name[100]="datax.in";
    
    srand(time(0));
    FILE* f=fopen(file_name,"w");
    fprintf(f,"%d
",n);
    for(int i=2;i<=n;i++)
    {
        int j=i-1-rand()%7;
        j=j<1?1:j;
        fprintf(f,"%d %d
",j,i);
    }
    
    return 0;
}

比如说这道题的数据程序（自己感觉比较典型）

修改程序如下

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    srand(time(0));//在第一行保证n是随机的 
    int n=rand()%2000;
    char file_name[100]="1.in";//我是输出在1.in里面的 
    FILE* f=fopen(file_name,"w");
    fprintf(f,"%d ",n);//输出n 
    int k=rand()%2000;
    fprintf(f,"%d
",n);//输出k 
    for(int i=1;i<=n;i++)
    {
        int u=rand()%2000;
        fprintf(f,"%d ",u);//输出a[i] 
}
    cout<<endl;
    for(int i=2;i<=n;i++)
    {
        int j=i-1-rand()%7;
        j=j<1?1:j;
        fprintf(f,"%d %d
",j,i);//树的输出 
    }
    
    return 0;
}

看看结果

数据是有大有小的

在对拍之前还要注意要先编译所有cpp，保证在同一文件夹下有exe文件

然后就可以愉快的对拍了

图

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <set>
using namespace std;
int main()
{
    //节点数量 
    int n=100000;
    //边数量
    int m=500000; 
    //文件名 
    char file_name[100]="datax.in";
    
    srand(time(0));
    FILE* f=fopen(file_name,"w");
    fprintf(f,"%d %d
",n,m);
    static int vertex[100000+5];
    for(int i=2;i<=n;i++)
    {
        int j=(rand()<<15|rand())%i+1;
        vertex[i]=vertex[j];
        vertex[j]=i;
    }
    set<pair<int,int> > edge;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        while(true)
        {
            u=(rand()<<15|rand())%n+1;
            v=u+1+rand()%10;
            if(v<=n&&edge.find(make_pair(u,v))==edge.end())
                break;
        }
        fprintf(f,"%d %d
",vertex[u],vertex[v]);
        edge.insert(make_pair(u,v));
    }
    return 0;
}