题解：FiSi 游戏最小操作次数问题（CCO 2023 Day2 T1）

一、题目核心分析

1. 问题本质

给定 01 字符串 $S$ 和 $T$，通过翻转子串操作（不改变字符总数，仅改变子串内部顺序），让 $S$ 不再包含 $T$ 作为子串，求最少操作次数或判断不可行。

2. 关键观察

• 翻转子串的特性：不改变字符串中 0 和 1 的总数，仅改变相邻字符的组合方式。
• 分类讨论依据：由于 $|T| \leq 3$，且 $T$ 的字符组合（如 $10$ vs $11$、$101$ vs $111$）直接决定消除策略，因此按 $|T|$ 的长度和 $T$ 的字符模式分类讨论是核心思路。
• 预处理技巧：若 $T$ 首字符为 $0$，可将 $S$ 和 $T$ 所有字符翻转（0↔1），转化为 $T$ 首字符为 $1$ 的等价问题，不影响最终结果。

二、完整代码

#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define N 100010
using namespace std;

string s, t;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> s >> t;

    // 预处理：将 T 首字符转为 1（0↔1 翻转）
    if (t[0] == '0') {
        for (int i = 0; i < s.size(); i++)
            s[i] ^= 1;  // 0^1=1, 1^1=0，等价于翻转
        for (int i = 0; i < t.size(); i++)
            t[i] ^= 1;
    }

    // 情况 1：T 长度为 1（此时 T 必为 "1"）
    if (t.size() == 1) {
        for (int i = 0; i < s.size(); i++)
            if (s[i] == '1') {  // 翻转无法减少 1 的数量，有 1 则无法消除
                cout << "-1\n";
                return 0;
            }
        cout << "0\n";  // 无 1，无需操作
        return 0;
    }

    // 情况 2：T 长度为 2
    if (t.size() == 2) {
        // 子情况 2.1：T 为 "10"（字符不同）
        if (t[0] != t[1]) {
            int num = 0;
            // 统计 S 中 "10" 的个数（每个 "10" 需一次操作消除）
            for (int i = 1; i < s.size(); i++)
                if (s[i-1] == '1' && s[i] == '0')
                    num++;
            cout << num << '\n';
            return 0;
        }

        // 子情况 2.2：T 为 "11"（字符相同）
        int num0 = 0, num1 = 0, num = 0;
        for (int i = 0; i < s.size(); i++) {
            num0 += (s[i] == '0');  // 0 的总数
            num1 += (s[i] == '1');  // 1 的总数
            if (i) num += (s[i] == '1' && s[i-1] == '1');  // "11" 的个数
        }
        // 可行性判断：需 num0 ≥ num1 - 1（足够的 0 分隔 1，避免 "11"）
        if (num0 < num1 - 1) {
            cout << "-1\n";
            return 0;
        }
        cout << num << '\n';  // 每个 "11" 需一次操作消除
        return 0;
    }

    // 情况 3：T 长度为 3
    // 子情况 3.1：T[0] != T[2]（如 T=100、110 反转后）
    if (t[0] != t[2]) {
        // 若 T[0] == T[1]（如 T=110），反转 S 和 T 转化为 T=011，再预处理为 100 模式
        if (t[0] == t[1]) {
            reverse(s.begin(), s.end());
            reverse(t.begin(), t.end());
            // 反转后可能 T 首字符为 0，需再次预处理
            if (t[0] == '0') {
                for (int i = 0; i < s.size(); i++)
                    s[i] ^= 1;
                for (int i = 0; i < t.size(); i++)
                    t[i] ^= 1;
            }
        }
        // 此时 T 为 "100"，统计 S 中 "100" 的个数（每个需一次操作）
        int num = 0;
        for (int i = 1; i + 1 < s.size(); i++)
            if (s[i-1] == '1' && s[i] == '0' && s[i+1] == '0')
                num++;
        cout << num << '\n';
        return 0;
    }

    // 子情况 3.2：T[0] == T[2] 且 T[0] != T[1]（如 T=101）
    if (t[0] != t[1]) {
        // 统计 S 中 "101" 的个数，每两个需一次操作（如 10101 → 翻转中间三位得 11011，消除两个）
        int num = 0;
        for (int i = 1; i + 1 < s.size(); i++)
            if (s[i-1] == '1' && s[i] == '0' && s[i+1] == '1')
                num++;
        cout << (num + 1) / 2 << '\n';  // 向上取整
        return 0;
    }

    // 子情况 3.3：T 为 "111"（三个字符全相同）
    int num0 = 0, num1 = 0, num = 0, lft0 = 0, lft1 = 0;
    // 统计 0 和 1 的总数
    for (int i = 0; i < s.size(); i++) {
        num0 += (s[i] == '0');
        num1 += (s[i] == '1');
    }

    // 遍历连续的 1 段，计算基础操作次数和剩余孤立 1 的情况
    for (int i = 0; i < s.size();) {
        int j = i;
        while (j < s.size() && s[j] == s[i]) j++;  // 找到当前连续段的结束位置
        if (s[i] == '1') {
            int len = j - i;
            num += (len - 1) / 2;  // 长度为 len 的 1 段需 (len-1)/2 次操作拆分（如 1111 → 1010，需 1 次）
            if (len & 1) {  // 长度为奇数
                if (len == 1) lft0++;  // 孤立的 1（长度 1）
                else lft1++;  // 长度 ≥3 的奇数段（拆分后剩 1 个孤立 1）
            }
        }
        i = j;
    }

    // 可行性判断：(num0 + 1)*2 ≥ num1（每个 0 最多支持 2 个 1，+1 是首尾可额外放 1）
    if ((num0 + 1) * 2 < num1) {
        cout << "-1\n";
        return 0;
    }

    // 处理剩余孤立 1 的配对问题
    lft0 = max(0, lft0 - lft1);  // 未配对的孤立 1 数量
    if (lft0) {
        int mx = (num0 + 1) * 2 - num1;  // 额外可容纳的孤立 1 数量
        lft0 = (max(0, lft0 - mx) + 1) / 2;  // 剩余需额外操作的次数（每两个需一次）
    }

    cout << num + lft0 << '\n';  // 总操作次数 = 基础操作 + 额外操作
    return 0;
}

三、分情况详细讲解

1. 预处理：统一 $T$ 首字符为 1

若 $t[0] = '0'$，将 $s$ 和 $t$ 中所有字符翻转（s[i] ^= 1 等价于 0↔1 转换）。这是因为：

• 翻转整个字符串的操作不改变问题本质（只是将 0 和 1 互换）；
• 统一后可减少分支判断，所有情况均基于 $T$ 首字符为 1 处理。

2. 情况 1：$|T| = 1$（此时 $T = "1"$）

• 目标：消除 $S$ 中所有 '1'；
• 关键限制：翻转子串无法改变 '1' 的总数；
• 结论：
  • 若 $S$ 中存在 '1' → 无法消除，输出 $-1$；
  • 若 $S$ 中无 '1' → 无需操作，输出 $0$。

3. 情况 2：$|T| = 2$

子情况 2.1：$T = "10"$（字符不同）

• 问题：消除 $S$ 中所有 "10" 子串；
• 操作逻辑：每次翻转可将一个 "10" 转为 "01"（如翻转子串 "10"），每个 "10" 需一次操作；
• 实现：统计 $S$ 中 "10" 的出现次数，直接输出该次数（如样例 1 中 $S=100110$ 包含 2 个 "10"，输出 2）。

子情况 2.2：$T = "11"$（字符相同）

• 问题：消除 $S$ 中所有 "11" 子串；
• 可行性判断：需用 0 分隔 1，避免相邻。若 0 的数量 $num0 < num1 - 1$（$num1$ 个 1 至少需 $num1 - 1$ 个 0 分隔），则无法消除，输出 $-1$；
• 操作逻辑：每个 "11" 需一次翻转拆分（如 "11" → "10"）；
• 实现：统计 $S$ 中 "11" 的出现次数，输出该次数。

4. 情况 3：$|T| = 3$

子情况 3.1：$T[0] \neq T[2]$（如 $T=100$、$110$）

• 转化逻辑：若 $T=110$（$T[0] = T[1]$），反转 $S$ 和 $T$ 得到 $T=011$，再预处理为 $T=100$（首字符转为 1）；
• 问题：消除 $S$ 中所有 "100" 子串；
• 操作逻辑：每次翻转可将 "100" 转为 "001"（如翻转子串 "100"），每个 "100" 需一次操作；
• 实现：统计 $S$ 中 "100" 的出现次数，输出该次数。

子情况 3.2：$T=101$（$T[0] = T[2] \neq T[1]$）

• 问题：消除 $S$ 中所有 "101" 子串；
• 操作逻辑：连续的 "101" 可通过一次翻转消除多个。例如 "10101" 翻转中间三位得 "11011"，消除 2 个 "101"，因此每 2 个 "101" 需一次操作；
• 实现：统计 "101" 的个数 $num$，输出 $\lceil num / 2 \rceil$（即 $(num + 1) / 2$）。

子情况 3.3：$T=111$（三个字符全相同）

• 问题：消除 $S$ 中所有长度 ≥3 的 1 连续段；
• 可行性判断：需满足 $(num0 + 1) \times 2 \geq num1$（每个 0 最多支持 2 个 1，首尾可额外各放 1 个），否则无法消除，输出 $-1$；
• 操作逻辑：
  1. 基础操作：长度为 $len$ 的 1 连续段需 $(len - 1) / 2$ 次操作拆分（如 $len=4$ → 1 次，$len=5$ → 2 次）；
  2. 额外操作：拆分后剩余的孤立 1 需配对消除，每两个孤立 1 需一次操作；
• 实现：
  • 统计基础操作次数 $num$；
  • 计算剩余孤立 1 的数量 $lft0$，并转化为额外操作次数；
  • 总操作次数 = $num + lft0$。

四、样例解析

样例 1

输入：

100110
10

• 预处理：$T$ 首字符为 1，无需翻转；
• 情况：$|T|=2$ 且 $T=10$；
• 统计 $S$ 中 "10" 的位置：第 1-2 位（10）、第 5-6 位（10），共 2 次；
• 输出：2（与样例一致）。

样例 2

输入：

000
00

• 预处理：$T$ 首字符为 0，翻转后 $S=111$，$T=11$；
• 情况：$|T|=2$ 且 $T=11$；
• 可行性判断：$num0=0$，$num1=3$，$0 < 3-1=2$，无法消除；
• 输出：$-1$（与样例一致）。

五、复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为 $|S|$。所有操作均为线性遍历，无嵌套循环；
• 空间复杂度：$O(1)$（除输入存储外，无额外空间消耗）。

六、总结

本题的核心是利用 $|T| \leq 3$ 的限制，通过分类讨论覆盖所有可能的模式，结合翻转子串的特性（不改变字符计数、仅改变相邻组合）设计策略。关键在于：

1. 预处理统一问题模型，减少分支；
2. 针对每种模式分析可行性（基于字符计数）和最少操作次数（基于模式统计）；
3. 利用线性遍历保证算法效率，适配 $n \leq 2 \times 10^5$ 的数据范围。