2021牛客多校4 C - LCS （构造）

本文主要是介绍2021牛客多校4 C - LCS （构造），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

构造字符串s1,s2,s3使得LCS(s1,s2)=a，LCS（s2,s3）=b,LCS（s3,s1）=c

我们先令minn为a,b,c三者中最小的，将s1,s2,s3用字符'a'填充至minn长度

然后再依次满足a,b,c三种条件，分别用字符'b''c''d'填充a-minn,b-minn,c-minn次

此时消耗最少字符满足上述三种条件，如果此时的s1,s2,s3中有一个长度超过了n，那么三种字符串不可能被构造，输出NO

然后随便使用三种不同的字符填充s1,s2,s3剩余空位至n即可

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

int a,b,c,n;
int minn=0x3f3f3f3f;
char s1[10010];
char s2[10010];
char s3[10010];
int len1,len2,len3;

int main(){
    scanf("%d%d%d%d",&a,&b,&c,&n);
    minn=min(c,min(a,b));
    for(int i=1;i<=minn;i++)
    {
        s1[++len1]='a';
        s2[++len2]='a';
        s3[++len3]='a';
    }
    for(int i=1;i<=(a-minn);i++)
    {
        s1[++len1]='b';
        s2[++len2]='b';
    }
    for(int i=1;i<=(b-minn);i++)
    {
        s2[++len2]='c';
        s3[++len3]='c';
    }
    for(int i=1;i<=(c-minn);i++)
    {
        s3[++len3]='d';
        s1[++len1]='d';
    }
    while(len1<n)
    {
        s1[++len1]='x';
    }
    while(len2<n)
    {
        s2[++len2]='y'; 
    }
    while(len3<n)
    {
        s3[++len3]='z';
    }
    if(len1==n&&len2==n&&len3==n)
    {
        cout<<s1+1<<endl<<s2+1<<endl<<s3+1<<endl;
    }
    else cout<<"NO";
    return 0;
}

这篇关于2021牛客多校4 C - LCS （构造）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！