从零开始的算法复建
前言
高考之后，算法能力大幅退化，于是决定从零开始重建。本文记录了从零开始算法复建的过程。
贪心
贪心算法是大多数人最早接触的算法之一，但其内涵远比表面看来深刻。
基本思想
贪心的基本思想是：在 不对后续产生影响 的前提下，对当前子问题做出 局部最优选择。由于这一局部抉择不会对后续（全局）产生影响，因此所得的局部最优解能够构成全局最优解，即满足 最优子结构。
类型一：直接利用贪心选择性质
首先，我们需要明确“不对后续产生影响”的具体含义。
通常分为以下两种情况：
- 选择当前元素后，后续可选元素的集合不变（不影响后续选择的可行性）；
- 选择当前元素后，后续选择的最优解不受影响（不影响后续最优解的价值）。
第一种情况通常较为显然，此处不再赘述。重点分析第二种情况。
若当前步骤的某个选择在效果上 严格优于或等价于 其他所有选择，则该选择必然能导向最优解。区间选择问题就是一个典型的例子。
区间选择问题
给定一组区间，要求选出尽可能多的互不重叠区间。贪心策略：每次选择结束时间最早的区间。
证明思路：设最优解 \(O\) 的第一个区间为 \(I'\)，其结束时间不早于贪心选择的区间 \(I\)。将 \(O\) 中的第一个区间替换为 \(I\)——由于 \(I\) 结束更早，剩余空间更大，后续可选区间数不会减少，替换后依旧是最优解。反复替换，最终得到贪心解。这一证明的本质是：局部最优（最早结束）为后续留下了最大的自由度。
此类问题中，我们可以较为直观地得出某种选择严格优于其他选择，因此可以直接采用贪心策略。
类型二：序列排序型（调整法）
但对于有些问题，个别选择的优劣难以直接比较。此时需要通过 调整法 来证明贪心解的最优性。
例题：P1080 国王游戏
对此类序列排序问题，若单独讨论第 \(i\) 个元素的选择，其对后续的影响极大，难以直接比较。此时可以考虑 调整法。
每次选取相邻的两个位置，分别放置 \(a_i\) 和 \(a_j\)，通过比较交换前后价值的改变，得到使总价值增加的条件。依据此条件对序列进行排序，即可得到最优解。
为何调整法有效？其正确性可以从两个角度来理解：
正向建构：设想我们逐个确定每个位置的最优元素。假定最优元素不在最前面，我们通过不断交换相邻元素将它"冒泡"到当前位置，交换过程始终朝向价值增加的方向。最终每个位置都放着该处的最优元素——这与贪心的局部最优思想一脉相承。
反证法：若一个序列不满足上述排序条件，则必然存在相邻逆序对。交换这对元素即可得到更优解，与"当前为最优解"的假设矛盾。
需要注意：以上证明有一个默认前提——我们找到的排序条件必须满足 严格弱序性，即“小于”关系具有传递性，且“等于”关系同样具有传递性。只有满足这一前提，才能对序列进行正确排序。
一定要满足严格弱序性吗
更本质地说，我们只需要保证最终序列中任意两个元素之间都满足排序条件即可。因此，如果比较条件本身不满足传递性，人为构造一套满足传递性的关系也是可行的。详见 P2123 皇后游戏。
由于只需考虑相邻元素的交换，证明难度远低于任意两个元素的交换，从而大幅简化问题。
类型三：反悔贪心
对于另一些问题，上面两种情况都不适用：我们无法找到一个选择使得保证能够在后续取到最优解。此时便需要引入 反悔贪心。
例题：P2949 [USACO09OPEN] Work Scheduling G
反悔贪心的核心思想是引入“补票”机制，允许在未来撤销已经做出的选择。
具体到本题，使用反悔贪心的关键在于：所有顾客的价值贡献 相同（均为 \(1\)，目标是最大化满足的顾客数）。这为反悔提供了可能——可以先尽量贪心地满足顾客，由于每位顾客的价值都是 \(1\)，后续的反悔不会影响总价值。在此基础上，剩余商品越多，越可能达到全局最优解。
重新审视题目，我们沿用了贪心的思想：让剩余商品最多的选择尽量满足顾客。然而，局部最优并不保证全局最优——剩余商品最多的步骤未必能导向整体最优解。但由于本题中所有顾客的价值相同，引入反悔机制后，便可以让这种局部贪心导向全局最优解。
博弈论
这里主要讲 SG 函数相关。
理论基础
参见 OI Wiki。
这里简单总结：
- 游戏的和/组合：简单理解为多个游戏组合，每次只能操作其中一个。记为 \(G+H\)。
- 游戏的等价：\(\forall H\)，\(H+G\) 和 \(H+G'\) 的胜负关系都相同，则 \(G\) 和 \(G'\) 等价。记为 \(G\sim G'\)。
- Nim 游戏：我们记单堆 \(n\) 石子的 Nim 游戏为 \(*n\)。
- Sprague–Grundy 理论：所有公平组合游戏都等价于单堆 Nim 游戏。
- 根据 SG 理论，我们定义 SG 函数：若 \(G\sim *n\)，则定义 \(\operatorname{SG}(G) = n\)。
- 类比 Nim 游戏，我们可以得到，对于游戏组合 \(\{G_i\}_{1\le i\le n}\)，该组合的 SG 函数为 \(\oplus _i \operatorname{SG}(G_i)\)。
- \(G+G\) 永远为先手必败（对称性）
- 若 \(H\) 先手必败，则 \(G+H\sim G\)
Multi-SG
先从 SG 函数最简单的应用开始。
这道题的特点在于堆可以 分裂。处理方法是，考虑操作后的局面相当于分裂后的所有堆的 和，因此将每种后继情况的「所有堆 SG 值的 \(\operatorname{xor}\)」取 \(\operatorname{mex}\) 即可。（当然本题 \(O(n^2)\) 无法通过，需要整除分块。）
由此可以看出，游戏的和与 Nim 和之间的顺序是可以穿插的。当涉及不同后继情况时用 \(\operatorname{mex}\)，涉及不同游戏的组合时取 \(\operatorname{xor}\)。
“堆”的定义
对于这道题，我们不能盲目套用 SG 函数了。最大的问题在于，一个堆（瓶子）的操作会影响到其他堆，这就导致堆之间并不是独立游戏，无法使用游戏组合的方法。
对于这种问题，我们通常需要转换思路。我们不应再拘泥于题目中的“堆/瓶子”，甚至不必再局限于“堆”本身。所谓“堆”的本质，其实就是一个包含若干后续状态的游戏局面。所以我们其实可以用最有利的方式切割原来的游戏，使其成为若干个独立的子游戏（也就是 Nim 游戏或前文所认为的“堆”）。
具体地，考虑一次操作前后，什么东西变化了，什么东西没变。我们倾向于将变化的内容尽量放入一个子游戏及其后续，而不变的内容则倾向于与该子游戏保持独立。对于本题而言，一次操作实际上只涉及三个豆子。那么我们将一个豆子看作一个子游戏，那么豆子所在瓶子的编号则是该子游戏的“局面”，而移走的两个位置则是子游戏的后续分裂。由此就可以用 SG 函数模拟解决了。
利用游戏的等价替换
在上一个问题中，我们还能注意到，在将一个豆子视为单独子游戏之后，最终答案是所有豆子的异或。而对于两个相同位置（即所在瓶子编号）的豆子，他们的 SG 异或会相互抵消，也就是最终答案只和每个位置豆子个数的奇偶性有关。
这是否是普遍结论呢？其实是的。这里要用到上面的等价游戏。对于两颗相同位置 \(i\) 的豆子 \(H_i\)，\(H_i+H_i\) 为先手必败局面，所以原游戏 \(G\sim G+(H_i+H_i)\)。也即我们可以任意地在同一个瓶子加减 \(2\) 的倍数，最终答案自然只和奇偶性有关。这个技巧便是使用游戏的等价性简化题目。
例 1
对于这道题，我们还是先观察一次操作，哪些东西会改变。然而我们发现，一次操作可能会改变很多硬币的状态，这导致我们很难将其分割为独立的子游戏。
此时就要用到上面的方法。我们将“硬币翻转”等价为“在上面叠放一枚硬币”，这一等价不会改变每个位置硬币的奇偶性，根据上面的证明，这样的等价是成立的。这时一个操作就不会影响原有的硬币了，而只会添加新的硬币，可以视为堆分裂。这时候再打表找规律就可以解决这道题。
这一部分也对应着 OI Wiki 的 这里，本质上是相同的。
例 2
阶梯 Nim 游戏
共有 \(n\) 堆石子，第 \(i\) 堆有 \(a_i\) 枚石子。两名玩家轮流操作，每次操作中，要么取走第 \(1\) 堆石子中的任意多枚，要么将第 \(i>1\) 堆石子中的任意多枚移动到第 \(i-1\) 堆，但不能不做任何操作。取走最后一枚石子的玩家取胜。
这种题比较有技巧性。整体思路为我们先观察得到一类必败的子局面 \(H\)，那么根据 \(G\sim G+H\)，我们可以用 \(H\) 来化简 \(G\)。
对于本题，注意到若奇数堆全为 \(0\)，则先手必败。读者自证不难。 那么对于任意局面 \(G\)，我们可以构造 \(H\) 为 \(G\) 的所有偶数堆（奇数堆清零），那么 \(G\sim G'+H\)，其中 \(G'\) 自然就为 \(G\) 的所有奇数堆。此时每次左移操作会将奇数堆挪到偶数堆（或者在第一堆删掉），此时用同样的方法可以等价为将其删掉。这样原题便转化为只有奇数堆的 Nim 游戏。