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 $ 2022 $ year, Mike found two binary integers $ a $ and $ b $ of length $ n $ (both of them are written only by digits $ 0 $ and $ 1 $ ) that can have leading zeroes. In order not to forget them, he wanted to construct integer $ d $ in the following way: - he creates an integer $ c $ as a result of bitwise summing of $ a $ and $ b $ without transferring carry, so $ c $ may have one or more $ 2 $ -s. For example, the result of bitwise summing of $ 0110 $ and $ 1101 $ is $ 1211 $ or the sum of $ 011000 $ and $ 011000 $ is $ 022000 $ ; - after that Mike replaces equal consecutive digits in $ c $ by one digit, thus getting $ d $ . In the cases above after this operation, $ 1211 $ becomes $ 121 $ and $ 022000 $ becomes $ 020 $ (so, $ d $ won't have equal consecutive digits). Unfortunately, Mike lost integer $ a $ before he could calculate $ d $ himself. Now, to cheer him up, you want to find any binary integer $ a $ of length $ n $ such that $ d $ will be maximum possible as integer. Maximum possible as integer means that $ 102 > 21 $ , $ 012 < 101 $ , $ 021 = 21 $ and so on.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases. The first line of each test case contains the integer $ n $ ( $ 1 \leq n \leq 10^5 $ ) — the length of $ a $ and $ b $ . The second line of each test case contains binary integer $ b $ of length $ n $ . The integer $ b $ consists only of digits $ 0 $ and $ 1 $ . It is guaranteed that the total sum of $ n $ over all $ t $ test cases doesn't exceed $ 10^5 $ .

输出格式

For each test case output one binary integer $ a $ of length $ n $ . Note, that $ a $ or $ b $ may have leading zeroes but must have the same length $ n $ .

输入输出样例

输入样例 #1

5
1
0
3
011
3
110
6
111000
6
001011

输出样例 #1

1
110
100
101101
101110

说明

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 $ .