The Solution of string

problem
外网

part 1, 二进制被 $3$ 整除转化

我们知道，十进制 $3$ 的整除性是 各个数位相加的和是 3 的倍数，原理是因为 $10^k \equiv 1 \pmod{3}$，所以

$$num=a_k \times 10^k + a_{k-1} \times 10^{k-1} + \dots + a_0 \times 10^0 \equiv a_k + a_{k-1} + \dots + a_0 \pmod{3}$$

二进制呢，我们可以列出 $2$ 的幂次除以 $3$ 的余数表

幂次	$0$	$1$	$2$	$3$	$4$	$5$	$\dots$
余数	$1$	$2$	$1$	$2$	$1$	$2$	$\dots$

当 $k$ 是奇数时，$2^k \equiv 2 \pmod{3}$；
当 $k$ 是偶数时，$2^k \equiv 1 \pmod{3}$；

所以: 对于奇数位，对余数的贡献是 $2$; 对于偶数位，对余数的贡献是 $1$.

进一步，我们就能推出：

$$C_{odd} \equiv C_{even} \pmod{3}$$

part 2，贪心

对于最大值，肯定是越是填 $1$，越好，反之同理。那么问题就在与我们填了 $1$ 或 $0$ 之后可不可能填出 $3$ 的倍数，如果可以就填，否则就填另一个。
那么怎么判定呢，就用到了 part $1$ 的结论：

$$C_{odd} \equiv C_{even} \pmod{3}$$

part 3, check

现在问题就在于，还剩 $cnt_1$ 个 $1$，$cnt_0$ 个 $0$，令 $lft = \frac{cnt_0 + cnt_1}{2}$，奇数位和偶数位差为 $d$，问此时可不可以。
我们不妨假设奇数位数量与偶数位数量相同（如果不同就枚举当前位填什么），奇数位与偶数位的差为 $0$ 或 $1$（如果是多 $2$，就可以改成少 $1$）。
此时开始分类讨论：

1. 奇数位和偶数位差为 $0$，$cnt_1$ 为偶数，则一定可以，将 $cnt_1$ 分成两份：奇偶各一份就行。
2. 奇数位和偶数位差为 $0$，$cnt_1$ 为奇数，则拿出三个放偶数，再平均分，判断偶数位够不够，此时 $cnt_1 \ge 3$ 且 $\frac{cnt_1 - 3}{2} + 3 \le lft$
3. 奇数位和偶数位差为 $1$，$cnt_1$ 为奇数，则拿出一个放偶数，再平均分，判断偶数位够不够，此时 $cnt_1 \ge 1$ 且 $\frac{cnt_1 - 1}{2} + 1 \le lft$
4. 奇数位和偶数位差为 $1$，$cnt_1$ 为偶数，则拿出两个放偶数，再平均分，判断偶数位够不够，此时 $cnt_1 \ge 2$ 且 $\frac{cnt_1 - 2}{2} + 2 \le lft$

（代码中会将这些式子变形，应该能理解）

part 4, 代码

#include <bits/stdc++.h>
using namespace std;

int T, n, m;

bool check(int one, int zero, int d) {
	int lft = one + zero;
	if (lft & 1) return one && check(one - 1, zero, (d + 2) % 3)
		|| zero && check(one, zero - 1, d);
	if (!d)
		if (one & 1) return one >= 3 && ((one + 3) >> 1) <= (lft >> 1);
		else return 1;
	else if (one & 1) return one >= 1 && ((one + 1) >> 1) <= (lft >> 1);
	else return one && (one >> 1) + 1 <= (lft >> 1);
}

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);
		int one = n - 1, zero = m, d = (((n + m - 1) & 1) ? 1 : 2);
		// max
		if (!check(n - 1, m, 1)) { puts("-1\n-1"); continue; }
        printf("1");
		for (int i = 2; i <= n + m; i++) {
			int pos = n + m - i, nxt = ((pos & 1) ? (d + 1) % 3 : (d + 2) % 3);
			if (one && check(one - 1, zero, nxt)) d = nxt, --one, printf("1");
			else --zero, printf("0");
		} puts("");
		// min
        printf("1");
		one = n - 1, zero = m, d = (((n + m - 1) & 1) ? 1 : 2);
		for (int i = 2; i <= n + m; i++) {
			int pos = n + m - i, nxt = ((pos & 1) ? (d + 1) % 3 : (d + 2) % 3);
			if (zero && check(one, zero - 1, d)) --zero, printf("0");
			else --one, d = nxt, printf("1");
		} puts("");
	}
	return 0;
}