整场模拟、复盘与知识地图

先别猜算法，先冻结题意

这节课我们一起解决整场模拟、复盘与知识地图。拿到题目先圈出输入对象、输出对象、规模上界、数值范围和多测条件，再用一句可判真的话写输出契约。不要看到关键词就套模板；同样写着“最短”“区间”“连通”，边权、更新方式和目标函数一变，正确算法就可能完全不同。本课主机制是：围绕整场模拟、复盘与知识地图先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度。
（本段反查：整场模拟、复盘与知识地图，课位12-7。）

先手算规模不超过8的例子，画数组、队列、栈、集合、图或DP表。每一步写当前状态和它代表的真实含义。样例只能说明程序在那一个输入上得到指定输出，不能证明算法，也不能覆盖空集、重复值、全负数、不连通、极大权值等边界。

从暴力基线出发

前置内容是字符串与竞赛数论。先写一个慢但显然正确的枚举：明确枚举对象、候选数量、验证成本和总复杂度。暴力不是丢人的废代码，它提供正确性参照、随机对拍的标准答案，也让我们看见重复工作究竟发生在哪里。

把重复工作圈出来，再问能否排序后单调移动、保存前缀状态、复用子问题、维护堆或集合、把图分层，或只更新受影响区域。优化不是“换成高级算法”，而是用一个可证明的不变量避免重复计算。

推导状态与不变量

现在按围绕整场模拟、复盘与知识地图先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度推进。循环不变量要回答进入本轮前哪些位置已经正确、未处理部分是什么；DP状态要回答它包含解决未来所需的全部信息且没有多余历史；图算法要回答已确定集合、候选边和松弛上界分别代表什么。
（本段反查：整场模拟、复盘与知识地图，课位12-7。）

每次更新分三步证明：更新前不变量成立；本次操作保持它；循环终止时不变量与终止条件共同推出输出契约。递归还要证明规模严格变小，贪心要给交换或领先证明，数据结构要证明查询与更新维护同一语义。

跟老师走一遍例题

构造一个正常例、一个最小例、一个能击穿错误直觉的反例。先跑暴力并保存答案，再逐操作运行优化算法；记录左右边界、队列首尾、堆顶、并查集代表、dist、dp或残量容量。第一次两份轨迹不同的位置就是调试入口，不要只比较最终一行。

复杂度从真实操作次数推导：每个指针移动多少次，每条边被扫描多少次，每个状态有多少转移，堆操作的元素数是多少。大O不是装饰；必须同时给空间、最坏或摊还口径，并把n、m、V、E、容量或状态维数定义清楚。

反例和适用边界

本节危险边界是：流量模型必须满足容量与守恒；二分图匹配建图方向不能错。 本课必须再检查边界输入、整数溢出、下标和不可行状态。 请主动写一个错误实现，给出最短反例，并指出它第一次违反不变量的操作。比如二分边界不收缩、Dijkstra遇负边、贪心局部选择不可交换、零一背包正序导致物品重复、字符串哈希碰撞未核验。
（本段反查：整场模拟、复盘与知识地图，课位12-7。）

工程边界也要验：空输入、单元素、重复值、答案不存在、图不连通、多重边、自环、1-based与0-based转换、long long溢出、多测未清空、递归爆栈和输出格式。每类边界至少有一组自动测试。

写成能提交的程序

先让清晰参考实现通过，再做常数优化。输入输出必须只依赖标准流，算法主体与解析打印分开；不开未声明的随机性，不依赖本机文件。代码题使用C++17，本地逐题编译，并对正常、最小、失败或极端至少四组用例运行。

提交前用小随机数据对拍：生成器同时喂给暴力和优化版，输出不同时保存种子与首个输入。对拍只能证明测过的数据，正确性仍由不变量或归纳负责；证明与测试互相补位，不能互相冒充。

四类随课练习

单选题检查算法适用条件；多选题逐项判断证据是否充分；计算题要求手推状态数、操作次数或复杂度；论述题公开量表，按契约2分、不变量3分、正确性2分、复杂度1分、反例2分评分。第六、七课通常绑定真实代码题，把纸笔推导落到可执行行为。

做错后标记为读题、模型、证明、复杂度、实现、边界或测试错误。只修代码不修思维流程，下次还会在同一处出错；换一组数据重新从契约走到提交，才能确认已掌握。

前后联系与闭卷验收

本课从字符串与竞赛数论取来对象与操作，向后把不变量交给赛场综合。请画因果链：输入性质为什么允许当前算法，核心结构怎样减少重复工作，删掉哪个条件会使优化失效。

闭卷回答：暴力是什么；重复工作在哪里；状态或不变量是什么；为什么终止后正确；时间空间复杂度从哪里来；最短反例是什么；四组测试覆盖什么。七问都能重建，才算真正会做，而不是见过题解。