题面:已知三个串的LCS和总长n,构造这三个串。
解析:临界条件是出现了三个串的公共部分,设公共部分为mi,则
(a-mi)+(b-mi)+(c-mi)+mi>=n
在条件以内,就一定可以构造三个串的公共部分。
细节见代码:
#include<bits/stdc++.h> using namespace std; int n,a,b,c; int main(){ cin>>a>>b>>c>>n; int mi=min(min(a,b),c);//公共部分长度 a-=mi,b-=mi,c-=mi; if(a+b+c+mi>n) cout<<"NO"<<endl; else{ string s1(mi,'a'),s2(mi,'a'),s3(mi,'a');//公共部分用a填充。 //两两之间的公共部分分别用b,c,d填充。 for(int i=1;i<=a;i++) s1+='b',s2+='b'; for(int i=1;i<=b;i++) s2+='c',s3+='c'; for(int i=1;i<=c;i++) s1+='d',s3+='d'; //填充剩余部分至长度为n while(s1.size()<n) s1+='x'; while(s2.size()<n) s2+='y'; while(s3.size()<n) s3+='z'; cout<<s1<<endl; cout<<s2 <<endl; cout<<s3<<endl; } }