对拍程序写法（c++版)

##**前方预警**
**只有有实力和编程非常熟练的学生才可以考虑用这个方法，熟练度一般的，不建议使用，因为你没有多余的时间写这个。**
###**原理**
利用windows的输出输入重定向功能(即改变输入输出的设备)，结合windows的fc(文件比较命令)，结合数据生成器，对程序进行对拍，一脸懵逼的看下图。
![](/api/file/getImage?fileId=61615b83d170a10014000076)
也就是说，你还要额外的多写2个程序。知道为什么我说只有非常熟练的人才能使用这个方法了吧。
###**举个栗子**
##**矩形**
**【问题描述】**
我们都知道，我们生活在矩阵中，矩阵被划分为N行×N列。一个整数被写入矩阵的每个NxN单元格中。为了离开矩阵，我们必须找到矩阵中包含的**最美丽的正方形**（正方形的子矩阵）。
如果我们用A来表示一个正方形的主对角线上的所有整数之和，用B来表示副角线上的所有整数之和，那么这个**正方形的美就是A-B**。
注意：正方形的主对角线是从左上角到右下角的对角线。
**【输入】**
第一行一个正整数N（2≤N≤400），矩阵的大小。
以下N行每个包含[-1000,1000]范围内的N个整数，矩阵的元素。
**【输出】**
一行，一个整数，矩阵中找到的最美的正方形，即A-B最大
###**样例输入**
**【输入样例1】**
2
1 -2
4 5
**【输入样例2】**
3
1 2 3
4 5 6
7 8 9
**【输入样例3】**
3
-3 4 5
7 9 -2
1 0 -6
###**样例输出**
**【输出样例1】**
4
**【输出样例2】**
0
**【输出样例3】**
5
***
**【纯暴力枚举】**
不管如何，一定要学会纯暴力写法，简单粗暴，拿分爽。
**【参考程序及解释】**
```
#include<bits/stdc++.h>
using namespace std;
long long n,zx,zy,yx,yy,sa,sb,mx;
int a[405][405];

int main()
{
	cin>>n;
	for(int i = 1; i <= n; i++)  
		for(int j = 1; j <= n; j++)  
			cin>>a[i][j];
	mx = -2e9;
	for(int i = 1; i <= n ;i++) //枚举行
		for(int j = 1; j <= n; j++) //枚举列  枚举的是正方形左上角的顶点坐标
			for(int k = 1; k <= min(n-i+1,n-j+1); k++){ //枚举边长 
				zx = i; //主对角线的行 
				zy = j; //主对角线的列 
				yx = i; //副对角线的行 
				yy = j+k-1; //副对角线的列 
				sa = 0;  //主对角线求和 
				sb = 0;  //副对角线求和 
				for(int z = 1; z <= k; z++){ //计算对角线的和 
					sa += a[zx][zy];
					sb += a[yx][yy];
					zx++,zy++,yx++,yy--; 
				}
				mx = max(mx,sa-sb);
			}
	cout<<mx<<endl;
	return 0;
 } 
```
暴力搜索只要能写出，就能拿分数。数据规模不可能都是大数据，预计30~50，有些数据弱的能拿更多分数。
**某同学代码**
```
#include<bits/stdc++.h>
using namespace std;

int a[405][405],b[405][405];
long long n,l,m,s,t,mx,x,y;
int main()
{
	//freopen("matrix.in","r",stdin);
	//freopen("matrix.out","w",stdout);
	cin>>n;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++){
			cin>>t;
			a[i][j] = t + a[i-1][j-1];
			b[i][j] = t + b[i-1][j+1];
		}	
	mx = -2e9;
	for(int i = 1; i <= n; i++)
		for(int j = i; j <= n; j++)
			for(int k = i; k <= n; k++){
				x=a[j][k]-a[j-i][k-i];
				y=b[j][k-i+1]-b[j-i][k+i];
				s=x-y;
				mx=max(mx,s);
			}
	cout<<mx<<endl;
	return 0;
}
```
把文件输入输出注释掉，**最后别忘记去掉注释！**
###**数据生成程序**
一些复杂的题目，有时候经常会遗漏一些情况，所以对拍是个不错的方法，让程序随机生成数据来测试。
但是有些题目数据生成并不好写，所以自己要会去判断该不该用对拍，自己时间够不够的问题。一些数据规则简单的，直接用随机函数生成即可。以上题为例，我们可以设计这样一个数据生成器程序：
```
#include<bits/stdc++.h>
using namespace std;
const int nn = 4, maxn = 10; //定义常量方便修改数据范围 
int n;

int main()
{
	srand(time(NULL));
	n = rand()%(nn-1) + 2; //根据题意，生成2~nn 
	cout<<n<<endl;  //对应输入的第一行 
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++)
			//cout<< rand(2*maxn+1)-maxn<<" "; //随机数区间[-maxn,maxn] 
			cout<<rand()%maxn<<" "; //这题只测正数就可以了 
		cout<<endl;
	}
	return 0;
 } 
```
这题的数据生成器，其实蛮简单的，主要题目要求并不复杂。
**【windows批处理对拍脚本写法--注释为了理解,实际不用写的】**
```
@echo off
:loop                  //:loop 理解成标记
   rand.exe > matrix.in  //数据生成器生成的数据放到matrix.in文件，这里输入文件根据题目要求来，此题中是matrix.in。注意>表示输出到哪里，反之<表示从哪里读取
   baoli.exe < matrix.in >std.out  //这条语句的意思是暴力程序从matrix.in读取数据，再把结果输出到std.out文件中
   echo 开始 %time% //echo等价于pascal中的输出语句，%time%是系统变量，获取当前时间，可以用于是否超时
   matrix.exe < matrix.in > matrix.out //同上面说明
   echo 结束 %time% //同上面说明
 
   fc std.out matrix.out  //fc是windwos自带的文件比较命令
if errorlevel 1 pause  //errorlevel 是fc的返回值，如果返回值是1，则表示答案不同，pause命令是暂停执行命令，让你有时间去看测试的数据和结果
goto loop  //goto命令 表示再跳转到loop标记
```
###**注意**
批处理文件构建方式：新建一个文本文件，敲入下面的批处理命令，然后重命名为：duipai.bat。其中主文件名随意，扩展名必须是bat。
**【干净版】**
```
@echo off
:loop
   rand.exe > matrix.in
   baoli.exe < matrix.in >std.out
   echo 开始 %time%
   matrix.exe < matrix.in > matrix.out
   echo 结束 %time%
 
   fc std.out matrix.out
if errorlevel 1 pause
goto loop
```
**如果比赛剩余时间有多余，纯暴力程序也可以作为备胎，自己想的其他算法错误率高，优先选择纯暴力程序作为提交的程序**
###**对拍**
**1.数据规模，n=4,矩阵元素范围0~10**
![](/api/file/getImage?fileId=61615b83d170a10014000077)
我们发现当第6次的时候，出现了错误，这时候可以根据生成的数据去分析错误原因了。
**2.数据规模，n=10,矩阵元素范围0~10**
![](/api/file/getImage?fileId=61615b83d170a10014000075)
还是用老的程序在对拍，发现规模增大后，出错几率增加了。现在修改数据规模只是为了说明，这个算法问题很大。
**3.数据规模，n=100,矩阵元素范围0~10**
![](/api/file/getImage?fileId=61615b83d170a10014000078)
错误率大大提升。当数据规模继续增大的时候，这个算法的得分率极低。
到此验证出算法有BUG，并不是样例正确了就可以高枕无忧了。
对拍建议数据规模从小到大去生成，这样便于分析。
##**最后还是要强调，没有一定的熟练度，没有富裕的时间，不建议对拍。**

Merlin's Blog

Navigation

Recent Posts

Friend Links