CF1328C Ternary XOR

如果一个数字只包含数字 $0$、$1$ 和 $2$，我们称其为三进制数。例如，以下数字都是三进制数：$1022$、$11$、$21$、$2002$。 现在给你一个很长的三进制数 $x$。保证 $x$ 的首位（最左边一位）是 $2$，其余各位可以是 $0$、$1$ 或 $2$。 我们定义两个长度为 $n$ 的三进制数 $a$ 和 $b$ 的三进制异或操作 $a \odot b$，结果为长度为 $n$ 的三进制数 $c = a \odot b$，其中 $c_i = (a_i + b_i) \bmod 3$（即对应位相加后对 $3$ 取余）。例如，$10222 \odot 11021 = 21210$。 你的任务是找到两个长度为 $n$ 的三进制数 $a$ 和 $b$（都不能有前导零），使得 $a \odot b = x$ 并且 $max(a, b)$ 尽可能小。 你需要回答 $t$ 组独立的测试用例。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是 $t$ 组测试用例。每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 5 \times 10^4$），表示 $x$ 的长度。第二行包含一个长度为 $n$ 的三进制数 $x$，由 $n$ 个 $0$、$1$ 或 $2$ 组成。保证 $x$ 的首位为 $2$。保证所有测试用例中 $n$ 的总和不超过 $5 \times 10^4$（$\sum n \le 5 \times 10^4$）。

对于每组测试用例，输出一行答案——两个长度为 $n$ 的三进制整数 $a$ 和 $b$，都不能有前导零，满足 $a \odot b = x$ 且 $max(a, b)$ 尽可能小。如果有多组答案，输出任意一组均可。

由 ChatGPT 4.1 翻译