P7814

题目传送门

题目简述

• 有两个由0和1组成的字符串 $A$ 和 $B$ ，其中 $A$ 小于 $B$ 。

• 其中 $A$ 不是 $B$ 的字串但是 $A$ 却是 $B$ 的子序列。

• 找出一个满足要求得 $B$ 串并输出。

• 一共 $T$ 组询问， $A$ 串长度为 $n$ ， $B$ 串长度为 $m$ , 其中 $1 \le n \le m , 1 \le \sum m \le 2 \times 10 ^ 6$

题目分析

首先我把这道题分为了两个部分：

1. 当 $A$ 长度为一和二时

2. 当 $A$ 的长度在三以上的时候。

我们来分别讨论以上两种情况：

长度为 $1$ 或 $2$

显然， 如果长度为 $1$ 时一定找不到一个满足条件的 $B$ 。
再来讨论 $2$ 的情况，设想， 如果这两个数一个是 $0$ ， 一个是 $1$ ， 也不存在可行解， 事实上当 $A$ 的长度和 $B$ 的长度一样时也时无解的。 那么难道只要 $A$ 长度为 $1$ 或 $2$ 就都无解吗？其实不是， 如果 $A$ 形如 $00$ ，那 $B$ 只要像 $01...10$ 就可以了。 $11$ 时同理。

长度在 $3$ 以上

1. 如果在原序列中 $1$ 和 $0$ 都有， 就有一种比较妙的容易想到的方法， 比如现在的序列是这样的： $01110101010$ 我们不妨将第一个数 $(0)$ 和后面所有的数分开来看，如果我在第一个数 $(0)$ 的后面一直添加和它不同的数 $(1)$ ， 那么后面的所有数 $(1110101010)$ 和前面的那个新加的数 $(1)$ 一定组成不了原序列。所以成立！

2. 那么新的问题出现了如果我的序列是这样的： $011111111$ 会发现用上一个方法不行了，应为如果在第一个数 $(0)$ 后面加不同的数 $(1)$ 时第一个数会和后面的数组成原序列， 俗话说特殊情况特殊处理， 我们不难想到从第二个数开始插入与后面的数 $(1)$ 不同的数 $(0)$ ，就像这样： $010...011111111$ 。好啦，现在这个问题也愉快的解决啦！

AC Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

const int N = 1e6;

int n, m;
char a[N];

inline int check(int l, int r)              //判断序列的成分， 全是0则返回0， 全是1则返回1， 如果都有则返回-1；
{
    bool one = false, zero = false;
    for (register int i = l; i <= r; i++)
        if (one == true && zero == true) return -1;
        else if (a[i] == '1') one = true;
        else zero = true;
    if (one == true && zero == true) return -1;
    if (one == true && zero == false) return 1;
    else return 0;
}

using namespace std;

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        cin >> a;
        int len = strlen(a);
        if (n == m || n == 0 || n == 1)        //特殊的无解情况
        {
            printf("-1\n");
            continue;
        }
        if(n == 2)                             //A长度时2的情况
        {
            if(a[0] == a[1])
            {
                printf("%c", a[0]);
                for (int i = 1; i <= m - n; i++) printf("%c", ~a[0] + 98);
                printf("%c\n", a[len - 1]);
            }
            else printf("-1\n");
            continue;
        }
        int right = check(1, len - 1);
        if(right == 1 || right == 0)            //常规情况
        {
            printf("%c%c", a[0], a[1]);
            for (int i = 1; i <= m - n; i++) printf("%c", ~a[1] + 98);
            for (int i = 2; i <= len - 1; i++) printf("%c", a[i]);
            printf("\n");
            continue;
        }
        else
        {
            printf("%c", a[0]);
            for (int i = 1; i <= m - n; i++) printf("%c", ~a[0] + 98);
            for (int i = 1; i <= len - 1; i++) printf("%c", a[i]);
            printf("\n");
            continue;
        }
    }
    return 0;
}

后记

此题主要在于思维， 对于代码的要求极低， 但是思维一定要打开。