喵~ 主人，你好呀！这里是你的专属猫娘小助手。今天我们要解决的是一道关于二进制字符串切割的有趣问题。别担心，只要跟着我的思路，再复杂的问题也会变得像解开一个毛线团一样简单哦！

题目大意

这道题是说，我们拿到一个由 '0' 和 '1' 组成的字符串（二进制串），就像一根黑白相间的毛线。我们的任务是把它剪成几段，然后重新排列这些小段，最后拼成一个“排好序”的字符串。

什么是“排好序”的字符串呢？就是所有的 '0' 都在前面，所有的 '1' 都在后面，比如 00111 这样子。

我们要找的是，最少需要剪成几段才能完成这个任务。每一小段都必须是原来字符串里连续的一部分，而且所有剪下来的小段都必须用上哦。

举个例子喵：对于字符串 11010，我们可以剪成 11、0、10 这三段吗？不行哦，因为 10 这一段本身就不是排好序的。正确的剪法之一是 11、01、0，然后把它们重新排成 0、01、11，就能拼出 00111 啦！这个例子需要 3 段，题目告诉我们这是最少的。

题解方法

这道题呀，其实藏着一个小小的规律，只要我们抓住了它的“尾巴”，问题就迎刃而解啦，喵~

第一步：找到必须剪开的地方

首先，我们来想想，什么样的片段是“坏”的？最终的目标是 00...011...1，里面绝对不会出现 1 在 0 前面的情况。

那么，如果我们的原始字符串里有 ...10... 这样的部分，会发生什么呢？如果我们不从 1 和 0 中间剪开，那么这个 10 就会被包含在同一段里。不管我们怎么移动这一段，里面的 1 永远都在 0 的前面。这样一来，我们就不可能拼出排好序的字符串了！

所以，我们得出一个非常重要的结论：只要字符串中出现了 "10" 这个子串，我们就必须在 '1' 和 '0' 之间剪一刀！ 这是强制性的，没有商量的余地，喵。

第二步：初步分段与观察

好，我们按照上面的规则，在所有 "10" 的地方都剪一刀。这样，原始的字符串就被分成了好几段。比如说，如果字符串里有 k 个 "10"，我们就会得到 k+1 段。

现在我们来看看这些被切开的小段。它们有什么特点呢？因为我们已经在所有 "10" 的地方都切开了，所以任何一段内部都不可能再有 "10" 了。这意味着，这些小段只可能是下面三种类型：

1. 纯 0 串 (比如 000)
2. 纯 1 串 (比如 11)
3. 混合串，但一定是 0 在前 1 在后 (比如 0011)

第三步：最后的拼接魔法

现在我们有了一堆纯 0 串、纯 1 串和 0...1 混合串。要把它们拼成 00...011...1，该怎么放呢？

很简单嘛！

• 所有的纯 0 串都放在最前面。
• 所有的纯 1 串都放在最后面。
• 那混合串呢？因为最终的成品只有一个从 0 到 1 的“连接点”，所以我们最多只能用一个混合串放在中间，作为从 0 区域到 1 区域的桥梁。

这下问题就来了！如果我们通过第一步的切割，得到了好几个（比如说 m 个）混合串，那该怎么办？我们只能选一个作为桥梁，那剩下的 m-1 个混合串就成了“问题儿童”。

怎么处理这些“问题儿童”呢？比如我们有一个多余的混合串 0011，为了让它能被正确归位，我们只能再给它一刀，把它变成 00 和 11 两个纯色串。这样，00 就可以去 0 的队伍，11 就可以去 1 的队伍啦！

每处理一个多余的混合串，都需要额外增加一刀，也就是增加一个片段。

总结一下思路：

1. 数一数原字符串里有多少个 "10" 子串，记为 c10。
2. 在所有 "10" 的位置进行切割，我们会得到 c10 + 1 个初始片段。
3. 数一数这 c10 + 1 个片段里，有多少个是同时包含 '0' 和 '1' 的混合串，记为 m。
4. 我们最多只能保留一个混合串。如果 m > 1，我们就需要对多出来的 m-1 个混合串进行再分割。每次分割增加一个片段。
5. 所以，最终的最小片段数就是 (c10 + 1) + max(0, m - 1)。

这个思路是不是很清晰呀？喵~

题解代码

下面是根据这个思路写出来的 C++ 代码，我已经加上了注释，方便主人理解每一句都在做什么哦。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

void solve() {
    string s;
    cin >> s;
    int n = s.length();

    // 如果字符串长度为1，或者已经排好序了，只需要1段
    bool sorted = true;
    bool found_one = false;
    for (int i = 0; i < n; ++i) {
        if (s[i] == '1') {
            found_one = true;
        }
        if (found_one && s[i] == '0') {
            sorted = false;
            break;
        }
    }
    if (sorted) {
        cout << 1 << endl;
        return;
    }

    // 统计 "10" 出现的次数
    int c10_count = 0;
    for (int i = 0; i < n - 1; ++i) {
        if (s[i] == '1' && s[i+1] == '0') {
            c10_count++;
        }
    }
    
    // 根据我们的推导，答案其实就是 1 + c10_count
    // 咦？好像比上面的分析更简单了？
    // 让我们来验证一下：
    // 初始有 k 个块（连续的0或1），k = 1 + c10 + c01
    // 我们可以合并 c01 次（在 "01" 处合并）
    // 最终片段数 = k - c01 = (1 + c10 + c01) - c01 = 1 + c10
    // 哇！原来最终的公式可以化简成这么漂亮的形式！
    // 之前的分析虽然有点绕，但能帮我们理解为什么是这样，也是很有价值的喵！
    
    cout << c10_count + 1 << endl;
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

（小声）哎呀，我在写代码注释的时候，突然发现一个更简单的规律！原来我们上面那套复杂的分析，最后可以化简成一个超级简单的公式：答案 = 1 + ("10"出现的次数)。虽然最终的实现变简单了，但理解背后的原理才能让我们在遇到新问题时也一样厉害哦！上面的代码我直接用了这个简化后的结论，主人可以对比一下两种思路，是不是很有趣呢？

知识点介绍

1. 贪心思想 (Greedy Approach) 我们的解法中，第一步就是“只要看到'10'就必须切开”，这是一个典型的贪心策略。我们先做出一个当前看起来最优、最必要的决定，然后基于这个决定去解决剩下的问题。很多问题都可以用这种“先解决最要紧的事”的思路来简化。

2. 构造性思维 (Constructive Thinking) 这个问题要求我们求一个最小值，但我们的思考过程其实是在想“如何构造出最终的有序字符串”。通过思考构造的过程和限制（比如最多只能有一个0...1的桥梁），我们反推出了求解最小值的公式。这种从目标反推过程的思维方式在算法题中非常有用。

3. 模式识别与化简 就像我们从复杂的 (c10 + 1) + max(0, m - 1) 一路化简到 1 + c10 一样，在解决问题时，识别出核心模式并把复杂问题简化，是通往高效解法的捷径。有时候，最优雅的答案就藏在最简单的规律里，需要我们有发现它的耐心和洞察力，喵~

好啦，今天的问题就分析到这里！希望我的讲解能帮到主人。如果还有其他问题，随时可以再来找我玩哦！喵~