Codeforces Round #715 (Div. 2) D. Binary Literature(構造)

題意：

給出三個長度為 2 n 2n 2n 的01串，要求構造一個長度不大于 3 n 3n 3n 的01串，使得至少有兩個原始01串為構造串的子序列。保證答案存在。

題解：

設三個指針來标記這三個串目前已經滿足的部分。 p o s 1 pos1 pos1表示串1前 p o s 1 − 1 pos1-1 pos1−1個字元已經是構造串的子序列， p o s 2 pos2 pos2， p o s 3 pos3 pos3

以此類推。

可以發現，目前這三個位置至少有兩個位置字元是相等的,那就把相等的字元加入到構造串中。

假設 s [ 1 ] [ p o s 1 ] = = s [ 2 ] [ p o s 2 ] s[1][pos1]==s[2][pos2] s[1][pos1]==s[2][pos2] ,那麼就将 s [ 1 ] [ p o s 1 ] s[1][pos1] s[1][pos1] 加入到構造串當中，然後 p o s 1 + + , p o s 2 + + pos1++,pos2++ pos1++,pos2++ 。

直到其中一個串已經周遊完，然後再将剩下兩個中 p o s pos pos大的加入到答案中即可。

證明：

當其中一個串已經周遊完時，假設此時構造串的長度為 x x x ，那麼 x ≥ 2 n x \geq 2n x≥2n , 其中 x − 2 n x-2n x−2n 個字元是來自其他的字元串，因為有一個串被周遊完，并且每次都是兩個位置++，根據均攤原理，另外兩個串的最大的 p o s pos pos 肯定 ≥ n \geq n ≥n , 再加上 x − 2 n x-2n x−2n，

那麼 p o s ≥ x − n pos \geq x-n pos≥x−n 那麼剩餘的長度 r e s ≤ 2 n − ( x − n ) = 3 n − x res \leq 2n-(x-n)=3n-x res≤2n−(x−n)=3n−x ,那麼把這剩餘的放到答案中，就滿足 r e s + x ≤ 3 n res+x \leq 3n res+x≤3n

代碼：

#pragma GCC diagnostic error "-std=c++11"
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<ctime>
#define iss ios::sync_with_stdio(false)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
const int mod=1e9+7;
const int MAXN=2e5+5;
const int inf=0x3f3f3f3f;
char s[5][MAXN];
std::vector<char> v;
void solve(int n)
{
    v.clear();
    int pos1=1,pos2=1,pos3=1;
    while(pos1<=2*n&&pos2<=2*n&&pos3<=2*n)
    {
        //cout<<s[1][pos1]<<" "<<s[2][pos2]<<" "<<s[3][pos3]<<endl;
        if(s[1][pos1]==s[2][pos2])
        {
            v.push_back(s[1][pos1]);
            pos1++;
            pos2++;
        }
        else if(s[1][pos1]==s[3][pos3])
        {
            v.push_back(s[1][pos1]);
            pos1++;
            pos3++;
        }
        else
        {
            v.push_back(s[2][pos2]);
            pos2++;
            pos3++;
        }
    }
    if(pos1>=min(pos2,pos3)&&pos1<=max(pos2,pos3))
    {
        for(int i=pos1;i<=2*n;i++)
        {
            v.push_back(s[1][i]);
        }
    }
    else if(pos2>=min(pos1,pos3)&&pos2<=max(pos1,pos3))
    {
        for(int i=pos2;i<=2*n;i++)
        {
            v.push_back(s[2][i]);
        }
    }
    else if(pos3>=min(pos1,pos2)&&pos3<=max(pos1,pos2))
    {
        for(int i=pos3;i<=2*n;i++)
        {
            v.push_back(s[3][i]);
        }
    }
    for(auto i:v)
    {
        printf("%c",i);
    }
    printf("\n");
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=3;i++)
        {
            cin>>s[i]+1;
        }
        solve(n);
    }
}