1328C. C. Ternary XOR

\r\n

CF1328C. Ternary XOR

\n

时限: 1 秒 | 内存: 256 MB | 输入: 标准输入 | 输出: 标准输出

\r\n

如果一个数字只包含数字 $0$、$1$ 和 $2$，我们称其为三进制数。例如，以下数字都是三进制数：$1022$、$11$、$21$、$2002$。

\r\n

现在给你一个很长的三进制数 $x$。保证 $x$ 的首位（最左边一位）是 $2$，其余各位可以是 $0$、$1$ 或 $2$。

\r\n

我们定义两个长度为 $n$ 的三进制数 $a$ 和 $b$ 的三进制异或操作 $a \\odot b$，结果为长度为 $n$ 的三进制数 $c = a \\odot b$，其中 $c_i = (a_i + b_i) \\bmod 3$（即对应位相加后对 $3$ 取余）。例如，$10222 \\odot 11021 = 21210$。

\r\n

你的任务是找到两个长度为 $n$ 的三进制数 $a$ 和 $b$（都不能有前导零），使得 $a \\odot b = x$ 并且 $max(a, b)$ 尽可能小。

\r\n

你需要回答 $t$ 组独立的测试用例。

\r\n

输入格式

\r\n

输入的第一行包含一个整数 $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$）。

\r\n

输出格式

\r\n

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

\n

样例输入 1

\n

4\n5\n22222\n5\n21211\n1\n2\n9\n220222021

\n

样例输出 1

\n

11111\n11111\n11000\n10211\n1\n1\n110111011\n110111010

状态	递交者	时间	内存	语言	代码	递交时间
AC	Zcr_shi_RJ	86ms	916 KiB	C++20(O2)	723 Bytes	2026-8-14 17:41:21
AC	DaDaLin2014	96ms	1.1 MiB	C++20(O2)	605 Bytes	2026-8-12 19:50:46
AC	Morning_field	99ms	896 KiB	C++20(O2)	573 Bytes	2026-8-12 21:37:08
AC	汤音同	213ms	1.3 MiB	C++17(O2)	611 Bytes	2026-8-6 19:22:54

统计

递交统计

1328C. C. Ternary XOR

信息

还没有账户？

登录