题解证明链检查：结论正确，也要说明为什么不能反例

一、题解最怕只给做法，不给证明

算法题解里，很多文章会直接给思路和代码：用贪心、用二分、用单调队列。代码可能能过，但读者看完还是不知道为什么这么做是对的。题解的核心不是“我会写”，而是“这个方法不会被反例打爆”。

AI 生成题解时，这个问题更明显。模型能写出很顺的解释，却可能跳过关键证明。尤其是贪心、二分答案、图论最短路这类题，证明链断一环，整个题解就不稳。

二、证明链至少包含不变量和边界

一份可检查题解应包含状态定义、转移依据、循环不变量、边界条件和复杂度证明。

flowchart TD A[题目约束] --> B[算法选择] B --> C[关键不变量] C --> D[正确性证明] D --> E[边界条件] E --> F[复杂度分析] F --> G[代码实现]

如果题解先写代码，再补一句“显然正确”，基本就可以判定证明链太薄。

三、用检查清单约束题解生成

下面示例定义题解检查项。AI 生成后，可以先按结构检查。

REQUIRED_SECTIONS = ["状态定义", "转移依据", "正确性证明", "边界条件", "复杂度分析"] def missing_sections(text: str) -> list[str]: return [item for item in REQUIRED_SECTIONS if item not in text]

这只是第一层。结构齐全不代表证明正确，但结构不齐全，肯定还不能算高质量题解。

四、反例检查比自我肯定更有用

证明链检查要主动找反例。比如贪心题，要问局部最优是否能交换成全局最优；二分题，要问判定函数是否单调；动态规划题，要问状态是否遗漏信息。

还要用暴力解做小范围验证。对 n 很小的随机数据，用暴力解和优化解对拍。证明负责逻辑，测试负责抓实现和边界。两者都要有。

最后，题解要说明适用条件。Dijkstra 不能处理负权边，拓扑排序要求有向无环，滑动窗口通常依赖单调移动。条件不写清，读者很容易套错模板。

证明链还要检查“必要性”和“充分性”。很多题解只证明用了这个方法可以得到答案，却没有说明为什么不会漏掉更优解。比如贪心题只说每次取最大收益，却没证明交换后不变差，这个证明就不完整。

对动态规划题，状态定义要能覆盖全部历史信息。如果状态少了关键维度，转移写得再漂亮也会错。检查时可以反问：两个样本落到同一个状态时，未来决策是否一定相同？如果不相同，状态就不够。

复杂度证明也要和代码一致。题解说 O(n)，代码里却在循环里做切片或查找，就可能变成 O(n²)。AI 生成题解时尤其容易口头复杂度和实现脱节。

最后，证明链可以配合最小反例。每当某个证明步骤说“显然”，就尝试构造反例。如果能构造出来，说明这一步不是显然，是漏洞。

循环不变量是证明链里最容易被忽略的一项。比如双指针题，左指针为什么只增不减，右指针为什么不会错过答案，都需要不变量支撑。只说“移动较小的一边”不够，要说明移动后被丢弃的状态为什么不可能更优。

边界证明也要单独写。空数组、单元素、全相等、严格递增、严格递减，这些样本不只是测试用例，也是证明是否完整的检查点。一个算法如果只能解释普通样本，遇到边界就靠代码碰运气，那题解还没写完。

对图论题，还要证明访问顺序。BFS 为什么第一次到达就是最短，Dijkstra 为什么弹出时距离可信，拓扑排序为什么能处理所有依赖。这些不是模板注释，而是算法成立的关键条件。

五、总结

题解证明链检查要逼题解回答“为什么不会错”。状态定义、转移依据、不变量、边界和复杂度都要完整，反例检查和暴力对拍要配合使用。结论正确只是起点，能解释为什么不能被反例推翻，才是可靠题解。