2021牛客暑期多校训练营4 C-LCS

本文主要是介绍2021牛客暑期多校训练营4 C-LCS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：https://ac.nowcoder.com/acm/contest/11255/C

思路：若A<=B<=C，则先三个串都加上A个’a’，然后s2和s3加上B-A个字母’b’，然后s1和s3加上C-A个字母’c’，就可以满足公共子序列个数的条件。之后在后面补’d’,‘e’,‘f’,直到长度到N。如果补之前长度超过N，就失败。
但是题目没有保证A<=B<=C，所以我们可以先建立映射关系，A映射s1,s2，B映射s2,s3，C映射s1,s3，所以我们可以将A,B,C重新排序后，按照映射关系进行操作，最后依此输出s1,s2,s3

#include <bits/stdc++.h>using namespace std;
struct node{int first,second;int val;
}a[4];
string s[4];
int cmp(node x,node y){return x.val<y.val;
}
int main()
{//cout << "Hello world!" << endl;int A,B,C,N;cin>>A>>B>>C>>N;a[1].val=A,a[1].first=1,a[1].second=2;a[2].val=B,a[2].first=2,a[2].second=3;a[3].val=C,a[3].first=3,a[3].second=1;sort(a+1,a+3+1,cmp);for(int i=1;i<=a[1].val;i++){for(int j=1;j<=3;j++){s[j]+='a';}}for(int i=1;i<=a[2].val-a[1].val;i++){int id1=a[2].first,id2=a[2].second;s[id1]=s[id1]+'b',s[id2]=s[id2]+'b';}for(int i=1;i<=a[3].val-a[1].val;i++){int id1=a[3].first,id2=a[3].second;s[id1]+='c',s[id2]+='c';}int flag=1;for(int i=1;i<=3;i++){if(s[i].size()>N)flag=0;for(int j=s[i].size();j<N;j++){s[i]+='d'+i;}}if(flag==0){cout<<"NO"<<endl;return 0;}for(int i=1;i<=3;i++){cout<<s[i]<<endl;}return 0;
}

这篇关于2021牛客暑期多校训练营4 C-LCS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---