链接
https://codeforces.com/contest/1509/problem/d
题意
三个长度为 $2n$ 的 $01$ 字符串 $a,b,c$，构造一个长度不超过 $3n$ 的 $01$ 字符串 $T$ 至少 $a,b,c$ 中两个是 $T$ 的子序列。
思路
建立三个指针分别对 $a,b,c$ 从左向右扫描。
每次至少有两个字符相同，输出当前字符，将两个指针向右移动，直到一个字符串被扫描完。
设当前已经输出 $k$ 个字符，总共移动 $2k$ 次，有一个字符串被扫描完，移动 $2n$ 次，那么剩下两个字符串移动 $2k-2n$ 次，平均 $k-n$ 次，最多剩下 $2n-(k-n)$ 个字符未添加，选最优的输出剩余部分。
总共最多 $2n+(2n-(k-n))=5n-k$ 个字符，因为 $k>=2n$ 所以肯定不超过 $3n$。
代码
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
| #include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;cin>>T;
while(T--) {
int n;cin>>n;
string a,b,c;cin>>a>>b>>c;
int aa=0,bb=0,cc=0;
while(aa<2*n&&bb<2*n&&cc<2*n) {
if(a[aa]==b[bb]) cout<<a[aa],++aa,++bb;
else if(a[aa]==c[cc]) cout<<a[aa],++aa,++cc;
else if(b[bb]==c[cc]) cout<<b[bb],++bb,++cc;
}
if(aa==2*n) cout<<(bb>cc?b.substr(bb,2*n-bb):c.substr(cc,2*n-cc))<<'\n';
else if(bb==2*n) cout<<(aa>cc?a.substr(aa,2*n-aa):c.substr(cc,2*n-cc))<<'\n';
else if(cc==2*n) cout<<(aa>bb?a.substr(aa,2*n-aa):b.substr(bb,2*n-bb))<<'\n';
}
return 0;
}
|