E. Skibidus and Rizz - 题解

比赛与标签

比赛: Codeforces Round 1003 (Div. 4) 标签: constructive algorithms, greedy, strings 难度: *1600

喵喵，题目在说什么呀？

主人你好呀~ 这道题是说，Skibidus小哥想要我们帮忙构造一个二进制字符串s，这个字符串需要满足三个条件呐：

1. 它由 n 个 '0' 和 m 个 '1' 组成。
2. 它的总长度是 n+m。
3. 在它所有的子串中，'0'的数量和'1'的数量之差的绝对值（我们叫它“平衡值”）最大不能超过 k，也必须能达到 k。也就是说，所有子串的最大平衡值恰好是 k。

如果能构造出这样的字符串，我们就把它打印出来；如果不行，就告诉Skibidus这是不可能的，输出 -1 喵~

解题思路，启动！

这道题看起来有点复杂，但别担心，我们一步一步来拆解它，就像猫猫拆毛线球一样简单！

第一步：简化问题喵！

题目中有 n 和 m 两个变量，分别代表 '0' 和 '1' 的数量。为了方便思考，我们可以先假设其中一种字符的数量总是比另一种多。比如说，我们总是假设 '0' 的数量不少于 '1' 的数量。

如果一开始 n < m（'0'比'1'少），我们就假装把'0'和'1'的角色互换一下！我们心里记着 n 现在是多数的那个，m 是少数的那个，最后输出的时候再把字符换回来就好啦。这样一来，我们就可以统一处理 n >= m 的情况了，是不是很机智呀？

第二步：无解的情况分析

在动手构造之前，我们先想想什么情况下是绝对不可能构造成功的。这能帮我们快速排除掉一些情况，就像猫猫先检查罐头能不能打开一样重要！

1. k 太大了: 平衡值是 |#0 - #1|。在一个子串里，'0' 的数量最多也就是总共的 n 个。所以，任何子串的平衡值都不可能超过 n（或者 m，取决于哪个更大）。经过我们的简化，n 是多数，所以平衡值绝不会超过 n。如果题目要求的 k > n，那肯定是办不到的啦，直接输出 -1。

2. k 太小了: 整个字符串 s 本身也是一个子串。它的平衡值是 |n - m|。因为我们已经保证了 n >= m，所以这个值就是 n-m。既然整个字符串的平衡值都是 n-m 了，那么所有子串中的最大平衡值肯定不会比它小。所以，如果题目要求的 k < n-m，那也是不可能的，同样输出 -1。

第三步：猫猫的构造大法！

排除了无解的情况，剩下的 n-m <= k <= n 就是我们大展身手的时候了！我们的目标是构造一个字符串，让最大平衡值刚好是 k。

这里有一个超级好用的思想：前缀和！ 我们定义一个“前缀净值”d，从左到右扫描字符串，遇到一个多数角色（比如'0'）就让d加1，遇到少数角色（比如'1'）就让d减1。 一个子串 s[i..j] 的平衡值，就等于它结尾的前缀净值 d_j 减去它开始前一位的前缀净值 d_{i-1}。 所以，所有子串的最大平衡值，就等于所有前缀净值中的最大值与最小值之差，即 max(d) - min(d)。

为了让这个差值恰好为 k，最简单的办法就是让 min(d) = 0，max(d) = k。 我们可以这样构造：

1. 打下基础: 先连续放 k 个多数角色（'0'）。 00...0 (k个) 此时，前缀净值序列是 1, 2, ..., k。max(d) 已经达到 k，min(d) 是 0（别忘了还有个 d_0=0 哦）。

2. 精细调控: 接下来，我们还有 n-k 个'0'和 m 个'1'没用。为了不让 max(d) 超过 k，也不能让 min(d) 掉到负数，我们可以成对地放 10。 每放一个 10，前缀净值会先从 k 变成 k-1，再变回 k。这样净值就在 k 和 k-1 之间来回摆动，非常安全！ 我们有多少个'0'和'1'可以组成 10 对呢？当然是取两者中较小的那个数量，也就是 min(n-k, m) 对。但是根据我们之前的推导 k >= n-m => m >= n-k，所以我们总是有足够的'1'来配对剩下的 n-k 个'0'。 于是我们放 n-k 对 10。

3. 收尾工作: 现在，所有的 n 个'0'都已经用完啦。我们还剩下 m - (n-k) 个'1'。把它们全部放到字符串的末尾。 此时，前缀净值会从 k 开始，每加一个'1'就减1，最后会降到 k - (m-n+k) = n-m。 因为我们知道 k >= n-m >= 0，所以这个过程中净值始终保持在 [n-m, k] 区间内，不会低于0。

这样一来，整个构造过程中，前缀净值的最大值始终是 k，最小值始终是 0。最大平衡值恰好就是 k-0=k！任务完成，喵~

特殊情况: 如果一开始 m=0，说明字符串里只有一种字符。那子串的平衡值就是 1, 2, ..., n。最大平衡值就是 n。所以只有当 k=n 时有解。

代码实现喵！

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

void solve() {
    long long n, m, k;
    std::cin >> n >> m >> k;

    bool swapped = false;
    // 简化问题，我们总是假设 n >= m。
    // 如果 m > n，就交换它们，并用 swapped 标记一下。
    if (n < m) {
        std::swap(n, m);
        swapped = true;
    }

    // 根据 swapped 标记，确定哪个是多数角色，哪个是少数角色。
    char zero_char = swapped ? '1' : '0';
    char one_char = swapped ? '0' : '1';

    // 特殊情况：如果 m=0，字符串只有一种字符。
    // 子串的平衡值会是 1, 2, ..., n，所以最大平衡值一定是 n。
    if (m == 0) {
        if (k == n) {
            for (int i = 0; i < n; ++i) {
                std::cout << zero_char;
            }
            std::cout << '\n';
        } else {
            std::cout << "-1\n";
        }
        return;
    }

    // 现在 n >= m > 0。
    // 检查无解条件。
    // k 不能大于多数角色的总数 n。
    if (k > n) {
        std::cout << "-1\n";
        return;
    }
    // k 不能小于整个字符串的平衡值 n-m。
    if (k < n - m) {
        std::cout << "-1\n";
        return;
    }

    // 构造开始！
    // 第一步：先放 k 个多数角色，让前缀净值达到 k。
    for (int i = 0; i < k; ++i) {
        std::cout << zero_char;
    }
    long long rem_z = n - k; // 剩余的多数角色
    long long rem_o = m;     // 剩余的少数角色

    // 第二步：通过 "少数+多数" 的配对来消耗字符，同时保持净值在 [k-1, k] 波动。
    // p 是可以配对的数量。因为 m >= n-k，所以 p 总是等于 rem_z。
    long long p = std::min(rem_z, rem_o);
    for (int i = 0; i < p; ++i) {
        std::cout << one_char << zero_char;
    }
    rem_z -= p;
    rem_o -= p;

    // 第三步：将剩下的字符全部放上去。
    // 经过第二步，rem_z 必定为 0。我们只需要把剩下的 rem_o 个少数角色放上去。
    if (rem_o > 0) { // rem_z 此时为 0
        for (int i = 0; i < rem_o; ++i) {
            std::cout << one_char;
        }
    }
    // 这个 if 其实是多余的，因为 m >= n-k 保证了 rem_z 在配对后会变成0。但留着也没错。
    if (rem_z > 0) { // rem_o 此时为 0
        for (int i = 0; i < rem_z; ++i) {
            std::cout << zero_char;
        }
    }
    std::cout << '\n';
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析的说

• 时间复杂度: O(n+m) 的说。因为我们只需要遍历一次来构造并输出这个长度为 n+m 的字符串。
• 空间复杂度: O(1) 的说。我们是直接输出字符，没有把整个字符串存起来，所以除了几个变量外，几乎不占用额外空间。

知识点与总结

这道题是一道非常有趣的构造题，它教会了我们几件重要的事情呐：

1. WLOG (Without Loss of Generality): 通过交换 n 和 m 来简化问题，让我们只需要处理一种情况，这是一个非常实用且优雅的技巧！
2. 前缀和思想: 将子串问题转化为前缀和/前缀差问题是解决许多字符串和数组问题的金钥匙。这道题里，把“最大平衡值”和“前缀净值的极差”联系起来，就是解题的突破口！
3. 边界分析: 在构造之前，先分析清楚无解的边界条件 (k > n 和 k < n-m)，可以大大简化后续的逻辑，避免走弯路。
4. 贪心构造: 我们的构造策略（先冲到k，再稳定，最后收尾）是一种贪心的思想。每一步都做出当前看起来最优的选择，最终导向了正确的全局解。

希望这篇题解能帮到你，如果还有不懂的地方，随时可以再来问我哦！一起加油，喵~ >w<