交卷之前你要检查什么

过样例不等于过题

到这一课，你会的算法已经够用了。真正让你丢分的往往不是不会做，而是交上去之后才发现：多组数据之间的状态没清空、答案该取模忘了取、数组开小了一格。这些错误有一个共同点——在题面给的样例上全都不会暴露。

样例通常是出题人挑出来的「正常」数据：规模小、情况普通。它能验的只有「你的代码能不能跑起来」，验不了边界、验不了退化、验不了多组之间的相互影响。

所以「提交前自检」不该靠感觉，要变成一份固定流程。这一课就把这个流程拆开，逐条量给你看它到底能挡住什么。

对拍器不是护身符

第 15 课教过对拍：写一个暴力解，造随机数据，两边跑，不一样就说明有一边错了。这是最有力的自检手段。

但它有一个致命前提——参考解必须真的独立于候选解。 如果你照着自己的思路再写一遍「参考解」，那两版会一起错，对拍全过，你得到一个假通过。

看一个具体的例子。题目求最大子段和，候选解写成了这样：

import random


def cand(a):
    """候选解：Kadane，但 best 从 0 起步。"""
    best = cur = 0
    for x in a:
        cur = max(0, cur + x)
        best = max(best, cur)
    return best


def ref_same_idea(a):
    """「参考解」——同一个错思路，只是行文不同。"""
    cur = 0
    ans = 0
    for x in a:
        cur += x
        if cur < 0:
            cur = 0
        if cur > ans:
            ans = cur
    return ans


def ref_brute(a):
    """独立暴力：枚举所有子段，一个不漏。"""
    best = None
    for i in range(len(a)):
        s = 0
        for j in range(i, len(a)):
            s += a[j]
            if best is None or s > best:
                best = s
    return best


random.seed(1)
TRIALS = 500
same_bad = 0
indep_bad = 0
for _ in range(TRIALS):
    n = random.randint(1, 8)
    a = [random.randint(-9, 9) for _ in range(n)]
    c = cand(a)
    if c != ref_same_idea(a):
        same_bad += 1
    if c != ref_brute(a):
        indep_bad += 1
print(f'   {TRIALS} 组随机数据（取值 -9..9，n 到 8）：')
print(f'      与「同一个思路的参考解」对拍，不一致的: {same_bad:>3} 组')
print(f'      与「独立暴力解」对拍，不一致的        : {indep_bad:>3} 组')

random.seed(1)
first = None
for _ in range(TRIALS):
    n = random.randint(1, 8)
    a = [random.randint(-9, 9) for _ in range(n)]
    if cand(a) != ref_brute(a):
        first = (a, cand(a), ref_brute(a))
        break
print(f'   独立暴力抓到的第一个反例：数据 {first[0]}  '
      f'候选解给 {first[1]}  暴力解给 {first[2]}')

   500 组随机数据（取值 -9..9，n 到 8）：
      与「同一个思路的参考解」对拍，不一致的:   0 组
      与「独立暴力解」对拍，不一致的        :  58 组
   独立暴力抓到的第一个反例：数据 [-7]  候选解给 0  暴力解给 -7

500 组数据，同一个思路的参考解一组都没抓到；换成独立暴力，抓到 58 组。

那个 bug 是 best 从 0 起步，所以面对全是负数的数据它会交回 0——而正确答案是那个最大的负数。ref_same_idea 和 cand 都犯了这个错，所以它们永远一致。

结论：参考解要尽量用「另一种办法」写。 求最值就用暴力枚举，计数就用组合公式或者小规模手推，图的问题就用矩阵小数据直接模拟。跟候选解思路不同的参考解才叫参考解，只是想换一种写法的，是对拍器里的装饰品。

生成器的范围要对

对拍器的第二个失效点更隐蔽：数据造得不对，等于没测。

上面那个 bug 只在「全部是负数」时才出现。很多人写生成器时会不自觉地绕开这种情况——比如为了让数据「好看一点」，加一句「至少有一个正数」：

def gen_narrow(n, rng):
    """只造「至少有一个正数」的数据——很多人的生成器就是这样写的。"""
    while True:
        a = [rng.randint(-9, 9) for _ in range(n)]
        if max(a) > 0:
            return a


def gen_full(n, rng):
    """允许全负。"""
    return [rng.randint(-9, 9) for _ in range(n)]


for name, gen in (('只造有正数的', gen_narrow), ('允许全负的', gen_full)):
    rng = random.Random(2)
    caught = 0
    for _ in range(300):
        n = rng.randint(1, 8)
        a = gen(n, rng)
        if cand(a) != ref_brute(a):
            caught += 1
    print(f'   {name:<12}：300 组里抓到 bug 的有 {caught:>3} 组')

   只造有正数的      ：300 组里抓到 bug 的有   0 组
   允许全负的       ：300 组里抓到 bug 的有  33 组

同一个对拍器、同一个 bug、同样是 300 组数据——生成器多了一句 max(a) > 0，抓到数从 33 变成 0。这就是「测了个寂寞」：跑了三百组，一组都没碰到问题所在。

所以生成器要照着题面的取值域写，不是照着你心里舒服的范围写。题面说「-10^9 \le a_i \le 10^9」，生成器就得允许全负、允许全零、允许重复、允许取到端点。

范围有两个维度，两个都容易造窄：

• 值域与结构：上面这个例子。题面允许负数，你只造正数，就漏掉了整类情况。
• 规模：题面上限是 10^5，你只造到 10。小数据能抓到逻辑错，但抓不到性能退化——一个在该合并时没合并的并查集、一个退化成链的哈希表，在 n = 10 时和正确答案完全一样。

边界清单

对拍用的是随机数据，但随机数据不太会撞上极端情况。所以除了对拍，还要有一份固定的边界清单，一条一条手动跑。四大类：

「最小」那一类最值钱，因为它最容易被跳过。n = 1 时很多循环体一次都不执行，best 之类的初值就原样交回去了——本课块 1 抓到的 [-7] 就是这一类。

多组数据要清空

题面写「共 T 组数据」的时候，多了一个全新的出错面：组与组之间的状态。

凡是定义在循环外面的东西——全局变量、类属性、累加器、上一次的答案——都必须在新一组开始时清掉。漏一个，第一组对、第二组开始就错：

class Solver:
    def __init__(self):
        self.total = 0

    def reset(self):
        self.total = 0

    def answer(self, a):
        for x in a:
            self.total += x
        return self.total


CASES = [[1, 2, 3], [10, 20], [5]]
EXPECT = [6, 30, 5]

s = Solver()
leaky = [s.answer(a) for a in CASES]        # 三问之间没清空
s.reset()
clean = []
for a in CASES:
    s.reset()
    clean.append(s.answer(a))

print(f'   三组数据      : {CASES}')
print(f'   忘了清空      : {leaky}')
print(f'   每问都清空    : {clean}')
print(f'   正确答案      : {EXPECT}')
print(f'   忘了清空对吗: {leaky == EXPECT}    每问清空对吗: {clean == EXPECT}')

   三组数据      : [[1, 2, 3], [10, 20], [5]]
   忘了清空      : [6, 36, 41]
   每问都清空    : [6, 30, 5]
   正确答案      : [6, 30, 5]
   忘了清空对吗: False    每问清空对吗: True

结果从 [6, 30, 5] 变成 [6, 36, 41]——第一组是对的。所以如果你只拿样例的第一组数据试，什么都看不出来。

取模与溢出

题面写「答案对 10^9 + 7 取模」的时候，最常见的错法是中途忘了取。而这件事在小数据上完全看不出来：

MOD = 10 ** 9 + 7


def fib_nomod(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a


def fib_mod(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, (a + b) % MOD
    return a


print(f'   MOD = {MOD:,}')
print('   n        不取模（末 14 位）        取模后的值      两者相等吗')
for n in (10, 30, 50, 100, 1000, 10000):
    x, y = fib_nomod(n), fib_mod(n)
    tail = str(x)[-14:]
    print(f'   {n:>5}      …{tail:>14}   {y:>14}   {x == y}')
print(f'   不取模在 n = 10000 时的位数: {len(str(fib_nomod(10000)))} 位')

   MOD = 1,000,000,007
   n        不取模（末 14 位）        取模后的值      两者相等吗
      10      …            55               55   True
      30      …        832040           832040   True
      50      …   12586269025        586268941   False
     100      …48179261915075        687995182   False
    1000      …95166849228875        517691607   False
   10000      …10059947366875        271496360   False
   不取模在 n = 10000 时的位数: 2090 位

n \le 30 时两版一模一样，n = 50 开始分道扬镳。 因为第 50 个斐波那契数 12{,}586{,}269{,}025 第一次超过了 10^9 + 7。你拿小样例试，永远试不出来。

Python 的整数不会溢出（这是它的好处），所以「忘了取模」在 Python 里带来的不是报错，而是静默地交出一个错误的数——比 C++ 里溢出成一个负数更难发现。

答案格式

这一类错误跟算法无关，纯属输出没照题面写，但一样是零分。逐条对：

「多解」那一条要特别注意：题面写「任意一组」不等于不检查——判题器会验你给的那组是否合法，而不是跟你比对某一份标准答案。所以这类题的自检不是对拍，是写一个合法性检查器，拿它验自己输出的方案。

提交前清单

把上面几节压成一份可以照着做的清单：

1. 样例逐字对。 题面给的每一组样例都跑一遍，输出与题面给的答案逐字符比，不是「看着差不多」。
2. 边界四类跑一遍。 最小、最大、重复、退化，一条一条手动跑，看输出合不合理。
3. 独立参考解对拍。 参考解必须换一种思路写。对拍不过就把反例缩到最小，找到根因再改代码。
4. 生成器照题面写。 值域和规模两个维度都要盖到题面上限。
5. 规模压到上限跑一次计时。 只看它有没有在时限内跑完，不看答案——这一步专门抓性能退化。
6. 多组数据混着测。 至少造一组「第 1 组小、第 2 组大、第 3 组相等」的数据，专门看状态有没有串。
7. 格式逐条核。 对着上一节那张表一条条过。
8. 删掉调试输出。 用样例输入跑一遍，标准输出里只该有答案。

第 3 步和第 5 步是两条独立的证据：对拍证明「答案对」，计时证明「跑得完」。只做其中一个都不够——本课那个并查集的例子，两版答案逐字一致，但一版跑 101 秒。

这一课用到的判断

• 过样例只证明代码能跑起来。 样例是「正常」数据，验不了边界、退化、多组之间的影响。
• 参考解必须换一种思路写。 实测 500 组数据：同一个思路的「参考解」抓到 0 组，独立暴力解抓到 58 组。同思路的参考解是对拍器里的装饰品。
• 生成器的范围照题面写。 同一个 bug、同样 300 组数据，生成器多一句 max(a) > 0，抓到数从 33 变成 0。
• 范围有值和规模两个维度。 小数据抓逻辑错，抓不到性能退化——并查集那两版在小数据上逐字一致，在 n = 20000 上差 2800 倍。
• 边界清单四类：最小、最大、重复、退化。 「最小」最值钱也最常被跳过，n = 1 时循环体一次都不进，初值会原样交出去。
• 多组数据的错法里，第一组往往是对的。 实测 [6, 30, 5] 变成 [6, 36, 41]，只有第二组起才错。最省事的修法是别把状态放在外面。
• 取模错在小数据上看不出。 n \le 30 时取不取模一模一样，n = 50 才分道扬镳。Python 不溢出，所以这类错是静默的。
• 「输出任意一组」要自己写合法性检查器。 判题器验的是你那组合不合法，不是跟你比某份标准答案。
• 对拍证明答案对，计时证明跑得完，两条证据缺一不可。

• Python 官方文档 · random官方 · 造对拍数据用的 randint / choice / seed，固定种子才能复现
• OI Wiki · 对拍社区 · 对拍脚本的常见写法与数据生成器设计
• 第 15 课：实验二：用暴力解验证你的答案对拍的完整流程与最小反例化，这一课是它的进阶
• 第 19 课：并查集：合并与查询本课引用的那个「小数据全对、大数据差 2800 倍」的例子
• 第 28 课：看数据规模挑算法第 5 步「压到上限跑一次」之后该换什么算法
• 第 29 课：让 Python 再快一点压上限超时后，先看是量级问题还是常数问题