CF1474A Puzzle From the Future

对于两个长度为 $n$ 的二进制整数 $a$,$b$，通过以下方式构造出整数 $d$： 1. 将 $a$ 和 $b$ 按位相加但不进行进位运算，得到一个整数 $c$，因此 $c$ 中可能有 $2$。例如将 $0110$ 与 $1101$ 按位相加的结果是 $1211$。 2. 将 $c$ 中相同且连续的数字替换为一位，得到 $d$。例如将 $022000$ 变成 $020$（因此，$d$ 没有相同且连续的数字）。 现在，给你 $b$，求一个 $a$ 使得 $d$ 最大。

第一行为测试数据组数 $t(1 \leq t \leq 1000)$ 每个测试数据包含两行。 第一行为一个整数 $n(1 \leq n \leq 10^5)$，表示二进制数 $a$,$b$ 的长度。 第二行一个长度为 $n$ 的二进制整数 $b$。

对于每一个测试数据，输出一个长度为 $n$ 的二进制整数 $a$，使得通过 $a$,$b$ 构造出的整数 $d$ 最大。 by uid=390770

In the first test case, $ b = 0 $ and choosing $ a = 1 $ gives $ d = 1 $ as a result. In the second test case, $ b = 011 $ so: - if you choose $ a = 000 $ , $ c $ will be equal to $ 011 $ , so $ d = 01 $ ; - if you choose $ a = 111 $ , $ c $ will be equal to $ 122 $ , so $ d = 12 $ ; - if you choose $ a = 010 $ , you'll get $ d = 021 $ . - If you select $ a = 110 $ , you'll get $ d = 121 $ . We can show that answer $ a = 110 $ is optimal and $ d = 121 $ is maximum possible.In the third test case, $ b = 110 $ . If you choose $ a = 100 $ , you'll get $ d = 210 $ and it's the maximum possible $ d $ . In the fourth test case, $ b = 111000 $ . If you choose $ a = 101101 $ , you'll get $ d = 212101 $ and it's maximum possible $ d $ . In the fifth test case, $ b = 001011 $ . If you choose $ a = 101110 $ , you'll get $ d = 102121 $ and it's maximum possible $ d $ .