陕西做网站公司有哪些,西宁网站建设报价cu君博規范,沙河企业做网站,手机网站建设效果LCS(2021牛客多校4)
题意#xff1a;
让你构造三个字符串s1,s2,s3#xff0c;长度均为n,要求LCS(s1,s2)a,LCS(s2,s3)b,LCS(s1,s3)c
题解#xff1a;
先考虑三个串互相LCS为x,y,z,且xyz 显然如果xy-nz则无解#xff0c;反之xy-nz有解 那么就先给三个串加…LCS(2021牛客多校4)
题意
让你构造三个字符串s1,s2,s3长度均为n,要求LCS(s1,s2)a,LCS(s2,s3)b,LCS(s1,s3)c
题解
先考虑三个串互相LCS为x,y,z,且xyz 显然如果xy-nz则无解反之xy-nz有解 那么就先给三个串加上一个z个a的前缀然后就变成了x-zy-z0n-z的问题 因为xy-nz,所以(x-z)(y-z)n-z,所以给前两个串一起放上x-z个b后两个串放上y-z个c即可
代码
#includestdio.h
#includecstring
#includealgorithm
#includevector
#includemap
#includeassert.h
#includeset
#includecmath
#includequeue
#includecstdlib
#includeiostream
#includebitset
#define pii pairint,int
#define fi first
#define se second
#define pb push_back
#define rep(i,j,k) for(int i(int)(j);i(int)(k);i)
#define per(i,j,k) for(int i(int)(j);i(int)(k);i--)
using namespace std;
typedef long long LL;
typedef double db;
const int N1005;
int n,a,b,c;
char x[N],y[N],z[N];
void work(int a,int b,int c){rep(i,1,c)x[i]y[i]z[i]a;a-c;b-c;rep(i,c1,ca){x[i]b;y[i]b;z[i]q;}rep(i,ca1,cab){x[i]p;y[i]c;z[i]c;}rep(i,cab1,n){x[i]x;y[i]y;z[i]z;}
}
void opt(char *a,char *b,char *c){rep(i,1,n)putchar(a[i]);puts();rep(i,1,n)putchar(b[i]);puts();rep(i,1,n)putchar(c[i]);puts();
}
int main(){scanf(%d%d%d%d,a,b,c,n);if(cab-n||abc-n||bac-n){puts(NO);return 0;}if(cacb){work(a,b,c);opt(x,y,z);}else if(acab){work(b,c,a);opt(z,x,y);}else{work(a,c,b);opt(y,x,z);}return 0;
}
