codeforces1509 D. Binary Literature
题意：
给定三个长度为2 ∗ n字符串，要求构造一个长度小于等于3 ∗ n的字符串s 使得至少有两个字符串是s的子序列。
思路：
本来的思路是枚举两个字符串a , b，b中的0 / 1一定在a里出现过，只需要在a后面拼接上b剩下的部分就行。思路会忽略掉一些正确的情况。
由于给出的字符串只有0 , 1所以一定有两个字符串有长度大于n的全0或全1的公共子序列，只需要将字符串中非子序列的部分按次序插入到公共子序列当中就是答案。
感觉不好实现所以去看了题解的第二种思路。
还是由于给出的字符串只有0 , 1两种情况，所以考虑指针的写法：
p a , p b , p c分别指向字符串a , b , c每次比较任意两个，有相同字符则将该字符添加到结果字符串中，同时对应的指针往后移动。由于字符不是0就是1，所以一定会有两个相等。
直到有一个字符串全部被加到结果字符串里。（假设该字符串为a aa，结束的条件为p a > 2 ∗ n）
这时候结果字符串的长度为i d x，所有的指针至少移动了 2 ∗ i d x次。
假设p a指针移动了2*n次，所以剩下的p b , p c指针移动了2 ∗ ( i d x − n )次，也就是说肯定有一个指针至少移动了( i d x − n )次，把这个指针对应的字符串的剩余部分加到结果中即可。
添加的字符最多为2 ∗ n − ( i d x − n ) = 3 ∗ n − i d x
结果字符串的长度最多为i d x + 3 ∗ n − i d x = 3 n
还有个小细节：数组至少要开到3 e 5
代码：
如果用数组存的话，代码会简洁点，下面是我的垃圾代码
const int maxn =1e6+7; char a[maxn],b[maxn],c[maxn]; char s[maxn]; int main(){ int T=read; while(T--){ int n=read; cin>>a+1>>b+1>>c+1; int pa=1,pb=1,pc=1,idx=0; while(1){ if(a[pa]==b[pb]){ s[++idx]=a[pa]; pa++,pb++; if(pa>2*n||pb>2*n||pc>2*n) break; continue; } if(b[pb]==c[pc]){ s[++idx]=b[pb]; pb++,pc++; if(pa>2*n||pb>2*n||pc>2*n) break; continue; } if(a[pa]==c[pc]){ s[++idx]=a[pa]; pa++,pc++; if(pa>2*n||pb>2*n||pc>2*n) break; } } ///cout<<pa<<"*****"<<pb<<"****"<<pc<<endl; int t=idx-n; if(pa>2*n){ if(pb>t){ for(int i=pb;i<=2*n;i++) s[++idx]=b[i]; for(int i=1;i<=idx;i++) cout<<s[i]; puts(""); continue; } if(pc>t){ for(int i=pc;i<=2*n;i++) s[++idx]=c[i]; for(int i=1;i<=idx;i++) cout<<s[i]; puts(""); continue; } } if(pb>2*n){ if(pa>t){ for(int i=pa;i<=2*n;i++) s[++idx]=a[i]; for(int i=1;i<=idx;i++) cout<<s[i]; puts(""); continue; } if(pc>t){ for(int i=pc;i<=2*n;i++) s[++idx]=c[i]; for(int i=1;i<=idx;i++) cout<<s[i]; puts(""); continue; } } if(pc>2*n){ if(pb>t){ for(int i=pb;i<=2*n;i++) s[++idx]=b[i]; for(int i=1;i<=idx;i++) cout<<s[i]; puts(""); continue; } if(pa>t){ for(int i=pa;i<=2*n;i++) s[++idx]=a[i]; for(int i=1;i<=idx;i++) cout<<s[i]; puts(""); continue; } } } return 0; }
