程序设计竞赛中的调试技巧

代码能力是我们在程序设计竞赛中常常谈到的一种能力，是指选手把算法用代码准确地实现的能力。
2005 年，Comars 曾经给代码能力作过一个比较准确的定义：如果我 150150 行以内的题目，1Y（提交一次就正确通过，Y 是指 Yes）率非常高，并且保持稳定；而当代码长度超过 150150 行以后，1Y 率就开始急速下降了。如果我们画出一条代码行数与 1Y 率之间的关系的曲线，150150 行就是一个转折点。我们不妨认为，150150 行就是 Comars 当时的代码能力。一年以后，经过努力，Comars 把代码能力提高到了 250250 行，也就意味着他通常可以无错误地写出一份 250250 行的代码。
当然，想要把代码能力提高到 150150 行并非是一个简单的事情。在代码能力不够强的时候，就需要有足够的调试（debug）能力了。结合我的比赛经历和平时训练的经验，给大家分享一些程序设计竞赛题目 debug 的技巧。
在开始 debug 之前，要先在脑海中过一遍思路，必须保证自己有一个清晰的算法思路和一个正确的算法（至少自己要相信它是正确的）。一定要有清晰的思路，不然写出来的代码可能连自己都看不懂；而基于一个错误算法的 debug 是毫无意义的。当你确认了上面两件事情以后，才有必要开始 debug。

1. 顺着你的思路仔细阅读自己的代码两到三遍，注意是仔细，要一句一句地读。核对你的代码和你的思路是否一致，不要放过任何一个小细节。如果遇到拿不准的地方，立刻停下来仔细想想，直到想清楚以后再继续。在这个过程中，往往可以找到很多低级错误，尤其是对于代码能力不太好的同学，比如——变量打错、代码写错位置、变量赋值错误等等。静态阅读代码的效率是非常高的，因为往往读一份自己写出的代码的时间远小于写的时间——既然都已经花了那么多时间写出来了，何必还在乎这点时间多读几遍呢。
2. 如果经过上面的过程还没有找到程序中的错误，或者找到了一些问题但是程序的结果还是不对，这时我们就要通过运行程序来 debug。根据我以往参加竞赛的经验，经过上面的过程基本上可以解决一半以上的问题。如果一定要走到这一步，很可能已经给自己挖了一个巨大的坑。想要通过运行程序来 debug，第一步是需要拿到一组能使得程序出错的数据，拿到错误数据以后，debug 就成功了一半。在造错误数据时，一定要静下心来耐心出，不要指望一下就能造出错误数据。并且造出的数据尽量不要规模太小、太简单，数据越复杂，找到错误的概率会越高。对于 ACM/ICPC 这种团队比赛，必要的时候你可以让队友帮你造数据。例如某年 ACM/ICPC 沈阳赛区，我当时调试一道模拟题半个多小时还是错的，距离比赛结束还有 1010 分钟时，队友找到一组错误数据，然后我调了 55 分钟就找出了那个致命的 bug。在比赛进行到 295295 分钟（比赛一共 300300 分钟）的时候正确通过了这题（很关键的一题）。同年上海赛区，也是最后几分钟队友给出一组给力数据，在 299299 分钟绝杀一道 dp 题目。有了数据以后，剩下的调试应该很简单了。根据错误数据，输出一些重要的中间变量的值，然后观察是否和预期一样。这里也可以借助二分思想输出中间变量，快速定位到错误代码块。不过实践中，通常是根据经验，觉得哪块容易出错就重点输出哪一块的变量。无论是平时训练还是比赛中我都建议少用 IDE 断点调试功能和单步调试功能，通常比较浪费时间。
3. 对于某些特殊题目，小数据可以很容易写出一个时间效率低但确保正确的“暴力”程序。这时候，我们可以用暴力程序和出错程序对拍。对于造出的一些小数据，同时用自己的程序和暴力程序得出答案然后对比。这个小数据的范围是暴力程序能在短时间内得到正确结果的最大范围。因为暴力程序一般都很简单，没那么容易写错，所以你通常把暴力程序当成小数据的标准程序。如果连暴力都写错，建议多做练习，提高代码能力，确保短代码都能尽量做到零失误。
   经过上面的 debug 过程以后，如果你手造的复杂数据多达 1010 组以上还没有发现错误。你可以尝试下面的做法：
   重新思考一个新思路，或者尝试去发现原思路中的问题。
   先静下心来，先看看其他题，AC 一些其他题调整一下状态，然后回来重新 debug。
   如果你确定思路一定没问题，代码也一定没错，那通常是因为你读错题目了，重新回去读题。
   如果到这一步你的程序还是无法正确通过，并且你确保没读错题，只要有足够的自信，联系出题人，和他确认数据是否有问题。
   debug 过程中不要轻易请教别人，请教别人思路没问题，但是请教别人帮你 debug 不太好。除非你已经连续 debug 了一天还没有发现错误，再考虑去请教其他人。这里教大家一个 debug 技巧——断言（assert）。
   1
   assert(x >= 0);
   如果x >= 0不成立，则程序会因为运行错误而退出。比如写一个整数除法函数：
   1
   int division(int x, int y) {
   2
   assert(y != 0);
   3
   return x / y;
   4
   }
   如果y == 0程序就会异常退出，你一定是在程序的其他什么地方写错了。

再如，solve(x, y)如果应该等于solve(y, x)，我们可以assert(solve(x, y) == solve(y, x))，如果运行错误，那么必然solve写错了。在解决 Polya 计数题目的时候，可以assert(sum % |G| == 0)。除了用来调试以外，assert还可以用来验证数据是否规范，对出题人很方便，还可以用来验证 OJ 数据的准确性。

经验之谈
最后列出一些比赛和训练中特别容易犯的一些低级错误和治疗方法：

错误代码
1
int n;
2
int a[n];
治疗方法：初学者很容易写出这样的代码，当然老队员肯定写不出这种代码的。尽量避免这种写法，定义数组用常量，比题目约定的数据范围稍微大一点。比如数据范围是 1 \leq n \leq 100001≤n≤10000，则开一个 10000 + 1010000+10 的数组会比较稳妥，因为你也许后来心血来潮让下标从 11 开始计数。
1
const int maxn = 10000 + 10;
2
int a[maxn];
错误代码
1
for (int i = 0; i < n; i++) {
2
if (i = n) {
3
printf("%d\n", i);
4
}
5
else {
6
printf("%d “, i);
7
}
8
}
治疗方法：剁手。编译警告（warning）会提醒的，不要忽略甚至直接关闭编译警告。建议在做题的时候把编译选项-Wall打开：
1
g++ -Wall -o main main.cpp
错误代码
1
double a = 1 / 3 * 3;
2
double b = 1;
3
if (a == b) {
4
printf(“Yes”);
5
}
治疗方法：判断浮点数相等应该用极小值eps来辅助，一般eps取1e-8足够了，确保比题目约定的精度误差要求更小。
1
const double eps = 1e-8;
2
double a = 1 / 3 * 3;
3
double b = 1;
4
if (fabs(a - b) < eps) {
5
printf(“Yes”);
6
}
错误代码
1
const int inf = 0x7fffffff;
2
int dp[10];
3
int main() {
4
for (int i = 0; i < 10; ++i) {
5
dp[i] = inf;
6
}
7
for (int i = 1; i < 10; ++i) {
8
dp[i] = min(dp[i], dp[i] + dp[i - 1]);
9
}
10
return 0;
11
}
治疗方法：这里inf + inf会溢出，超出了int的范围。可以把inf的定义改成：const int inf = 0x3fffffff，就可以确保不会溢出了。顺便给大家推荐一个小技巧：
1
int dist[100];
2
memset(dist, 0x3f, sizeof(dist));
如上的代码可以让dist数组中的所有元素赋值为0x3f3f3f3f，并且两个初始值相加也不会溢出，常用于图论或动态规划中数组的初始化。
错误代码
1
// 1. 线段树 build
2
void build(int id, int l, int r) {
3
if (l == r) {
4
return;
5
}
6
int mid = (l + r) >> 1;
7
build(id << 1, l, mid);
8
build(id << 1 + 1, mid + 1, r);
9
}
10
// 2. 取 dp 答案
11
printf(”%d\n", dp[1 << n - 1]);
治疗方法：没有弄清楚操作符优先级。在优先级不确定的情况下，用小括号来明确指定优先级能够避免这类问题的发生。当然，最好还是要弄清这些符号之间优先级的关系。
1
// 1. 线段树 build
2
void build(int id, int l, int r) {
3
if (l == r) {
4
return;
5
}
6
int mid = (l + r) >> 1;
7
build(id << 1, l, mid);
8
build(id << 1 | 1, mid + 1, r);
9
}
10
// 2. 取 dp 答案
11
printf("%d\n", dp[(1 << n) - 1]);
错误代码
1
#define MAXN 1000 + 10
2
#define MULTIPLY(x, y) x * y
3
int a[MAXN * 4];
4
int main() {
5
int x = MULTIPLY(1 + 2, 3);
6
return 0;
7
}
治疗方法：尽量不要用宏定义，常量用const来定义。宏定义虽然很方便，但是用起来很容易出错，比如上面这段代码。如果你一定要用宏定义，先去了解宏定义常见的“坑”再用。
错误代码
1

#include <iostream>
2
 using namespace std;
3
 bool t, first;
4
​
5
 int main() {
6
     first = true;
7
     cin >> t;
8
     while (t--) {
9
         ...
10
     }
11
     return 0;
12
 }

治疗方法：写代码的时候不要太“随性”，这种情况的发生通常都是写程序时中途加了一个变量导致的，只要不太粗心就能避免。由于可能会发生这类错误，所以在本地造数据的时候，对于多组数据的题目要尽可能在一次测试中多造几组数据，以尽量避免此类问题。

在大多数平台和 ACM/ICPC 现场赛时，C++ 的 long long 用%lld输入；而对于一些搭建在 Windows 上的 OJ（如 Codeforces、HDOJ），要用%I64d读入。具体使用哪个占位符要多看 FAQ。

变量在访问前一定要初始化。好的习惯是在定义一个变量的时候就立刻初始化。一定注意，很多平台（包括计蒜客的题库）的编译器是不会在定义数组后将数组内元素全部初始化为 00 的，如果你遇到本地和线上结果不一致的情况，可以从这个方向来找问题。

避免访问非法内存。访问非法内存的事情经常发生，但是可以通过养成好习惯来避免。比如stack、queue、set访问之前必须先确认不为空；访问指针之前确保指针不是野指针；数组内存开得足够大，等等。