洛谷P7814 「小窝 R3」心の記憶

题意

第一行给定两个数字\(n\) \(m\) \((m \ge n)\)分别代表给定字符串长度以及需要构造出的字符串长度

第二行给定一个长度为\(n\)的字符串 (假设原来的字符串是\(a\) 需要构造出来的字符串是 \(x\))

构造出的字符串需要满足子序列与子串的定义

1.\(x\)的任意一个子串都与\(a\)不相同

2.\(x\)的某一个子序列和\(a\)相同

分析

当 \(n=1\)的时候,显然无法存在\(x\)满足条件
当 \(n=2\)的时候,如果两个字符串中的字符不同,显然构造不出
当 \(n=m\)的时候,显然满足条件\(2\)的时候,\(x\)与\(y\)是一模一样的,无法满足条件\(1\)

假设现在以上三种情况均不可能发生

我们可以找到每个与 他的下一个字符相同的字符,然后在这样一对字符中间加入一个与他们不相同的字符
如果找不到在第一个字符(除了最后一个的任意一个字符均可)后面输出与它不相同的字符即可

AC_CODE

#define pb push_back

#include <bits/stdc++.h>

#define rep(i, b, s) for(int i = (b); i <= (s); ++i)

using namespace std;

void solve() {

    int n, m; scanf("%d%d", &n, &m);

    string a; cin >> a;

    // 三种不可能构造出的情况

    if(n == 1 || n == m || n == 2 && a[0] != a[1]) {

        puts("-1");

        return;

    }

    //构造方式为找到每个与 他的下一个字符相同的字符,然后在这样一对字符中间加入一个与他们不相同的字符

    // 如果找不到在第一个字符(除了最后一个的任意一个字符均可)后面输出与它不相同的字符即可

    //寻找出 每个与 他的下一个字符相同的字符 存起来

    vector<int> v;

    for(int i = 0; a[i + 1]; i ++)

        if(a[i] == a[i + 1]) {

            v.pb(i);

        }

    int len = v.size();

    if(!len) { // 找不到的情况

        putchar(a[0]);

        for(int i = 0; i < m - n; i ++ ) putchar(a[0] ^ 1);

        rep(i, 1, n - 1) putchar(a[i]);

        puts("");

        return;

    }

    int p = 0;

    int ans = m - n;

    for(int i = 0; a[i]; i ++ ) { // 找到了这样的字符

        putchar(a[i]);

        if(i == v[p] && ans) {

            putchar(a[i] ^ 1);

            p ++; ans --;

            if(p == len) {

                rep(j, 1, ans) putchar(a[i] ^ 1);

                ans = 0;

            }

        }

    }

    puts("");

}

signed main()

{

    int T = 1;cin >> T;

    while(T -- ) solve();

    return 0;

}

巴特西

洛谷P7814 「小窝 R3」心の記憶

题意

分析

AC_CODE

最新文章

热门文章