竞赛算法与算法训练 · 小纸条

选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。

第 1 页 · 正面（题目）

1排序稳定性与比较模型

闭卷重建排序稳定性与比较模型的对象、状态、事件、不变量与一个失败反例。

2归并排序的分治证明

闭卷重建归并排序的分治证明的对象、状态、事件、不变量与一个失败反例。

3逆序对与跨区间贡献

闭卷重建逆序对与跨区间贡献的对象、状态、事件、不变量与一个失败反例。

4二分查找的区间不变量

闭卷重建二分查找的区间不变量的对象、状态、事件、不变量与一个失败反例。

5二分答案与可行性判定

闭卷重建二分答案与可行性判定的对象、状态、事件、不变量与一个失败反例。

6分治递推与主定理边界

闭卷重建分治递推与主定理边界的对象、状态、事件、不变量与一个失败反例。

7最近点对与分治复盘

闭卷重建最近点对与分治复盘的对象、状态、事件、不变量与一个失败反例。

第 1 页 · 背面（答案）

核心机制：围绕归并排序的分治证明先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成归并排序的分治证明的暴力、优化、对拍与复盘；边界：二分必须先证明单调谓词；递归要写终止规模与合并成本。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕排序稳定性与比较模型先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成排序稳定性与比较模型的暴力、优化、对拍与复盘；边界：二分必须先证明单调谓词；递归要写终止规模与合并成本。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕二分查找的区间不变量先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成二分查找的区间不变量的暴力、优化、对拍与复盘；边界：二分必须先证明单调谓词；递归要写终止规模与合并成本。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕逆序对与跨区间贡献先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成逆序对与跨区间贡献的暴力、优化、对拍与复盘；边界：二分必须先证明单调谓词；递归要写终止规模与合并成本。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕分治递推与主定理边界先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成分治递推与主定理边界的暴力、优化、对拍与复盘；边界：二分必须先证明单调谓词；递归要写终止规模与合并成本。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕二分答案与可行性判定先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成二分答案与可行性判定的暴力、优化、对拍与复盘；边界：二分必须先证明单调谓词；递归要写终止规模与合并成本。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕最近点对与分治复盘先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成最近点对与分治复盘的暴力、优化、对拍与复盘；边界：二分必须先证明单调谓词；递归要写终止规模与合并成本。本课必须再检查边界输入、整数溢出、下标和不可行状态。。