对拍程序写法

##**前方预警**
**只有有实力和编程非常熟练的学生才可以考虑用这个方法，熟练度一般的，不建议使用，因为你没有多余的时间写这个。**
###**原理**
利用windows的输出输入重定向功能(即改变输入输出的设备)，结合windows的fc(文件比较命令)，结合数据生成器，对程序进行对拍，一脸懵逼的看下图。
![](http://magicoj.imwork.net/api/file/getImage?fileId=59fbdba31d41c80752000006)
也就是说，你还要额外的多写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
***
**【纯暴力枚举】**
不管如何，一定要学会纯暴力写法，简单粗暴，拿分爽。
**【参考程序及解释】**
```
var
 a:array[1..400,1..400] of longint;
 i,j,k,z,zx,zy,yx,yy,n,sa,sb,max:longint;

function min(x,y:longint):longint;
begin
 if x<y then exit(x)
        else exit(y);
end;

begin
 readln(n);
 for i:=1 to n do
  for j:=1 to n do
   read(a[i,j]);
 max:=-maxlongint;
 for i:=1 to n do    //枚举行
  for j:=1 to n do   //枚举列  确定正方形左上角坐标
   for k:=1 to min(n-i+1,n-j+1) do //枚举边长，边长最大矩形的短边
     begin
      zx:=i;      //主对角线行
      zy:=j;      //主对角线列
      yx:=i;      //副对角线行
      yy:=j+k-1;  //副对角线列
      sa:=0;      //主对角线求和
      sb:=0;      //副对角线求和
      for z:=1 to k do //计算对角线的和
       begin
        sa:=sa+a[zx,zy];
        sb:=sb+a[yx,yy];
        inc(zx);         //为了直观形象，单独抽出来处理
        inc(zy);
        inc(yx);
        dec(yy);
       end;
       if sa-sb>max then max:=sa-sb; //打擂台
     end;

writeln(max);
end.
```
暴力搜索只要能写出，就能拿分数。数据规模不可能都是大数据，预计30~50，有些数据弱的能拿更多分数。
**某同学代码**
```
var
 a,b:array[0..401,0..401]of longint;
 i,j,k,l,m,n,s,t,max,x,y:longint;
begin
 {assign(input,'matrix.in');
 assign(output,'matrix.out');
 reset(input);
 rewrite(output);}
 readln(n);
 for i:=1 to n do
  for j:=1 to n do
   begin
    read(t);
    a[i,j]:=t+a[i-1,j-1];
    b[i,j]:=t+b[i-1,j+1];
   end;
 max:=-maxlongint;
 for i:=1 to n do
  for j:=i to n do
   for k:=i to n do
    begin
     x:=a[j,k]-a[j-i,k-i];
     y:=b[j,k-i+1]-b[j-i,k+i];
     s:=x-y;
     if s>max then max:=s;
    end;
 writeln(max);
 {close(input);
 close(output);}
end.
```
把文件输入输出注释掉，**最后别忘记去掉注释！**
###**数据生成程序**
一些复杂的题目，有时候经常会遗漏一些情况，所以对拍是个不错的方法，让程序随机生成数据来测试。
但是有些题目数据生成并不好写，所以自己要会去判断该不该用对拍，自己时间够不够的问题。一些数据规则简单的，直接用随机函数生成即可。以上题为例，我们可以设计这样一个数据生成器程序：
```
const
  nn=4;             //用常量，方便修改规模
  maxn=10;          //数据生成范围，一般也没必要开大，只有检查是否会爆，才把数据范围开大
var
 i,j,n:longint;
begin
 randomize;
 n:=random(nn-1)+2; //根据题目要求n生成2~nn,这里不随机生成，用固定值也可以的
 writeln(n);  //根据题目要求，第1行是n
 for i:=1 to n do
  begin
   for j:=1 to n do
    //write(random(maxn*2+1)-maxn,' '); //这里生成的是[-maxn,maxn]
    write(random(maxn),' '); //其实只检测非负整数就够了

writeln;
  end;
end.
```
这题的数据生成器，其实蛮简单的，主要题目要求并不复杂。
**【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标记
```
**【干净版】**
```
@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**
![](http://magicoj.imwork.net/api/file/getImage?fileId=59fbdba31d41c80752000005)
我们发现当第6次的时候，出现了错误，这时候可以根据生成的数据去分析错误原因了。
**2.数据规模，n=10,矩阵元素范围0~10**
![](http://magicoj.imwork.net/api/file/getImage?fileId=59fbdba31d41c80752000008)
还是用老的程序在对拍，发现规模增大后，出错几率增加了。现在修改数据规模只是为了说明，这个算法问题很大。
**3.数据规模，n=100,矩阵元素范围0~10**
![](http://magicoj.imwork.net/api/file/getImage?fileId=59fbdba31d41c80752000007)
错误率大大提升。当数据规模继续增大的时候，这个算法的得分率极低。
到此验证出算法有BUG，并不是样例正确了就可以高枕无忧了。
对拍建议数据规模从小到大去生成，这样便于分析。
##**最后还是要强调，没有一定的熟练度，没有富裕的时间，不建议对拍。**

Merlin's Blog

Navigation

Recent Posts

Friend Links