竞赛编程中的调试技巧

• 作 者: 谢秋锋
• 出 处: 信息教研周刊
• 发表日期: 2013年1期

　　在OI竞赛中，你只有一次提交机会，也就是说，你第一次交上去的程序就要是正确的。而在比赛时，很难保证在想出正解的前提下，程序一定都能写对。于是乎，对于写出来的程序，我们需要通过各种方法去查错。常用的有静态查错、分步调试等调试方式。这里我想给大家介绍一个非常高效的查错的方法——对拍。
　　所谓对拍，是将你写的待检查程序和对拍程序，对相同的输入数据，进行运行，然后利用批处理来比对输出结果，如果对多组输入数据，输出都一致，则可以初步下结论，待检查的程序是正确的，如果有输出不一致的现象，可以对错误输出的这个数据进行进一步调试来发现待检查程序究竟哪里出错了。其中对拍程序是你自己编写的，针对原题不考虑时间和空间复杂度的，我们常称暴力的正确程序。输入数据是你写的一个数据生成程序生成的数据。这个数据生成程序我们常取名叫make1。
　　要让这种对拍得以执行，还需要写一个执行对拍的程序，该程序在windows下和linux下的写法有所不同，我们分别来看
　　在windows下，对拍执行代码一般使用批处理（.bat）来写。（操作：新建文本文档，改名，注意扩展名是.bat）
　　以下是模板：
　　：1 //一个标记而已
　　make1 //生成数据
　　check1 //生成正确答案
　　a //生成你的答案
　　fc a.out a.ans //比较你的答案与正确答案
　　if %errorlevel% equ 0 goto 1 //若结果相同，跳到1
　　pause //最后停住，供查看错误答案。
　　a是文件名+输入输出文件名（这个一般是相同的）。
　　写完后直接双击运行即可。
　　若要人工停，可以直接掉，亦可ctrl+C中断。
　　在linux下，一般都是用的bash写的，这种语言比较简洁，适合写这种小东西。
　　首先，bash文件的后缀名一般是”.sh”，直接新建文件改名即可。
　　以下是模板：
　　let cnt=0； //计数器清零
　　while [ 1 ]； do //死循环
　　let cnt=${cnt}+1； //计数器+1
　　./make1 //生成数据
　　./check1 //生成正确答案
　　./a //生成你的答案
　　diff a.out a.ans //比较你的答案与正确答案
　　if [ $？ -eq 0 ]； then //判断结果是否相同
　　echo ${cnt} AC； //若结果相同，则打印AC到屏幕
　　else break； //若结果不同，终止循环
　　fi
　　done
　　注意：make在linux中有内置命令，不建议作为对拍的文件名使用。
　　在写好这个代码并保存后，直接在终端中进入当前文件夹并调用命令”bash comp.sh”即可。（comp.sh为文件名）它会在终端中显示你已经通过了多少组数据，并且出错后会自动中断。当你不想拍时，直接按ctrl+C即可中断（当然，也可以直接把終端掉）。
　　综上所述，要进行对拍需要准备以下几个内容：
　　一个你写的待检测的程序
　　例如：a.cpp
　　另外编写一个对拍程序
　　例如：check1.cpp
　　编写一个数据生成程序
　　例如：make1.cpp
　　针对不同的系统复制上面能执行对拍的代码
　　运行此代码，就可以对拍查错了
　　下面我们看一个具体例子：
　　【问题】给定一个序列，你每次可以合并相邻两个元素，新的元素为这两个元素的和。你需要使得若干次合并之后的序列非降，求最小合并次数。
　　输入第一行一个数 n ，表示序列长度。
　　接下来一行 n 个正整数，表示这个序列。
　　输出一行一个数，表示最小合并次数。
　　eg：
　　input：
　　5
　　8 2 7 3 1
　　output：
　　3
　　n ≤ 1500 ，序列元素大小不超过1000。
　　具体操作：
　　分析，根据此题数据规模，正解需要写一个低于O（n^3）的算法，但是，这个算法可能会打错。所以可以考虑对拍查错。
　　数据生成程序：
　　make1.cpp：
　　#include
　　#include
　　#include
　　int n；
　　int main（）
　　{
　　freopen（"a.in"，"w"，stdout）；
　　srand（time（0））；
　　printf（"%d＼n"，n=rand（）%105+495）；
　　for （；n；n--）printf（"%d "，rand（）%1000+1）；
　　}
　　对拍程序（很容易想到的O（n^3）算法的程序）：
　　check1.cpp：
　　#include
　　#include
　　int f[1505][1505]，a[1505]，i，j，k，n，ans=～0U>>1；
　　void down（int&a，int b）{if（a>b）a=b；}
　　int main（）
　　{
　　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）；
　　for （i=n；i；i--）down（ans，f[n][i]）；
　　printf（"%d"，ans）；
　　return 0；
　　}
　　你的程序：略。
　　对拍的执行代码可以复制上面提供的模板。剩下的就只需运行对拍的执行代码查错就行了。