A102286 雾港城的开关 题解

一、题目简述

给定一个长度为 (n) 的 01 串 (s)。
一次操作可以选择位置 (i)，把区间 ([i,n]) 的所有位全部翻转（0↔1）。
目标是用最少操作次数，使最终所有位都变成 0。

---

二、关键性质

操作是“翻转后缀”，因此：

• 如果已经处理到位置 (i)
• 之后再进行的任何操作，其起点都必须 (> i)
• 这些操作 不会再影响位置 (i)

所以可以 从左到右贪心地“定型”每一位。

---

三、贪心思路

维护一个变量 flip，表示前面已经执行的翻转次数的奇偶性：

• flip = 0：前面的翻转对当前位无影响
• flip = 1：前面的翻转已将当前位翻转一次

对字符串从左到右扫描：

1. 当前位的真实状态为

   $$(s[i] - '0') \oplus flip$$

2. 若真实状态为 0：

   • 不需要操作，直接继续

3. 若真实状态为 1：

   • 若不在当前位置执行操作，则之后任何翻转都不会再影响该位，最终无法变成 0

   • 因此 必须在当前位置执行一次操作

   • 操作后：

     • 操作次数 +1
     • flip 取反

---

四、正确性证明（简述）

对任意位置 (i)：

• 若当前位置在已有翻转影响下为 0，不执行操作是最优的；执行操作只会把它变为 1，且之后无法修复。
• 若当前位置为 1，不在 (i) 执行操作，则之后所有操作都不会影响该位，最终无法变为 0，因此必须在 (i) 执行一次操作。

因此，每一步的决策都是必要且最优的，整体得到的操作次数最少。

---

五、复杂度分析

• 时间复杂度：(O(n))
• 空间复杂度：(O(1))

---

六、参考代码（AC）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    string s;
    cin >> n >> s;

    int flip = 0;   // 当前翻转奇偶
    int ans = 0;    // 最少操作次数

    for (char c : s) {
        int cur = (c - '0') ^ flip;
        if (cur == 1) {
            ans++;
            flip ^= 1;
        }
    }

    cout << ans << '\n';
    return 0;
}

---

七、样例说明

输入：

6
001110

从左到右处理：

• 遇到第一个真实为 1 的位置必须翻转
• 最终共需 2 次操作

输出：

2

---

翻转后缀的问题应从左到右贪心处理，每一位一旦离开就不会再被影响，这是本题的关键。