自动搬运

查看原文

来自洛谷，原作者为

	Hexarhy 干好饭，睡好觉，遇见好人。

搬运于2025-08-24 22:33:20，当前版本为作者最后更新于2021-08-17 14:51:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这里是出题人官方题解。

为了保证子序列相同，我们可以直接在 01 串 $A$ 的基础上插入 $m-n$ 个字符。下文的所有分析都是基于此的。

下文所有做法都要求先特判无解。

显然 $n=m$ 或 $n=1$ 时无解，因为不可能做到子串不同。除此之外，还有容易忽略的情况是 $A$ 为 01 或 10。

当然，如果不想动脑，随机生成字符串并暴力验证也可以发现只有上述可能。

Subtask 1

由于 $A$ 全是 0，因此在非首尾位置直接插入 $n-m$ 个 1 即可。

期望得分 $10$ 分。

Subtask 2

暴力枚举每一位填 0 还是 1，然后跑一次 KMP 检验是否有子串相同，再用两个指针扫一遍 $A,B$ 看是否有子序列相同。

时间复杂度 $O(m\cdot2^m)$。期望得分 $20$ 分。

Subtask 3

显然直接插入 $m-n$ 个连续的 0 或 1 可以很大机会做到子串不相同。

此时枚举插入位置，再跑 KMP 判断有没有子串相同即可。

时间复杂度 $O(m^2)$。期望得分 $40$ 分。

Subtask 4

送给随机化的选手。乱搞应该都可以过。

期望得分 $70$ 分。

Subtask 5

先放结论：插少插首异。

「插少」，即插入的字符为 0 1 在 $A$ 中出现次数少的那个。
「插首异」，即插入位置为另一个字符第一次出现的位置后。

下面证明这种做法的正确性。

要保证插入一段字符后不会有子串相同，分类讨论一下：

• 插入串与前面拼接成的串的子串不会是 $A$。
• 插入串与后面拼接成的串的子串不会是 $A$。
• 插入串的子串 或者 与前后拼接成的串的子串不会是 $A$。

不失一般性地，假设 1 的数量比 0 少，则插入串为 $m-n$ 个连续的 1。然后我们逐个考虑：

• 插入串与前面拼接成的串的子串不会是 $A$。

显然成立，因为 0 的数量不一致。插首保证了插入串之后还有 0。

• 插入串与后面拼接成的串的子串不会是 $A$。

显然成立，因为 0 的数量不一致。

• 插入串的子串 或者 与前后拼接成的串的子串不会是 $A$。

对于前者，因为 $A$ 中肯定有 0，而插入串没有 0，不会有子串是 $A$。

对于后者，我们要找的子串为了达到这么多 0 的数量，而插入串并没有新增 0 的数量，因此这个子串必须包含插入串。此时第一个和第二个 0 的距离由于插入串发生了改变，因此必定不会有子串同时满足：

• 0 的数量与 $A$ 相同。
• 第一个与第二个 0 的距离与 $A$ 对应相同。

综上，「插少插首异」的策略是正确的。代码实现的时候分类讨论 0 1 数量多少即可。

时间复杂度 $O(m)$。期望得分 $100$ 分。

当然，应该存在不少正确的构造方法，思考难度应该都不大毕竟本来设计出来是打算作 A 题的。

参考代码

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        vector<bool> a(m+10);
        for(int i=1;i<=n;i++)
        {
        	int x;scanf("%1d",&x);
        	a[i]=x;
		}
        if(n==m || n==1 || (n==2 && (a[1]^a[2])))
        {
            puts("-1");
            continue;
        }
        int cnt0=0,cnt1=0;
        for(int i=1;i<=n;i++)   a[i]?cnt1++:cnt0++;
        bool f=false;
        for(int i=1;i<=n;i++)
        {
            printf("%d",int(a[i]));
            if(!f && (cnt1<cnt0?!a[i]:a[i]))
            {
                for(int j=1;j<=m-n;j++)
                	printf("%d",int(cnt1<cnt0));
                f=true;
            }
        }
        putchar('\n');
    }
    return 0;
}

结语

本题定位为签到题，题意简洁，代码简短，没有涉及任何高深算法，考察了选手的构造能力和细心程度是不可多得的好题。