利用 Windows 或 linux 简单脚本，自动化、批量化运行“数据生成程序” 和两份不同的“问题求解程序”，并对两份程序的输出结果进行比对，这个过程我们称为“对拍”。

对拍前需要编写好三个程序：

1. 根据题目要求，数据生成程序，名为 “makedata.cpp”,该程序将生成的数据写入 “data.in” 文件中;

2. “暴力”程序，或其他选手的正解，名为 “bf.cpp”，该程序将生成的数据写入 “data.ans” 文件中;

3. 自己编写的正解，即准备提交评测的程序，名为“sol.cpp”，该程序将生成的数据写入 “data.out” 文件中；

依次编译这三个文件，得到三个可执行文件，在 Windows 下可以得到 makedate.exe,bf.exe,sol.exe

接下来，就是编写脚本，依次循环执行一下过程

1. 运行随机数据生成器 makedata.exe
2. 运行“暴力程序” bf.exe
3. 运行“选手正解” sol.exe
4. 比对文件 data.ans 和 data.out 的内容是否一致。

Windows 和类 Unix 下有 bat 批处理脚本和 bash 脚本。 不过，为了避免介入一门新的脚本语言，我们可以用C++语言来编写“对拍”程序。

头文件cstdlib(stdlib.h) 提供了一个函数 system ,它接受一个字符串参数，并把字符串作为系统命令执行。 例如代码 system("C:\makedata.exe") 执行C盘更目录下 makedata.exe 程序。

Windows 系统命令 fc 或类 Unix 系统命令 diff 可以执行文件比对工作，它们接受两个文件路径，比较二者是否一致，如果一致，返回0，否则返回非零值。

Windows 系统对拍程序：

#include <cstdio>
#include <cstdlib>

int main() {
  // For Windows
  // 对拍时不开文件输入输出
  // 当然，这段程序也可以改写成批处理的形式
  int t=0;
  while (true) {
    system("makedata.exe > data.in");  // 数据生成器将生成数据写入输入文件
    system("bf.exe < data.in > data.ans");  // 获取程序1输出
    system("sol.exe < data.in > data.out");  // 获取程序2输出
    if (system("fc data.ans data.out")) {
      // 该行语句比对输入输出
      // fc返回0时表示输出一致，否则表示有不同处
      puts("Wrong Answer\n");
      system("pause");  // 方便查看不同处
      return 0;
      // 该输入数据已经存放在test.in文件中，可以直接利用进行调试
    }
    else
      printf("%d Accepted\n",++t);
  }
}

类Unix 系统对拍程序

将上面程序中 system("fc data.ans data.out") 改为 system("diff data.ans data.out")

NoiLinux 下对拍参考代码：

int t=0;
    while(true)
    {
        system("./makedata > data.in");
        system("./bf < data.in > data.ans");
        double st=clock();  //记录开始时间
        system("./sol < data.in > data.out");
        double ed=clock();  //记录结束时间
        if(system("diff data.ans data.out"))
        {
            puts("Wrong Answer!\n");
            system("pause");
            return 0;
        }
        else 
            printf("%d Accept! , time : %0.2lf ms\n",++t,ed-st);

    }

对拍举例

接下来以 [CSP-J2024T3]小木棍 为例演示在 OI 赛制下如何对拍。

【题意】：给定 $n$ 根小木棍，拼成一个正整数数码，恰好用完 $n$ 根拼成最小的数字是多少？（拼成数码 0-9 分别使用：{6,2,5,5,4,5,6,3,7,6}）

分析：只有当 $n=1$ 时，无法拼出数码数字，当 $n>=2$ 时可以拼出，为什么？如果拼数码 1 和 7 使用 2、3 根小木棍，若拼 x 个 1 y 个 7 , 即 $2x+3y$ ，$2x+3y$ 可以表示出任意大于 2 的数值。

1. 暴力程序

   当 $n>=2$ 可以暴力枚举数字 $i$, 计算数字 $i$ 使用几根小木棍，枚举到第一个符合条件的 $i$ 就是答案。这种方法，时间复杂度太大，当 $n$ 较大时，会超时。但思路简单，可以作为对拍暴力程序。复制下面的代码，另存为 bf.cpp ,方便之后对拍使用。

   #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    int a[10]={6,2,5,5,4,5,6,3,7,6};
    int cal(int x)
    {
    	int num=0;
    	while(x)
    	{
    		num+=a[x%10];
    		x=x/10;
    	}
    	return num;
    }
    int work(int n)
    {
    	if(n==1)return -1;
    	for(int i=1; ;i++)
    		if(cal(i)==n)return i;
    }
    int main()
    {
    	ios::sync_with_stdio(false);cin.tie(0);
    	int t;
    	cin>>t;
    	while(t--)
    	{
    		int n;
    		cin>>n;
    		cout<<work(n)<<"\n";
    	}	
    	return 0;
    }
   
   

2. 贪心

   我们发现数码 8 使用的小木棍最多，那么拼出的数字最小，那么首先要位数少，优先拼数码 8 可以使得数字位数少。但可能会有多余的小木棍，不同的余数对应不同的情况，可以进行分类讨论。

   设：$m=n/7,r=n$

   • 当余数 $r$ 为 0 ：答案为 m 个 '8'

   • 当余数 $r$ 为 1 ：

     • 当 n=1 时：无解，输出 -1
     • 当 n=7k+1 时： 少拼一个 8，先输出 “10”，再输出 m-1 个 '8'

   • 当余数 $r$ 为 2 ：先输出 “1”，再输出 m 个 '8'

   • 当余数 $r$ 为 3 ：

     • 当 n=3 时：输出 “7”
     • 当 n=10 时：输出 “22”
     • 当 n=7k+3 且 n>=17 时: 少拼两个 8 ，先输出 “200” ，再输出 m-2 个 ‘8’

   • 当余数 $r$ 为 4 ：

     • 当 n=4 时：输出 ‘4’
     • 当 n=7k+4 时：少拼一个 8 ，先输出 “20”，再输出 m-1 个 ‘8’

   • 当余数 $r$ 为 5 ：先输出一个 ‘2’，再输出 m 个 ‘8’

   • 当余数 $r$ 为 6 ：先输出一个 ‘6’，再输出 m 个 ‘8’

   参考代码如下，可以复制粘贴另存为 sol.cpp:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void print(int m)
{
  while(m--)cout<<'8';
}
void cal(int n)
{
  int m=n/7,r=n%7;
  if(r==0)print(m);
    else if(r==1)
    {
      if(n==1)cout<<-1;
      else cout<<"10",print(m-1);
  }
  else if(r==2)cout<<"1",print(m);
  else if(r==3)
  {
    if(n==3)cout<<'7';
    else if(n==10)cout<<"22",print(m-1);
    else cout<<"200",print(m-2);
  }
  else if(r==4)
  {
    if(n==4)cout<<"4";
    else cout<<"20",print(m-1);
  }
  else if(r==5)
  {
    if(n==5)cout<<"2";
    else cout<<"2",print(m);
  }
  else
  {
    if(n==6)cout<<"6";
    else cout<<"6",print(m);
  }
}
int main()
{
   ios::sync_with_stdio(0);
   cin.tie(0);
   int t;
   cin>>t;
   while(t--)
   {
      int n;
      cin>>n;
      cal(n);
      cout<<"\n";
   }
   return 0;
}

**分类较多**，容易遗漏一些情况，这就使得在 OI 赛制下丢分，可以与暴力对拍，降低丢分失误。

3. 造数据

   可以复制粘贴下面程序，另存为“makedata.cpp”

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0)^clock());
ll rad(ll l,ll r)
{
  return rnd()%(r-l+1)+l;
}
int main()
{
  ios::sync_with_stdio(false);cin.tie(0);
  int t;
  t=rad(1,50);
  cout<<t<<"\n";
  for(int i=1;i<=t;i++)
    cout<<i<<"\n";
    //或者 cout<<rad(1,50) 
  return 0;
}

4. 对拍

   #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    int main()
    {
    	ios::sync_with_stdio(false);cin.tie(0);
    	//先编译 需要配置好环境变量
    	//如果已经生成为 exe ,可以跳过这个步骤 
    	system("g++ makedata.cpp -o makedata.exe -O2 -std=c++14");
    	system("g++ bf.cpp -o bf.exe -O2 -std=c++14");
    	system("g++ sol.cpp -o sol.exe -O2 -std=c++14");
    	int t=0;
    	while(true)
    	{
    		system("makedata.exe > data.in");
    		system("bf.exe < data.in > data.ans");
    		system("sol.exe  < data.in > data.out");
    		if(system("fc data.ans data.out"))
    		{
    			cout<<"Wrong Answer!\n";
    			return 0;
    		} 
    		else printf("%d Accept!\n",++t);
    	} 	
    	return 0;
    }
   

   注意：在此对拍程序中，system("g++ makedata.cpp -o makedata.exe -O2 -std=c++14"); ,先编译，Windows 使用 g++ 编译需要先配置好 g++环境变量。当然如果已经编译生成 exe 文件，可以跳过编译这个步骤。

学习完毕

{{ select(1) }}

• YES
• NO