Moe's CF Life

哈喽，各位小伙伴们，你们好呀！我是你们的小助教猫娘，今天也要元气满满地和大家一起学习算法喵~ (ฅ'ω'ฅ)

今天我们要看的是一道非常有趣的构造题，来自 Codeforces 的 Problem 1352F - Binary String Reconstruction。别看是 F 题，其实它是一只很温顺的小猫咪，只要我们顺着它的毛摸，就能轻松解决啦！

题目大意喵

这道题是这样的：有一个神秘的二进制字符串 s（也就是只包含 '0' 和 '1' 的字符串）。有人把这个字符串里所有相邻的两个字符（也就是长度为 2 的子串）都拿了出来。

然后，他数了数：

含有 0 个 '1' 的子串（也就是 "00"）有 n0 个。
含有 1 个 '1' 的子串（也就是 "01" 或 "10"）有 n1 个。
含有 2 个 '1' 的子串（也就是 "11"）有 n2 个。

现在，我们只知道 n0, n1, n2 这三个数字，需要我们反过来，构造出任何一个满足这些条件的二进制字符串 s。题目保证了至少有一个数字大于 0，并且解总是存在的。

举个栗子🌰：如果字符串是 s = "1110011110"，那么它的相邻字符对有： "11", "11", "10", "00", "01", "11", "11", "11", "10"。我们数一下：

"00" 有 1 个 => n0 = 1
"01" 或 "10" 有 3 个 ("10", "01", "10") => n1 = 3
"11" 有 5 个 => n2 = 5 所以，如果输入是 1 3 5，输出 1110011110 就是一个正确的答案。

解题思路喵

看到这种构造题，不要害怕喵~ 我们一步一步来分析，就像猫猫拆毛线球一样，总能找到线头的！

首先，我们来分析一下这三种字符对是怎么产生的：

"00"：它由两个连续的 '0' 组成。如果我们有一串连续的 k 个 '0' (00...0)，它会产生 k-1 个 "00" 对。所以，想要得到 n0 个 "00" 对，最简单的办法就是放一串 n0 + 1 个 '0'。
"11"：同理，想要得到 n2 个 "11" 对，最简单的办法就是放一串 n2 + 1 个 '1'。
"01" 和 "10"：这两个是 '0' 和 '1' 之间的“过渡”地带。每当字符串从 '0' 变为 '1'，就产生一个 "01"；从 '1' 变为 '0'，就产生一个 "10"。它们共同构成了 n1 的计数。

我们的任务是构造任何一个合法的字符串，所以我们可以用最简单、最直接的方法来构造它！

情况一：没有 '0' 和 '1' 的混合（`n1 == 0`）

这是最简单的情况啦，就像猫猫只吃一种口味的猫粮一样，很简单喵~ 如果 n1 是 0，说明字符串里没有 "01" 或 "10" 这种交错。这意味着，整个字符串要么全是 '0'，要么全是 '1'！

如果 n0 > 0，那字符串肯定全是 '0'。为了得到 n0 个 "00"，我们需要 n0 + 1 个 '0'。
如果 n2 > 0（题目保证了 n0+n1+n2 > 0，所以 n1=0 且 n0=0 时，必有 n2>0），那字符串就全是 '1'。为了得到 n2 个 "11"，我们需要 n2 + 1 个 '1'。

情况二：'0' 和 '1' 混合存在（`n1 > 0`）

当 n1 > 0 时，事情就变得有趣起来了，我们需要巧妙地把 '0' 和 '1' 编织在一起。一个非常直接的策略是：

先满足 n0 和 n2：我们先把所有需要的 "00" 和 "11" 一次性造出来。怎么造最简单？当然是把它们各自聚成一整块啦！
再处理 n1：然后我们再来处理 n1 个过渡。

让我们来实践一下这个策略喵：

首先，我们先一口气写下 n2 + 1 个 '1'。比如 111...1。这样，n2 个 "11" 对就全部搞定了！
接着，我们紧跟着写下 n0 + 1 个 '0'。比如 000...0。这样，n0 个 "00" 对也全部搞定了！

现在，我们的字符串变成了 11...100...0 的样子。我们来盘点一下成果：

n2 个 "11"：满足了。
n0 个 "00"：满足了。
n1 呢？在 '1' 串和 '0' 串的连接处，我们得到了一个 "10" 过渡。这消耗了 n1 的一个名额。

太棒了！我们已经满足了 n0, n2，并且还顺便解决了一个 n1。现在我们还需要 n1 - 1 个过渡。

我们的字符串目前以 '0' 结尾。怎么制造新的过渡呢？

在末尾加一个 '1'，就得到了一个 "01" 过渡。字符串现在以 '1' 结尾。
再在末尾加一个 '0'，又得到了一个 "10" 过渡。字符串现在以 '0' 结尾。
再加 '1' ... 再加 '0' ...

发现规律了吗？我们只需要在后面交替地追加 101010... 这样的序列，每追加一个字符，就能得到一个新的过渡！就像猫猫玩毛线球，一拉一扯，'0' 和 '1' 就交替出现啦！

所以，我们只需要在 11...100...0 的基础上，再追加一个长度为 n1 - 1 的 1010... 交替序列，所有问题就都解决啦！

这种构造方法一定能得到一个正确的解，而且实现起来非常简单。

题解代码

下面就是根据我们的思路写出的 C++ 代码啦，加上了猫娘的专属注释哦~

cpp

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

void solve() {
    int n0, n1, n2;
    std::cin >> n0 >> n1 >> n2;

    // 情况一：没有 '0' 和 '1' 的交替，喵~
    if (n1 == 0) {
        if (n0 > 0) {
            // 只有 "00" 对，所以整个字符串都是 '0'
            std::cout << std::string(n0 + 1, '0') << "\n";
        } else { // n2 > 0 的情况
            // 只有 "11" 对，所以整个字符串都是 '1'
            std::cout << std::string(n2 + 1, '1') << "\n";
        }
        return;
    }

    // 情况二：'0' 和 '1' 混合存在，开始构造！
    std::string res = "";

    // 1. 先放一整块 '1'，搞定所有的 "11" 对
    for (int i = 0; i <= n2; ++i) {
        res += '1';
    }

    // 2. 再放一整块 '0'，搞定所有的 "00" 对
    for (int i = 0; i <= n0; ++i) {
        res += '0';
    }
    
    // 此时，我们已经有了一个 "10" 过渡，还剩下 n1 - 1 个过渡需要制造

    // 3. 在末尾追加一个交替的 '1010...' 序列来制造剩下的过渡
    // 因为字符串现在以 '0' 结尾，所以我们从 '1' 开始追加
    char current_char = '1';
    for (int i = 0; i < n1 - 1; ++i) {
        res += current_char;
        // '1' 变 '0'，'0' 变 '1'，就像猫猫翻滚一样~
        current_char = (current_char == '1' ? '0' : '1');
    }

    std::cout << res << "\n";
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

题目大意喵 ​

解题思路喵 ​

情况一：没有 '0' 和 '1' 的混合（n1 == 0） ​

情况二：'0' 和 '1' 混合存在（n1 > 0） ​

题解代码 ​

相关知识点介绍 ​

题目大意喵

解题思路喵

情况一：没有 '0' 和 '1' 的混合（`n1 == 0`）

情况二：'0' 和 '1' 混合存在（`n1 > 0`）

题解代码

相关知识点介绍