题意:给你三个长度为\(2n\)的01串,要你构造出一个长度为\(3n\)的字符串\(s\),使得\(s\)的两个子序列至少包含两个给出的01串.

题解:因为给出的字符串长度为\(2n\)且为01串,那么某一个串包含的\(0\)或\(1\)的个数必然不小于0,那么我们可以找到两个\(0\)的个数或\(1\)的个数不小于0的串,拿出\(n\)个\(0\)或\(1\)当作公共子序列,然后再把它们剩下的字符按位置插入即可构造出答案,长度为\(4n-n=3n\).

代码:

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

int n;

string construct(string a,string b,char c){
	vector<int> v1,v2;
	v1.pb(-1),v2.pb(-1);
	rep(i,0,2*n-1){
		if(a[i]==c) v1.pb(i);
		if(b[i]==c) v2.pb(i);
	}
	string ans;
	rep(i,0,n-1){
		for(int j=v1[i]+1;j<v1[i+1];++j){
			ans.pb(a[j]);
		}
		for(int j=v2[i]+1;j<v2[i+1];++j){
			ans.pb(b[j]);
		}
		ans.pb(c);
	}
	for(int j=v1[n]+1;j<2*n;++j){
		ans.pb(a[j]);
	}
	for(int j=v2[n]+1;j<2*n;++j){
		ans.pb(b[j]);
	}
	return ans;
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int _;
	cin>>_;
	while(_--){
		cin>>n;
		string s[3];
		vector<string> s0,s1;
		rep(i,0,2){
			cin>>s[i];
			int cnt0=0;
			for(auto w:s[i]){
				if(w=='0') cnt0++;
			}
			if(cnt0>=n) s0.pb(s[i]);
			else s1.pb(s[i]);
		}
		string ans;
		if((int)s0.size()>=2){
			ans=construct(s0[0],s0[1],'0');
		}
		else ans=construct(s1[0],s1[1],'1');
		
		cout<<ans<<'\n';

	}
	

    return 0;
}