程序调试教程（3）——WA 和 TLE

wzf2000
2019年9月27日

程序调试教程（3）——WA 和 TLE

WA 和 TLE

看到 Wrong Answer，先不要 WA 地哭出来（雾）。

毕竟你要知道，这代表着你的程序没有超时，也就是有不小的可能性算法本身正确只是实现出现了问题。

对于 WA 这种错误，最让人抓狂的莫过于调试了许久，最终发现自己的程序完美地实现了算法的目标，只是算法就得不出正确的结果。也就是对着一个错的程序浪费青春。

所以首先请确认你的算法的正确性，如果是较复杂的算法，可以利用一些简单的数据进行验证（不一定要依赖样例），顺便还能借这些数据看看程序的算法实现有没有什么问题。

而 TLE 实际上跟 WA 很相似，很多相同的错误在不同的情况会导致这两种不同的错误。

在确认算法正确性（包括答案正确与复杂度正确）后，这两种错误的调试也基本相同，所以我们将其放在一起。

接下来我们来看一下技巧方法。

一、对代码分段

一般我们写的程序涉及的算法都不是一步到位的，总是可以分为若干步，比如：

1. 在一段分解质因数的程序中，我们会先用线性筛预处理素数，然后再对输入的素数进行分解。这时，我们可以先用输出检查前 $100$ 个质数，看看是否正确。（阶段性分段）
2. 在一道维护链表的题中，我们可以在每次插入删除后，都将整条链表输出，观察是否合理，甚至可以通过是否死循环确定是否成环。（循环过程分段）
3. 对于一个需要深度优先搜索的题目，我们可以在每一层函数中，都将相关数据输出，判断层数相关的各变量是否正确变化。（递归过程分段）
4. 除此之外，还可以在一些 if 语句中输出特殊符号，确认是否进入正确的分支。

二、选择输出的变量

选择的变量一般有以下特性：

1. 经过这段（上面分段后）代码后，发生或者可能发生了变化。
2. 对于后面的代码有影响，或者说在后面会用到。
3. 有时需要具有直观、明确的含义，方便人工模拟算法的计算。

三、手动计算“正确答案“并与输出调试对比

这一步注意计算是以你心中的算法为准，因为你不能保证自己的算法就一定能算出正确结果。为了避免出现调试错误算法的情况，一定要先用你的算法计算来确认算法正确性。（一组数据正确不一定能保证全部正确）

四、构造特殊的数据来 Hack 自己的算法和程序

很多算法对于普通数据和特殊数据（大概就是某些数据取到了上下界，或者极端情况）的处理情况总有些许不同，所以可以首先考虑构造这种特殊数据。

对于一个数而言可能是指取到了 $1$ 和 $n$，而对一棵树而言可能是构成了一条链（每个点的度数 $\le 2$）、菊花图（所有除根节点以外的点连在了根节点上）、随机树或者三者的组合（部分节点满足其中某个性质），对于一个链表来说可能就是加到开头、结尾，或者中间删除到了空链表。

五、以一道题为例讲解

我们以 Codeforces150E 此题（在网站上就有对应题解）为例。

可能这道题对于大多数编程学习者来说有点难，但是我们重在学习其中的调试方法，所以对于算法不需要有多深了解。

这道题大致题意：

• 有一颗 $n$ 个节点的树，它应有 $n-1$ 条边连接。
• 每条边有一个权值 $val[i]$。
• 对于树上任意两个不同点，都有唯一一条不重复（每条边只走一次）路径，这条路径上的长度即为路径经过的边的数量，比如设点 $a$ 到点 $b$ 的路径长度为 $L(a,b)$。
• 这 $L(a,b)$ 条边上的权值构成了长度为 $L(a,b)$ 的数组，这个数组应该有一个中位数（如果是偶数条边，选取较大的那个数）。
• 我们现在希望求得所有长度在 $[L,R]$ 区间的路径中中位数最大的路径，如果有多个，任意输出一个都可以。
• 数据范围略去。

我们给出的题解是：

• 先通过二分法确定一个基准的 $val_0$ 值，然后对于 $val[i] > val_0$ 的边给一个新的权值为 $1$，其它边给一个新的权值为 $-1$。
• 那么如果可以找到一条路径使得其新的权值和 $\ge 0$ 且长度在 $[L,R]$ 之间，那么这条路径的中位数一定大于等于 $val_0$，所以最大的中位数一定也大于等于 $val_0$。
• 然后我们可以用树分治的算法，根据树的重心将其分为若干个子树，递归进行寻找是否存在路径。（这里不需要知道什么是树分治，为什么这样可以覆盖所有路径）
• 然后每一层，我们通过不断从小到大地加入子树，用双指针扫描计算经过重心的最大路径权值并更新到固定长度的重心的路径最大值，获取是否存在这样的路径满足条件。

这道题的算法可以说十分复杂。

但是我们可以通过合理的分块然后输出调试让你明白自己 Wrong Answer 是为什么。

首先树分治需要预处理一些子树大小的数组，我们可以在处理完后输出每个点的子树大小，然后判断正误，这也就是阶段性分块。

然后我们会进行二分法，我们可以在每个二分的判断输出它是向小变还是向大变，然后根据结果判断是否正确，也就是循环过程分块以及 if 语句的选择。

而在树分治的递归过程中，我们可以每层输出重心，保证重心的正确性，也就是递归过程分块。

我们上面三种分块中的输出，选择的子树大小数组、判断函数、以及重心标号，都是较为满足之前所说的要求的重要变量。

这个过程中我们也要根据算法自己计算样例每一步的各个变量的变化。

在此之后，我们还可以自主设计数据，比如对于特殊树的构造，对于边的权值的边界情况赋值（全部取下限或者上限）。

当然在很多题中，光是依靠样例和自己手动造的数据，还是找不出错误，或者说，这样自己寻找错误的效率太低，这时候我们可能就需要一种对拍的方法。

六、对拍“神器”

对拍，一般是针对 Wrong Answer 而言，但有时也可以针对 Time Limit Exceeded。

首先，我们一般需要一个保证正确的程序，也就是避免对于一组新的数据，通过人脑来得出答案（当然一般是较为朴素、较为暴力的做法）。

其次，我们需要一个可以自己生成合法数据的程序，比如生成一棵树，生成一个随机数组这些生成方法的组合，这样才能保证构造数据的快速性。

最后，我们还需要一个批处理文件，它需要完成的功能大致是：

1. 运行生成数据程序获得输入数据；
2. 运行暴力程序获得正确输出；
3. 运行你正在调试的程序获得你的输出；
4. 对比两个输出，确认答案正误；
5. 如果错误，留下数据来进行上面的调试；
6. 否则，重复进行上述过程。

当然对于一个 TLE 的程序，我们可以只构造数据和运行在调试的程序，而不运行暴力程序，然后通过命令行的反应时间，判断是否超时，然后保留超时数据进行相似的操作。

这样的批处理文件一般不同系统差异较大，在下面收集了一些可行的写法。

:loop
makedata.exe
K.exe
Kture.exe
fc a.out b.out
if %errorlevel%==0 goto loop
pause 

while true; do
./make>tmp.in #出数据
./tmp<tmp.in>tmp.out #被测程序
./tmp2<tmp.in>tmp2.out #正确（暴力）程序
if diff tmp.out tmp2.out; then #比较两个输出文件
printf AC #结果相同显示AC
else
echo WA #结果不同显示WA，并退出
#cat tmp.out tmp2.out
exit 0
fi #if的结束标志,与C语言相反，0为真
done # while的结束标志

#BY NICK WONG 2014-08-29
#在终端下，进入当前目录，输入"sh ./nick.sh",（其中nick.sh为当前shell脚本名） '#'表示单行注释
#diff在两文件相同时返回空串

#include <iostream>
#include<cstdlib>
using namespace std;
int main() {
    for(int i=1;i<=100;i++){
        system("./data");
        system("./test1");
        system("./test2");
        if(system("diff test1.out test2.out")){
            cout<<"Wrong on test#:"<<i<<endl;break;
        }
        else cout<<"Test#"<<i<<": No problem!"<<endl;
    }

    return 0;
}

（对于 C++ 程序就是编译运行）

最后顺便说一下，实际上一般的 RE 跟上述错误的调试方法也基本相同，但因为其可能情况特别复杂，所以这里不特别列出来。（之后可能会写点关于特殊 RE 的调试技巧）

 教程 调试