3764. 三元数异或

如果一个整数，其各个数位不包含 0,1,2 以外的数字，则称这个数为三元数。

例如，1022,11,21,2002 都是三元数。

给定一个可能很长的三元数 x，其首位数字（最左边那位）保证为 2，其他位数字为 0 或 1 或 2。

我们规定，两个长度为 n 的三元数 a 和 b 可以通过三元异或运算 ⊙ 得到另一个长度为 n 的三元数 c。

设 ai,bi,ci 分别表示 a,b,c 的第 i 位的数字，则 ci=(ai+bi)mod3。

例如，10222 ⊙ 11021=21210。

你的任务是对于每个给定的 x，求出可以满足 a ⊙ b=x，并且 max(a,b) 尽可能小的 a,b。

注意，a,b 都必须是 n 位三元数，且不含前导 0。

输入格式
第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含整数 n，表示 x 的长度。

第二行包含一个长度为 n，首位为 2 的三元数 x。

输出格式
每组数据输出占两行，分别包含数 a 和数 b。

如果答案不唯一，则输出任意合理答案均可。

数据范围
1≤T≤104,
1≤n≤5×104,
同一测试点所有 n 的和不超过 5×104。

输入样例：
4
5
22222
5
21211
1
2
9
220222021
输出样例：
11111
11111
11000
10211
1
1
110111011
110111010
难度：中等
时/空限制：1s / 64MB
总通过数：972
总尝试数：1699
来源：CF1328C

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int T = sc.nextInt();while (T-- != 0) {int n = sc.nextInt();String s = sc.next();char[] ss = s.toCharArray();StringBuilder a = new StringBuilder();StringBuilder b = new StringBuilder();boolean flag = false;for (char c : ss) {if (c == '0') {a.append('0');b.append('0');} else if (c == '1') {if (flag) {a.append('0');b.append('1');} else {a.append('1');b.append('0');flag = true; // a>b的判断}} else {if (flag) {a.append('0');b.append('2');} else {a.append('1');b.append('1');}}} // forSystem.out.println(a.toString());System.out.println(b.toString());} // while} // main
}