合肥信息学竞赛常见问题总结(二)
2014年合肥信息学竞赛的初赛已经结束了,但是考生们并不能松懈,信息学复赛即将在11月8日进行。大家已经经历了初赛,对信息学竞赛的一些考场规则已经有所了解,也一定在初赛的时候遇到了备考时没出现的新状况,下文将继续之前过来人对信息学竞赛常见问题的总结,希望可以帮助考生们更加了解信息学竞赛。
【问题:写出来的程序总是出错,怎么办?】
这是我去年犯的一个错误。就此给大家几点忠告:
1、不要写自己没有把握的算法。还是以我的同学举例,SPFA这个算法他不久前才学的,根本就没有学精,看到题以后也不想就开始写SPFA,然后各种调试调到比赛结束,交了一个连样例都时间过的程序上去了。其实他想过写一个搜索,但是他担心那样拿不到多少分,就放弃搜索。一个不熟悉的算法,很多问题是你还没有发现到的,因为你不常写。所以现场出了问题是很麻烦的。
2、调试。第一种调试是编译器自带的监视变量,这里我就不说了。第一种调试一般会伴随着单步运行,看看程序卡在哪里什么的。第一种有个缺点,有些数据你监视后会发现监视窗口的值和变量实际值一点也不搭边,会出现各种奇怪的值比如我的fpc2.4.0……。
第二种调试是调试输出,比如你发现答案不对,怀疑是某个在循环中值会发生改变的变量的问题,那你就在循环中加一个输出语句,用一个相对简单的测试数据,看看输出的该变量值和你人工模拟的值对不对。多加几个调试输出,可以清楚的发现问题发生在哪里。不过,等要交程序的时候一定要把调试输出等和程序无关的语句删掉或者注释掉,接着运行,看看答案对不对,然后保存(很重要),把源程序移动到题目文件夹下。
3、小问题解决。看一下你的程序中,变量置零了吗?变量置零语句的位置对不对?DFS的循环变量应该用局部变量,而你是不是用的全局变量?是不是有的极限情况没想到?是不是当达成某一个条件时就不用使计数变量+1或者-1了?是不是你的某个优化取余数mod错了?……等等,这些小问题最好的避免方法就是比赛前多做题。
4、样例是会骗人的。我会告诉你某同学的3个程序样例都过了但是都爆0了吗!样例有时候也是会骗人的,一定要自己多出几组数据测试。
【问题:经常听他们说对拍,对拍是什么?】
对拍是一种对照调试程序,用于比较2个程序对于相同测试数据的结果是否相同。比如你写了个高效的算法,但是不知道对不对;你又写了个效率很低但是不会出错的算法,你就可以使用对拍比较,看看2者答案相同与否。对拍可以检验出程序的正确性,但是一定要保证对拍的2个程序中有一个是绝对正确程序。
下面说说对拍怎么用。对拍是用批处理命令(.bat)来完成的,需要你在任意地方建立一个文件夹,文件夹下面要有这几个个东西:
1、你的对拍.bat命令。
2、数据生成器。用你的编译器写一个可以生成一组格式正确的测试数据的程序,编译成exe文件(生成的数据要保存在一个文件中,如xxx.in你的2个题目程序就用xxx.in作为输入源)。
3、你的2个程序,要用文件输入输出。
4、xxx.in作为被调试的2个程序的输入文件(事先需要自己手动建立一个,否则报错)。
5、算法1.out和算法2.out2个程序的输出文件(也要自己手动建立否则对拍会报错)。
接下来,写一个相对简单的对拍批处理命令,把它写进记事本里,然后保存把文件后缀改成.bat就可以。
off:loop//定义一个可被goto的标签loop数据生成器.exe//先运行数据生成器生成数据,否则xxx.in为空
算法1.exe
算法2.exe//你的2个程序,顺序不重要。运行后自动读取xxx.in中的测试数据。
fc算法1.out算法2.out//要比对的2个输出文件。
ifnoterrorlevel1gotoloop
pause
gotoloop
本对拍程序是不断循环执行以上语句,直到二者答案不相符就停止运行。这时选手可以查看xxx.in内的数据,并对此作出修改。其实就是一个自动比对答案的东西。