【题解】P17414「IXOI R3」贴吧 82 号 —— 从左到右的强制贪心

题目链接：洛谷 P17414
难度：普及−　|　算法标签：贪心、位运算（异或翻转）、数学归纳
时间限制 1.00s，内存限制 512MB，开启 O2 优化
代码来源：luogu/17414/1.cpp

〇、写在前面

这是一道思路极简、但证明很值得品味的题。代码只有十来行，但想清楚“为什么这么贪心一定最优”才是本题的核心。整篇题解会按「读题 → 样例手玩 → 发现关键结构 → 贪心 → 严格证明 → 代码 → 对拍 → 总结」的顺序展开，力求把每一步都讲透。

一、题意

给定一个长度为 $n$ 的 01 字符串 $s$（下标从 $1$ 开始）。

你可以进行若干次操作，每次操作选择一个正整数 $x$（$1 \le x \le n$），然后把所有下标是 $x$ 的倍数的位置上的字符取反（$0 \to 1$，$1 \to 0$）。

求：最少需要多少次操作，才能把整个字符串变成全 $1$。

输入格式

第一行一个整数 $n$；第二行一个长度为 $n$ 的字符串 $s$。

输出格式

一行一个整数，即最少操作次数。

数据范围

对于 $100$ 分的数据（即全部数据），$1 \le n \le 10^5$，$s$ 仅由 0、1 组成。

看到 $n \le 10^5$，暴力枚举操作集合（$2^n$）显然不行。但注意：操作本身只有 $n$ 种可选（$x = 1 \dots n$），而且操作满足交换律、每次操作是自身的逆（对合）。这类结构往往有非常干净的性质。

二、样例手玩

样例 #1

4
1010

• 目标全 $1$。位置 $1$ 是 1，不动它。
• 位置 $2$ 是 0，我们希望把它翻成 1。选择 $x=2$，翻转位置 $2,4$：

$1010 \longrightarrow 1111$

• 已经全 $1$，结束。共 1 次。

样例 #2

2
01

• 位置 $1$ 是 0，选 $x=1$（注意：$1$ 的倍数包含所有位置），翻转位置 $1,2$：

$01 \longrightarrow 10$

• 位置 $2$ 仍是 0，选 $x=2$，翻转位置 $2$：

$10 \longrightarrow 11$

• 共 2 次。

样例 #3

3
000

• 位置 $1$ 是 0，选 $x=1$，翻转全部：$000 \to 111$，共 1 次。

三组样例已经暗示了一个规律：从左到右扫描，遇到 0 就立刻用 $x=i$ 修掉它。

下图把样例 #1 的完整演算画了出来，同时对比了样例 #2 里 $x=1$ 的特殊作用：

三、关键观察

3.1 操作的含义

一次 $x$ 操作，就是给所有「$x$ 的倍数」位置打一个“翻转开关”。下图展示了 $x=2$ 与 $x=3$ 分别影响哪些位置：

注意两个要点：

1. 操作会互相影响：比如位置 $6$ 会被 $x=1,2,3,6$ 反复翻转，翻的次数决定最终是 $0$ 还是 $1$。
2. $x$ 操作影响的位置最小也是 $x$ 本身，往后的都是 $2x, 3x, \dots$。

3.2 核心结构：三角性

这是本题最重要的一句话：

能影响位置 $i$ 的操作 $x$，一定满足 $x \mid i$（$x$ 整除 $i$），因此 $x \le i$。

为什么呢？位置 $i$ 只有在“$i$ 是 $x$ 的倍数”时才会被 $x$ 操作翻到，也就是 $x \mid i$。而整除意味着 $x \le i$。

于是，把位置按 $1, 2, \dots, n$ 排好，每个操作 $x$ 影响的是一个“从 $x$ 开始的倍数集合”，用矩阵的语言说：

• 操作对位置的作用矩阵是上三角的（位置 $i$ 只会被 $x \le i$ 的操作影响）；
• 对角线全为 $1$（$x=i$ 一定影响位置 $i$）；
• 在 $\mathbb{F}_2$（模 2）下，这是一个对角元为 1 的上三角矩阵。

上三角 + 对角元非零 $\Longrightarrow$可逆。这意味着：满足“最终全 $1$”的操作集合是唯一的！

换句话说，本题根本没有“在多个合法方案里挑最少”的空间——解唯一，所以“最少的操作次数”就等于那唯一解的规模。我们的任务只是把它求出来。

3.3 从左到右的强制贪心

既然解唯一，那就可以用最朴素的“高斯消元”式思路，只不过因为三角性，消元退化成了一次线性扫描：

从左到右处理位置 $i = 1, 2, \dots, n$：

• 如果位置 $i$ 当前是 1，那它已经正确，若再用任何操作去翻它反而会破坏别的已定位置，所以对 $i$ 不做操作；
• 如果位置 $i$ 当前是 0，那么在“所有 $x < i$ 的操作都已确定”的前提下，唯一还能修正它、又不会回头破坏前面位置的操作就是 $x = i$，所以必须执行 $x=i$。

下图解释了“为什么轮到位置 $i$ 时只有 $x=i$ 可用”：

为什么“遇到 0 才操作、遇到 1 不操作”是被迫的？

• 当我们扫到位置 $i$ 时，所有 $x < i$ 的操作已经定死（因为再往后就轮不到改它们了）；
• 能翻到 $i$ 的操作只有 $x \mid i$，而其中 $x < i$ 的已成定局，$x > i$ 的又够不着位置 $i$；
• 所以**“位置 $i$ 的最终值 = 目前已确定操作对它的翻转次数 + （是否用 $x=i$）”**。这是一个“用不用 $x=i$”的二选一：
  • 当前是 1：如果还用 $x=i$，它会被翻成 0，直接失败；所以不能用。
  • 当前是 0：如果不用 $x=i$，它永远是 0，没有别的操作能救它；所以必须用。

这不是“贪心也许正确”，而是每一步都没有选择余地的强制推导。因此得到的操作次数就是唯一解，也就是最小值。

3.4 一个自然的实现

扫描时，“当前值是 0 还是 1”不需要真的反复翻转整个倍数序列——模拟一下即可（$n \le 10^5$，调和级数复杂度足够）。用 $s$ 本身当状态，遇到 0 就 cnt++，并把所有 $i$ 的倍数位置翻转：

for (int i = 1; i <= n; i++) {
    if (s[i] == '1') continue;      // 已是 1，不动
    cnt++;                          // 必须操作 x = i
    for (int j = i; j <= n; j += i)
        s[j] ^= 1;                  // 翻转所有 i 的倍数
}

内层循环总次数是

$\sum_{i=1}^{n} \left\lfloor \frac{n}{i} \right\rfloor = O(n \log n),$

完全跑得动。

四、完整参考代码（1.cpp）

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 5;
ll n;
string s;
ll a;
ll len;
ll cnt;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin >> n >> s;
    s = " " + s;                       // 1-indexed，方便处理倍数下标
    len = s.length();
    for (ll i = 1; i < len; i++)
    {
        if (s[i] - '0') continue;      // 当前位是 '1'，跳过
        cnt++;                          // 是 '0'，必须操作 x = i
        for (ll j = i; j < len; j += i) // 翻转所有 i 的倍数位置
        {
            s[j] = (s[j] == '0' ? '1' : '0');
        }
    }
    cout << cnt;
    return 0;
}

代码细节说明

• s = " " + s; 把下标整体右移一位，让位置从 $1$ 开始，直接与题意对齐，避免到处写 i - 1。
• if (s[i] - '0') continue;：字符 '1' - '0' = 1（真），'0' - '0' = 0（假）。所以这句话就是“是 1 就跳过，是 0 就处理”。
• s[j] = (s[j] == '0' ? '1' : '0'); 就是对单个位置取反；也可以写成 s[j] ^= 1（对 '0'/'1' 而言等价）。
• 循环里没有额外开数组，直接用字符串当状态，空间 $O(n)$。

复杂度

$n = 10^5$ 时，$n \log n \approx 1.7 \times 10^6$，实测 0 秒出头，轻松通过。

五、多解法对比

为什么贪心能取代高斯消元？ 因为方程组系数矩阵是上三角且对角元为 1，消元时不需要回代找主元——位置 $i$ 的方程里，未知数 $x > i$ 的系数全为 $0$，只剩“用不用 $x=i$”这一个未知数，于是直接解出。“三角矩阵让高斯消元退化为一次扫描”，这就是本题的精髓。

六、易错点 / 踩坑合集

1. 下标从 1 开始，倍数的含义别搞错。 $x$ 操作翻的是 $x, 2x, 3x, \dots$。代码里用 s = " " + s 统一成 1-indexed，是对齐题意的关键。
2. $x=1$ 会翻转所有位置。 这是最容易被忽略的操作——样例 #2 正是靠 $x=1$ 先把 01 变成 10。写对拍/手玩时别忘。
3. 别把“最少”理解成要搜索。 解是唯一的，贪心不是“在很多解里挑坏的”，而是“把唯一解求出来”。想清楚这点，才能自信地不用搜索。
4. 内层取反别写错。 对字符 '0'/'1'，s[j] ^= 1 与 s[j] = (s[j]=='0'?'1':'0') 等价；若混用 s[j] = 1 - (s[j]-'0') + '0' 也可以，但注意不要把它写成对整数取反后忘记加回 '0'。
5. cin >> n >> s 之间可能有的空白。 cin >> s 会自动跳过换行/空格，正常；但如果用 getline 混用要格外小心前导换行。本题用 cin >> 最省心。
6. 数据范围与类型。 答案最大为 $n$（每个位置各操作一次），$n \le 10^5$，int 足够；代码里用 ll 也无妨。
7. 子任务 2（全 0 / 全 1）不必特判。 全 1 时循环直接跳过，输出 $0$；全 0 时先操作 $x=1$ 变全 1，输出 $1$——贪心天然覆盖。

七、对拍验证

为确认正确性，我用暴力程序做了三重验证：

1. 官方样例：三组样例 4/1010、2/01、3/000 分别输出 1、2、1，全部吻合；
2. 穷举小数据：$n \le 12$ 时枚举所有$2^n$ 个串，用「枚举 $2^n$ 种操作集合的暴力」对拍正解，全部一致；
3. 随机大数据：$n \in [13,18]$ 随机 300 组，仍与暴力一致（暴力 $O(2^n)$ 已接近上限）。

结论：1.cpp 为本题的正确最终版本。

说明：本目录下只有 1.cpp 与自带测试输入 in，没有 2.cpp 等多个版本需要甄别。

八、小结

一句话总结：“翻转倍数”问题的系数矩阵是上三角且对角为 1，因此解唯一；从左到右遇到 0 就翻 $x=i$，既是贪心，也是唯一正确的强制推导。