Codeforces Round #715 Binary Literature

题意

给你三个长度为$2n$的01串。现在要你找到一个长度最长为$3n$的01串，使得至少有两个$2n$的01串是这个串的子序列。

就很简单可以证明，$3n$的串一定可以得到。

假设一个$2n$的串是00000，另一个是11111。于是我们可以立刻发现，第三个串无论怎么构造和前面两个串的差异的最大值就是$n$。于是公共部分一定可以拿出$n$个来，剩下小于等于$n$的差异直接补上去就完事。

如果直接按照这个思路裸着做，要求两个串的最长公共子序列，就很麻烦。于是注意到这是一个01串。那么对于一个串，要么0多，要么1多。

我们就假设0多好了。既然是0多，那么我们把小于等于$n$的1，直接各自往里面插入不就好了。

比如001100和010100。首先搞出四个0。得到0000。然后把001100的1插进去就得到001100。再把010100的1插进去得到01011100。