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。

代码

Submission #113288524 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论