竞赛编程中的调试技巧——对拍

《竞赛编程中的调试技巧——对拍》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、竞赛编程中的调试技巧——对拍在OI竞赛中，你只有一次提交机会，也就是说，你第一次交上去的程序就要是正确的。而很多比赛中，想出了正解而手抽打错的数不胜数。于是乎，对于一个程序，我们可以进行静态查错、分步调试等调试方式。除此之外，我们还可以写对拍来判断程序是否正确并且获得错误数据。所谓对拍，是将你的程序跑出的答案与正确程序进行比较。具体方法是先写一个程序make来生成数据，再使用一个一定正确，但是不限制时间、空间复杂度的程序（暴力一般是可以保证正确性的）生成正确答案，然后再和你的程序运行出来的答案进行比较。若你的程序有各种BUG，这个一般都可以产生错误数据供调试需要。在windows下，

2、对拍一般使用批处理(.bat)来写。（新建文本文档，改名）以下是模板：:1//一个标记而已make1//生成数据check1//生成正确答案a//生成你的答案fca.outa.ans//比较你的答案与正确答案if%errorlevel%equ0goto1//若结果相同，跳到1pause//最后停住，供查看错误答案。a是文件名+输入输出文件名（这个一般是相同的）。写完后直接双击运行即可。若要人工停，可以直接掉（可能会死掉……），亦可ctrl+C中断。在linux下，一般都是用的bash写的，这种语言比较简洁，适合写这种小东西。首先，bash文件的后缀名一般是”.sh”，直接新建文件改名

3、即可。以下是模板：letcnt=0;//计数器清零while[1];do//死循环letcnt=${cnt}+1;//计数器+1./make1//生成数据./check1//生成正确答案./a//生成你的答案diffa.outa.ans//比较你的答案与正确答案if[$?-eq0];then//判断结果是否相同echo${cnt}AC;//若结果相同，则打印AC到屏幕elsebreak;//若结果不同，终止循环fidone注意：make在linux中有内置命令，不建议作为对拍的文件名使用。在写好这个东西并保存后，直接在终端中进入当前文件夹并调用命令”bashcomp.sh”即可。（c

4、omp.sh为文件名）它会在终端中显示你已经通过了多少组数据，并且出错后会自动中断。当你不想拍时，直接按ctrl+C即可中断（当然，也可以直接把终端掉）。eg：给定一个序列，你每次可以合并相邻两个元素，新的元素为这两个元素的和。你需要使得若干次合并之后的序列非降，求最小合并次数。输入第一行一个数n，表示序列长度。接下来一行n个正整数，表示这个序列。输出一行一个数，表示最小合并次数。eg：input：582731output：3n≤1500，序列元素大小不超过1000。很明显，正解需要一个低于O(n^3)的算法（这个可以用来写O(n^3)暴力……）但是，这个算法可能会打错。于是乎：数据

5、生成程序：make1.cpp:#include#include#includeintn;intmain(){freopen("a.in","w",stdout);srand(time(0));printf("%d",n=rand()%105+495);for(;n;n--)printf("%d",rand()%1000+1);}一定正确的程序：check1.cpp:#include#includeintf[1505][1505],a[1505],i,j,k,n,ans=~0U>>1;voiddown

6、(int&a,intb){if(a>b)a=b;}intmain(){freopen("a.in","r",stdin);freopen("a.ans","w",stdout);scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]),a[i]+=a[i-1];memset(f,100,sizeof(f));f[0][0]=0;for(i=1;i<=n;i++)for(j=i;j;j--)for(k=j-1;k>=0;k--)if(a[i]-a[j-1]>=a[j-1]-a[k-1])down(f[i][j],f[j-1][k]+i-j);f

7、or(i=n;i;i--)down(ans,f[n][i]);printf("%d",ans);return0;}你的程序：略。a:这个你自己写吧。。。要拍一个错误程序才有意思嘛。。comp:直接参考上面的模板……通过这种方式，我们就可以发现程序是否是正确的，若程序不正确，还可以获得一组你程序出错的数据，接下来的工作就是调过这组数据了。