题目描述

位串是仅包含字符0和1的字符串。

卡努晃（Koyomi Kanou）致力于实现自己成为作家的梦想。 为了练习，她决定参加二进制小说写作比赛。 比赛的写作提示由三个长度为2n的位串组成。 一本竞赛有效的小说是一个长度最大为3n的位串，其中至少包含三个给定字符串中的两个作为子序列。

Koyomi刚从比赛组织者那里收到了三个提示字符串。 帮助她为比赛写一部有效的小说。

如果可以通过删除几个（可能为零）字符从b获得a，则字符串a是字符串b的子序列。

样例

2
1
00
11
01
3
011001
111010
010001

output
010
011001010

算法1

(双指针+鸽巢原理) $O(n)$

鸽巢原理也叫抽屉原理,首先这题的字符串是由0和1组成的,而长度又是2n,
如果一个01字符串的长度为2n,那么0或1中有一个的长度>=n,三个字符串也
就是说有三个0或1的长度>=n,二次鸽巢原理,也就是说至少有两个字符串>=n的
字符(0 or 1)一致,找到这样的满足条件的两个字符串就好了

C++ 代码

/*
    鸽巢原理:也是抽屉原理,首先要使得3*n中含有两个子序列,则必然公共
    子序列大于等于n,如果公共的子序列小于等于n:c
    当3*n字符串在位置的时候已经扫完了某个字符串2*n:a,然后对于另一个字符串b
    它至少也就扫描了公共子序列,假设另一个字符串就前面的全是公共子序列,那么它还有
    2*n-c>n也就是说还要补大于n个字符,这样必然最终的ans>3*n,不满足条件
*/
#include<bits/stdc++.h>
using namespace std;
const int N =1e5+10;

void solve()
{
    string str[3];
    int cnt0[3]={0};
    int n;

    scanf("%d", &n);

    for(int i=0;i<3;i++)
    {
        cin>>str[i];
        for(int j=0;j<n*2;j++)  if(str[i][j]=='0')  cnt0[i]++;//记录0的个数
    }
    string ans="";
    int flag=0;
    for(int i=0;i<3;i++)
        for(int j=i+1;j<3;j++)
        { 
            char key;
            if(min(cnt0[i],cnt0[j])<n&&max(cnt0[i],cnt0[j])>n)  continue;//>n的不一致

            if(min(cnt0[i],cnt0[j])>=n) key='0';
            if(max(cnt0[i],cnt0[j])<=n)  key='1';//这里要记住等于woc
            flag=1;

            int pi=0,pj=0;

            while(pi<2*n&&pj<2*n)
            {
                if(str[i][pi]==key&&str[j][pj]==key)
                {
                    ans+=str[i][pi],pi++,pj++;
                }
                else if(str[i][pi]==key)
                {
                    ans+=str[j][pj],pj++;
                }
                else
                {
                    ans+=str[i][pi],pi++;
                }
            }


            while(pi<2*n)
            {
                ans+=str[i][pi],pi++;
            }

            while(pj<2*n)
            {
                ans+=str[j][pj],pj++;
            }
            if(flag)    
            {
                cout<<ans<<endl;
                return;
            }
        }

}



int main()
{
    int t;
    scanf("%d", &t);
    while(t--)  solve();
    return 0;
}