题解：P13205 [GCJ 2016 #3] Go++

jokersen · 2025-12-22 20:56:49 · 题解

这是官方题解的 AI 中文翻译

像这样处于另一层级的为我个人补充的内容。

首先，我们来判断问题何时无解。当 B\in G 时，问题显然无解 —— 样例输入中已包含此类情况。那么其他情况下呢？

令人意外的是，若 B\notin G，则问题始终有解。

为证明这一点，我们将构造两个 Go++ 程序，按题目描述运行后，能够生成所有长度为 L 的字符串（B 除外）。这听起来比仅生成 G 中的字符串更复杂，但有时将问题“复杂化”反而能帮助我们获得解决原问题所需的关键思路。对于本题而言，集合 G 其实是一个干扰项！

第一个程序

给定输入字符串 B，按以下步骤构造第一个程序：

1. 对 B 中的每个字符取反（0\to 1，1\to 0）；
2. 在每个 0 或 1 指令后添加一个 ? 指令。

例如：

• 若 B = 111（可能出现在小数据集），第一个程序为 0?0?0?；
• 若 B = 010（仅可能出现在大数据集），第一个程序为 1?0?1?。

工作原理

默认情况下，该程序会生成 B 的反串。若要生成其他字符串，需覆盖一个或多个 ? 指令 —— 即两个程序交错执行，在第一个程序的 ? 指令执行前，由第二个程序的某些指令修改输出结果。例如：

• 第一个程序为 1?0?1?，第二个程序为 01，交错执行顺序为 1 0 ? 0 1 ? 1 ?，可输出 011（而非默认的 101）。

若要生成 B，则需覆盖所有 L 个 ? 指令。因此，我们需要构造一个无法覆盖所有 ? 指令的第二个程序，具体实现分小数据集和大数据集两种情况。

第二个程序（小数据集）

小数据集的 B 始终是全 1 字符串，因此第一个程序必然是 0? 重复 L 次（例如 B = 111 时，第一个程序为 0?0?0?）。

我们的第二个程序需要满足：

• 可覆盖任意两个 ? 指令（从而生成最多包含两个 1 的所有输出）；
• 不可覆盖所有三个 ? 指令（避免生成 B）。

解决方案：第二个程序由 L-1 个 1 组成（仅含 L-1 个 1，不含 L 个 1）。例如 B = 111 时，第二个程序为 11。

第二个程序（大数据集）

对于任意 B，第二个程序需满足以下两个核心要求：

1. 包含所有长度为 L-1 的字符串作为子序列（确保能生成除 B 外的所有字符串）；
2. 不包含 B 作为子序列（避免生成 B）。

注：此处“子序列”指元素顺序与原序列一致但无需相邻的任意子集。

构造方法（非最短但易于理解）

1. 取 B 除去最后一个字符的子串；
2. 将每个字符替换为两位序列：0\to 10，1\to 01。

例如：

• 若 B = 010，取前两个字符 01，替换后得到第二个程序 1001（0\to 10，1\to 01）。

注意要特判 B 长度为 1 的情况。

有效性证明

要求 1：包含所有长度为 L-1 的子序列

第二个程序由 L-1 个 01 或 10 的两位对组成（每个两位对均包含 0 和 1）。从每个两位对中任选一个字符，即可组合出任意长度为 L-1 的字符串，因此满足要求 1。

要求 2：不包含 B 作为子序列

以 B = 010、第二个程序 1001 为例：

• 若要从 1001 中提取子序列 010，需先找到第一个 0（位置 2），再找到其后的第一个 1（位置 4），后续无可用字符继续匹配 B 的第三个 0；
• 由于第二个程序的长度为 2(L-1)，而提取 B 作为子序列需至少 L 个字符（且需满足特定顺序），因此无法完整匹配 B，满足要求 2。

参考代码：

#include<bits/stdc++.h>
#define N 105
using namespace std;
int n,l;
string s[N],t;
int main(){
    int T;scanf("%d",&T);
    for(int cas=1;cas<=T;cas++){
        printf("Case #%d: ",cas);
        scanf("%d%d",&n,&l);
        for(int i=1;i<=n;i++) cin>>s[i];
        cin>>t;
        for(int i=1;i<=n;i++)
            if(s[i]==t) goto end;
        if(t.size()==1){
            printf("%c %c?\n",s[1][0],s[1][0]);
            continue;
        }
        for(auto p:t)
            printf("%c?",p^1);
        putchar(' '),t.pop_back();
        for(auto p:t)
            printf("%c%c",p^1,p);
        putchar('\n');continue;
        end:puts("IMPOSSIBLE");
    }
    return 0;
}