第二版（2018年6月印刷）勘误1

《算法竞赛进阶指南》第二版（2018年6月印刷）的勘误主要涉及几个关键的算法和数据结构知识点，以下是这些知识点的详细解释： 1. **最小表示法**： 在处理字符串问题时，最小表示法用于找到字符串的循环节，即最短的重复子串。原书中描述不够准确，修订后的表述指出，如果在扫描了所有字符后仍相等，说明存在更小的循环元，并且这个循环元已经扫描完成。这意味着可以通过`𝐵[min(𝑖, 𝑗)]`找到最小表示。 2. **双端队列BFS（广搜变形）**： 在广度优先搜索（BFS）中，使用双端队列可以优化某些问题的解决。原来的描述错误地表示每个节点仅访问一次，但实际情况是节点可能被多次更新（入队），然而，首次从队列中扩展（出队）的节点将得到从起点到该节点的最短距离。 3. **同余理论**： 在数论中，最小公倍数（LCM）的概念用于表示同余关系。原书中用乘积表示，而修正后使用了LCM的表示方法，即`𝑚 = lcm(𝑚1, 𝑚2, … , 𝑚𝑘−1)`。 4. **二叉查找树（BST）的删除操作**： 二叉查找树的删除操作是一个复杂的问题，因为它需要保持树的有序性。原书中删除函数的C++实现有一个引用错误，已从非递归改为递归实现，确保正确处理节点的删除和替代，特别是处理有左右子树的情况。 5. **KM算法**（Kuhn-Munkres算法）： 这是一种求解二分图最大匹配的算法。修正后的代码中，全局数组`upd`的引入是为了记录更新，以避免每次调用`dfs`时重新计算。在`dfs`函数内，对`upd[y]`的更新和在`KM`函数中对全局数组的初始化和使用，都是为了优化算法的效率，确保找到最大匹配。 以上这些勘误对于理解和应用这些算法至关重要。在学习和实践算法竞赛时，确保理解这些修正点能帮助提高解决问题的准确性，避免因误解而犯错。同时，作者提供的GitHub资源是一个宝贵的补充，读者可以在这里找到完整的程序示例和更新，以便深入学习和调试。