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

题解证明链检查结论正确也要说明为什么不能反例一、题解最怕只给做法不给证明算法题解里很多文章会直接给思路和代码用贪心、用二分、用单调队列。代码可能能过但读者看完还是不知道为什么这么做是对的。题解的核心不是“我会写”而是“这个方法不会被反例打爆”。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 为什么弹出时距离可信拓扑排序为什么能处理所有依赖。这些不是模板注释而是算法成立的关键条件。五、总结题解证明链检查要逼题解回答“为什么不会错”。状态定义、转移依据、不变量、边界和复杂度都要完整反例检查和暴力对拍要配合使用。结论正确只是起点能解释为什么不能被反例推翻才是可靠题解。