题解 | #01串题#

1. 算法核心思路

这个问题本质上是一个栈消除（Stack Elimination）或括号匹配类的问题。

• 消除规则分析： 每次删除相邻且相同的字符（"00" 或 "11"），这意味着字符是成对消失的。

  • 无论怎么删除，剩余字符串中字符的相对顺序（0和1的交替关系）是保留的。
  • 最终无法操作的字符串，一定是一个交替字符串（例如 010101... 或 101010...）。因为如果有相邻相同的字符，就可以继续操作。
  • 由于题目保证目标长度 是偶数，且最终字符串是交替的，那么最终字符串中 0 和 1 的数量一定相等，均为 个。

• 构造策略： 我们需要构造一个字符串，使得它包含 个 0 和 个 1，并且在消除后剩下 个 0 和 个 1 组成的交替串。 这意味着我们需要将多余的 个 0 和 个 1 通过“自我消除”的方式抵消掉。

  • 要让字符自我消除，最简单的方法是将它们成对放置（例如 00、11）。
  • 因此，多余的 0 的数量必须是偶数，多余的 1 的数量也必须是偶数。

• 构造方案： 我们可以将字符串分为三部分拼接：

  1. 多余的 0：将所有需要消除的 0 放在最前面。因为数量是偶数，它们会两两消除殆尽。
  2. 多余的 1：将所有需要消除的 1 紧接着放在后面。因为数量是偶数，它们也会两两消除殆尽。
  3. 目标串：最后放置长度为 的交替字符串（如 0101...），这部分将保留下来。

  由于消除结果具有唯一性（与消除顺序无关），前两部分自我抵消后，剩下的就是第三部分。

2. 算法步骤

1. 计算目标需求： 由于 是偶数，最终保留的字符串中需要 个 0 和 个 1。

2. 可行性判断（输出 -1 的情况）： 检查以下条件是否同时满足，如果任一条件不满足，则无法构造，输出 -1：

   • 数量足够：原始的 必须大于等于 ，且 必须大于等于 。
   • 奇偶性匹配：需要消除的 0 的数量 必须是偶数。
   • 奇偶性匹配：需要消除的 1 的数量 必须是偶数。
   • (注：由于删除操作总是减少2个字符，如果总长度 与目标长度 的奇偶性不同，或者 与 奇偶性不同，都无法达成目标。上述条件已涵盖这些逻辑。)

3. 构造字符串： 如果条件满足，按以下顺序输出字符：

   • 输出 个字符 '0'。
   • 输出 个字符 '1'。
   • 输出 组 '01'（即重复输出 '01' 共 次）。

3. 复杂度分析

• 时间复杂度：

• 空间复杂度： 或 如果直接输出字符而不存储整个字符串，空间复杂度为 。如果需要先构建字符串再输出，则需要 的空间来存储结果。

4. 代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b, x;
    cin >> a >> b >> x;
    int t = x / 2;

    if (a < t || b < t)
        goto invalid;

    if ((a - t) % 2 == 1 || (b - t) % 2 == 1)
        goto invalid;

    for (int i = 0; i < (a - t) / 2; i++)
        cout << "00";
    for (int i = 0; i < (b - t) / 2; i++)
        cout << "11";
    for (int i = 0; i < t; i++)
        cout << "01";
    cout << "\n";

    return 0;

invalid:
    cout << "-1\n";
    return 0;
}