在 OI 赛制的比赛中,高效、恰当地调试程序,是拿到稳定分数的必要条件。只有一次提交机会,意味着本地需要进行大量调试工作,以保证程序在各种各样的输入下都能正常运行。
一般来说,选手会手造特殊数据、对拍随机数据,对程序进行调试。
应在开始编码前,就考虑算法在各种极端情况下的表现。
常见的特殊情况有:
此外,根据问题的不同,还有不同的特殊情况。
序列中,考虑单调递增、单调递减、常值序列。
若有区间询问,考虑询问长度特别小(例如全为单点)、长度特别大(例如全为整个区间)。
序列的情况可以搬到树上,此外,还可以考虑:
图上问题同样可以照搬树上问题的情况,还可以考虑:
在完成代码后,可以手造特殊数据,手算答案来补充小样例,若程序出错可以使用小样例进行调试。
而通过手造的样例后,可以用代码生成特殊的大样例来测试程序的复杂度的正确性。
随机数据对拍是一种强有力的调试手段。
在进行对拍前,需要准备:
一般来说,OI 赛制的题目设有小数据范围的部分分,选手可以先打出部分分的代码,再思考正解。 这样一来,暴力代码可以用于对拍,而没有想出正解也能拿到暴力分。 在此过程中,请注意不要随意地对暴力代码进行修改,而是新开文件写正解,保证若最后失败,也能直接交上暴力程序拿分。
若暴力程序编写难度较大,对拍得不偿失,可以考虑放弃对拍。
在对拍中,生成有强度的随机数据是非常必要的。
生成随机数,常用的有 rand()
和 mt19937
,后者是 c++11 中强度较高的随机数生成方法。
如果需要使用后者,需要使用 c++11 或以上版本,例如 Dev C++ 在编译命令中加入 -std=c++11
才能使用。
为了保证数据随机,需要设置随机数种子。 以下是一个生成随机序列的例子:
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(time(0));//use time as random seed
const int maxn = 1e4 + 100;
int n,a[maxn];
inline int getint(int x)
{
return (rnd() % x) + 1;//get an integer in [1,x]
}
int main()
{
freopen("file.in","w",stdout);
n = getint(10000);//generate n in [1,10000]
for(int i = 1; i <= n; ++i) a[i] = getint(1000000);
//output
printf("%d\n", n);
for(int i = 1; i <= n; ++i) printf("%d ", a[i]);
putchar('\n');
return 0;
}
暴力程序没有什么额外要求,按照 OI 赛制要求的 FILEIO 即可。
freopen("file.in","r",stdin);
freopen("std.out","w",stdout);
...
期望程序输入可以与暴力共用,但输出必须不同。
freopen("file.in","r",stdin);
freopen("ans.out","w",stdout);
对拍器是对拍的中枢,功能流程如下:
对拍有两种常用的实现方式:批处理实现与 c++实现。
核心的对比答案都使用了系统自带的 fc
函数,因此两种实现差别不大。
批处理版本:
@echo off
:loop
datamaker
std
myprogram
fc myprogram.out std.out
if not errorlevel 1 goto loop
pause
go to loop
c++ 版本:
#include <iostream>
#include <windows.h>
using namespace std;
int main()
{
int T = 200;
while(T--)
{
system("generator.exe");
system("std.exe");
system("yourprogram.exe");
if(system("fc std.out ans.out")) system("pause");
}
return 0;
}
将程序编译为 exe 后,放在同一目录下,运行对拍器即可开始对拍了。
一般来说,从小数据开始对拍,用来找出程序潜在的漏洞并加以改进。
生成范围小的随机数据,方便出错时手动调试。而在小数据通过后,生成大数据来检验正确性。
需要注意,生成的数据范围需要在暴力程序可接受范围内。
因此对拍能检验的数据范围是有限的,而仅仅能检验在部分范围内的正确性。
当范围更大时,需要注意的几点是:
其中前两点可以用良好的编程习惯加以避免,而最后一点可以直接生成极限数据检验。
对拍的任务仅仅是检验算法的正确性,而一般情况下,中等数据下运行正确的算法,在极限数据下正确性不会受到太大影响。