题解 P7814 【心の記憶】

· · 题解

这里是出题人官方题解。

为了保证子序列相同，我们可以直接在 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 中出现次数少的那个。
「插首异」，即插入位置为另一个字符第一次出现的位置后。

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

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

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

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

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

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

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

综上，「插少插首异」的策略是正确的。代码实现的时候分类讨论 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;
}

结语

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