A102286 雾港城的开关 题解
一、题目简述
给定一个长度为 (n) 的 01 串 (s)。
一次操作可以选择位置 (i)，把区间 ([i,n]) 的所有位全部翻转（0↔1）。
目标是用最少操作次数，使最终所有位都变成 0。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、关键性质
操作是“翻转后缀”，因此：
* 如果已经处理到位置 (i)
* 之后再进行的任何操作，其起点都必须 (> i)
* 这些操作 不会再影响位置 (i)
所以可以 从左到右贪心地“定型”每一位。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、贪心思路
维护一个变量 flip，表示前面已经执行的翻转次数的奇偶性：
* flip = 0：前面的翻转对当前位无影响
* flip = 1：前面的翻转已将当前位翻转一次
对字符串从左到右扫描：
1. 当前位的真实状态为
(s[i]−′0′)⊕flip(s[i] - '0') \oplus flip (s[i]−′0′)⊕flip
2. 若真实状态为 0：
* 不需要操作，直接继续
3. 若真实状态为 1：
* 若不在当前位置执行操作，则之后任何翻转都不会再影响该位，最终无法变成 0
* 因此 必须在当前位置执行一次操作
* 操作后：
* 操作次数 +1
* flip 取反
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、正确性证明（简述）
对任意位置 (i)：
* 若当前位置在已有翻转影响下为 0，不执行操作是最优的；执行操作只会把它变为 1，且之后无法修复。
* 若当前位置为 1，不在 (i) 执行操作，则之后所有操作都不会影响该位，最终无法变为 0，因此必须在 (i) 执行一次操作。
因此，每一步的决策都是必要且最优的，整体得到的操作次数最少。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、复杂度分析
* 时间复杂度：(O(n))
* 空间复杂度：(O(1))
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、参考代码（AC）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
七、样例说明
输入：
从左到右处理：
* 遇到第一个真实为 1 的位置必须翻转
* 最终共需 2 次操作
输出：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> 翻转后缀的问题应从左到右贪心处理，每一位一旦离开就不会再被影响，这是本题的关键。
