Moe's CF Life

喵~ 主人，今天我们来一起看看 Codeforces 上的 1399D 这道题吧！这道题就像是整理一堆混在一起的黑白毛线球，要把它们理成一根根漂亮的黑白相间毛线，还想用最少的线头，听起来就很有趣对不对？(ฅ'ω'ฅ)

题目大意

简单来说，题目会给我们一个只包含 '0' 和 '1' 的二进制字符串 s。

我们的任务是，把这个字符串 s 里的每一个字符，都分配到一个子序列里。最终，我们要把整个字符串 s 划分成若干个子序列，并满足以下两个条件：

最少化：划分出的子序列数量要尽可能的少。
交替性：每个子序列本身必须是 "010101..." 或者 "101010..." 这种 '0' 和 '1' 交替出现的形式。也就是说，子序列里不能有两个连续的 '0' 或者两个连续的 '1'。

最后，我们需要输出两个东西：

最少需要多少个子序列，我们称之为 k。
一个长度和 s 相同的数组，表示 s 的第 i 个字符属于第几个子序列。

举个栗子，如果 s = "0011"，我们可以把它分成两个子序列：

子序列 1: s[0] 和 s[3]，组成 "01"
子序列 2: s[1] 和 s[2]，组成 "01" 这样就满足了条件，最少需要 2 个子序列。所以 s 中每个字符对应的子序列编号就是 1 2 2 1。

解题思路喵

这道题呀，用贪心的思想就能很漂亮地解决哦！让本喵来给你分析一下思路的说~

我们的目标是子序列数量最少，对吧？那最直接的想法就是，尽可能地重复利用已经存在的子序列，而不是每次都开一个新的。就像猫猫有了玩具，就不会总想着要新的啦（除非是新的小鱼干！）。

我们可以从左到右遍历整个字符串 s。对于当前遇到的字符 s[i]，我们想把它放到一个已经存在的子序列的末尾。什么样的子序列可以接纳它呢？

如果 s[i] 是 '0'，那它就需要被添加到一个以 '1' 结尾的子序列后面，这样才能形成 ...10 的交替模式。
如果 s[i] 是 '1'，那它就需要被添加到一个以 '0' 结尾的子序列后面，形成 ...01 的模式。

所以，我们的策略就很清晰了喵：

我们维护两个“池子”（用栈或者队列实现最方便啦），一个叫 ends_with_0，用来存放当前所有以 '0' 结尾的子序列的编号；另一个叫 ends_with_1，存放所有以 '1' 结尾的子序列的编号。
我们从头到尾遍历字符串 s，对于第 i 个字符 s[i]：
- 如果 s[i] 是 '0'：我们去 ends_with_1 池子里看看，有没有可以用的子序列。
  - 如果有 (ends_with_1 不为空），太棒啦！我们就从里面随便拿一个子序列的编号，把当前的 '0' 接在它后面。这个子序列现在就变成以 '0' 结尾了，所以我们要把它的编号从 ends_with_1 移到 ends_with_0 里面。
  - 如果木有 (ends_with_1 为空），那就没办法啦，只能委屈巴巴地创建一个新的子序列了。我们分配一个新的编号给它，然后把这个新编号放进 ends_with_0，因为它现在是一个只包含 '0' 的，以 '0' 结尾的子序列。
- 如果 s[i] 是 '1'：逻辑是完全一样的哦！我们去 ends_with_0 里找一个以 '0' 结尾的子序列。
  - 找到了，就把它接上，然后把编号从 ends_with_0 移到 ends_with_1。
  - 找不到，就创建一个新的，把新编号放进 ends_with_1。
我们每处理一个字符，就记录下它被分配到的子序列编号。遍历结束后，我们就得到了每个字符的归属，以及总共创建了多少个子序列啦！

这个方法为什么是最优的呢？因为我们每一步都尽了最大努力去复用旧的子序列，只有在万不得已（找不到可以续接的子序列）时才创建新的。所以最后得到的子序列数量一定是最小的，喵~

题解代码

下面就是具体的代码实现啦，和我们刚刚讨论的思路一模一样的说！本喵加了一些注释，方便主人理解哦。

cpp

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

// 使用标准命名空间，写起来方便一点喵
using namespace std;

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

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;

        vector<int> ans(n); // 用来存储每个字符所属的子序列编号
        // stack0 存所有以 '0' 结尾的子序列的编号
        // stack1 存所有以 '1' 结尾的子序列的编号
        vector<int> stack0, stack1; 
        int color_count = 0; // 总共用了多少个子序列（也叫颜色）

        for (int i = 0; i < n; i++) {
            if (s[i] == '0') {
                // 当前是'0'，需要找一个以'1'结尾的子序列
                if (stack1.empty()) {
                    // 木有以'1'结尾的，只好开个新的啦
                    color_count++;
                    ans[i] = color_count;
                    stack0.push_back(color_count); // 新的子序列以'0'结尾
                } else {
                    // 找到了！从stack1里拿一个出来用
                    int col = stack1.back();
                    stack1.pop_back();
                    ans[i] = col;
                    stack0.push_back(col); // 这个子序列现在以'0'结尾了
                }
            } else { // s[i] == '1'
                // 当前是'1'，需要找一个以'0'结尾的子序列
                if (stack0.empty()) {
                    // 木有以'0'结尾的，也只好开个新的
                    color_count++;
                    ans[i] = color_count;
                    stack1.push_back(color_count); // 新的子序列以'1'结尾
                } else {
                    // 找到了！从stack0里拿一个
                    int col = stack0.back();
                    stack0.pop_back();
                    ans[i] = col;
                    stack1.push_back(col); // 这个子序列现在以'1'结尾了
                }
            }
        }

        cout << color_count << '\n';
        for (int i = 0; i < n; i++) {
            if (i > 0) cout << ' ';
            cout << ans[i];
        }
        cout << '\n';
    }
    return 0;
}

题目大意 ​

解题思路喵 ​

题解代码 ​

相关知识点介绍 ​

题目大意

解题思路喵

题解代码

相关知识点介绍