AT_agc052_a [AGC052A] Long Common Subsequence

题目描述

给你三个 01 字符串 $S_1,S_2,S_3$,其中每一个都含有 $N$ 个 `0` 和 $N$ 个 `1`。 找到一个同时是 $S_1+S_1,S_2+S_2,S_3+S_3$($s+t$ 表示将 $s$ 和 $t$ 按顺序拼接而成的字符串)的子序列的长度为 $2N+1$ 的 01 字符串。保证在本题的数据范围内总存在一个这样的序列。 $B$ 是 $A$ 的子序列当且仅当 $B$ 可以通过删除 $A$ 零个或更多个字符并将剩余字符在不改变顺序的前提下拼接在一起得到。 多组数据。

输入格式

第一行一个整数 $T$,表示数据组数。 对于每组数据,第一行一个整数 $N$。 第二行一个字符串 $S_1$。 第三行一个字符串 $S_2$。 第四行一个字符串 $S_3$。

输出格式

对于每组数据,输出一行一个长度为 $2N+1$ 的 01 字符串,是 $S_1+S_1,S_2+S_2,S_3+S_3$ 的子序列。如果存在多种解,输出任意一种均可。

说明/提示

**数据范围** - $1\le T\le 10^5$ - $1\le N\le 10^5$ - $S_i$ 是一个长度为 $2N$ 的 01 字符串,包含 $N$ 个 `0` 和 $N$ 个 `1`。 - 单个测试点内 $N$ 的和不超过 $10^5$。