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);
    }
}