题目概述
有三个长度为$2n$的01串，现在要求构造一个长度不超过$3n$的01串，使得所给的三个01串中至少两个是该构造串的子序列。
分析与解
这个题的关键在于怎么处理3和2的关系。
一个正确的思路是尽量用串与串之间公共的子序列来节省构造的位置。一个错误的方向是从三个串两两考虑来验证能否构造。
为什么是错误的方向？如果是这么做，为什么是给三个串而不是四个、五个串？为什么最后构造长度要求$3n$不是其他量？
这个3是有原因的。
首先说一说证明上的可行性。
根据抽屉原理，长度为$2n$的01串，至少有一种数码出现不少于$n$次。而再根据抽屉原理，三个串的这种数码必然有两个串的是一样的。
也就是说，最终的串必然有$00…0$或$11…1$的子序列，长度至少为$n$.而包含两个串作为子序列的答案串长度$L \leq |s|+|t|-lcs \leq4n-n=3n$因此构造是一定可行的。
再说具体的构造方法。其实还是抽屉原理。
我们不妨用三个指针来考虑三个给定的01串。那么这三个指针指向的字符，必然有一个是在两个串上都出现的（因为只有01两种字符），把它放到答案中，移动指针。那么一直移动下去必然有一个时刻某个串全部包含在了答案中。记此时答案串已有字符$k$个，这说明三个指针至少移动了$2k$次，那么对于剩下两个没有完全包含的01串，已经移动了$2k-2n$次，再利用抽屉原理，必然有一个串的指针至少移动了$k-n$次。现在把这个串的剩余部分全放到答案中。这么做之所以可行，是因为$2n-(k-n)=3n-k$.
P.S. 这种抽屉原理套抽屉原理让我回想起当年高三做北京高考数学最后一题的情形。（归根结底还是不会呀（逃））
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| #include <bits/stdc++.h>
using namespace std;
#define min(a,b) (a)<(b) ? (a) : (b)
#define max(a,b) (a)>(b) ? (a) : (b)
typedef long long LL;
int mread() {
int ret=0,f=1;
char c=getchar();
while(c<'0' || c>'9') {
if(c=='-')f=-1;
c=getchar();
}
do {
ret=ret*10+c-'0';
c=getchar();
} while('0'<=c && c<='9');
return ret*f;
}
#define MAXN 100100
char a[MAXN<<1],b[MAXN<<1],c[MAXN<<1];
char output[MAXN<<2];
int n;
int main() {
int sig;
int kase;
kase=mread();
int i,j,k,now;
while(kase--) {
n=mread();
scanf("%s",a+1);
scanf("%s",b+1);
scanf("%s",c+1);
now=i=j=k=1;
while(i<=2*n && j<=2*n && k<=2*n) {
if(a[i]==b[j]) {
output[now++]=a[i];
i++,j++;
} else if(a[i]==c[k]) {
output[now++]=a[i];
i++,k++;
} else if(b[j]==c[k]) {
output[now++]=b[j];
j++,k++;
}
if(i>2*n) {
sig=1;
break;
} else if(j>2*n) {
sig=2;
break;
} else if(k>2*n) {
sig=3;
break;
}
}
if(sig==1) {
if(j>=now-n)
while(j<=2*n)
output[now++]=b[j++];
else if(k>=now-n)
while(k<=2*n)
output[now++]=c[k++];
} else if(sig==2) {
if(i>=now-n)
while(i<=2*n)
output[now++]=a[i++];
else if(k>=now-n)
while(k<=2*n)
output[now++]=c[k++];
} else if(sig==3) {
if(i>=now-n)
while(i<=2*n)
output[now++]=a[i++];
else if(j>=now-n)
while(j<=2*n)
output[now++]=b[j++];
}
output[now]='\0';
printf("%s\n",output+1);
}
return 0;
}
|