The Solution of string

problem
外网

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

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

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

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

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

进一步，我们就能推出：

part 2，贪心

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

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;
}

注意到2的偶数次幂模3为2,2的奇数次幂模3为1

记在偶数位上的1的个数为x,奇数位上的1的个数为y

若要使该数被3整除，需满足x=y或|x-y|=3 因为（1+2）%3=0，1x3%3=0,2x3%3=0; 故当n<=1时无解

故当n%2=0时 字典序最大为1全放在前，0全方在后 字典序最小时，当m%2=时，第一位为1，0全放在前，1全方在后，当m%2!=0时，即最后连续的1的第一个的位数的奇偶与第以为的1相同时，使得|x-y|=2,故需要在最后的连续的1的第一个1后补0，使|x-y|=3

当n%2==0时 则只能满足|x-y|=3,那么至少需要2个0来填位若没有则无解 字典序最大为1放在前，最后为0101，后添加0 字典序最小时考虑m的奇偶决定连续的1前为0101还是1010来保证|x-y|=3

本文由GPT5.6撰写

题解

设二进制数为：

因为

所以这个数除以 3 的余数等于：

因此问题变成：

让奇数位置的 1 数量 − 偶数位置的 1 数量是 3 的倍数。

贪心

我们从左往右确定每一位。

• 求字典序最大：优先尝试放 1
• 求字典序最小：优先尝试放 0
• 第一位不能放 0

假设当前尝试放了 x，那么剩下 r 个 1。

设剩下有 O 个奇数位置、E 个偶数位置。

如果剩余的 1 中有 y 个放在奇数位置，那么：

个放在偶数位置，所以剩余贡献为：

其中：

我们只需要判断这个区间里是否存在一个 y，使最终的：

因为只看模 3，所以实际上只需要检查最多 3 个 y。

复杂度

每个位置只尝试 0/1 两种情况，每次判断 O(1)。

所以：

空间复杂度：

核心代码

string work(int big){
    int N=n+m,one=n,sum=0;
    string s;
    for(int i=1;i<=N;i++){
        int O=(N+1)/2-(i&1),E=N/2-!(i&1);
        for(int x=big;x>=0;x--){
            if((i==1&&x==0)||x>one) continue;
            int r=one-x;
            if(r>O+E) continue;
            int l=max(0,r-E),R=min(r,O);
            int t=(sum+(x?(i&1?1:-1):0))%3;
            if(t<0)t+=3;
            bool ok=0;
            for(int y=l;y<=min(R,l+2);y++)
                if((t+2*y-r)%3==0) ok=1;
            if(ok){
                s+=x+'0';
                one-=x;
                if(x) sum+=i&1?1:-1;
                break;
            }
        }
    }
    return one||sum%3?"-1":s;
}

一句话总结：利用 2≡-1 (mod 3) 把整串转成奇偶位置计数，然后从左到右贪心，每次判断剩余的 1 能否补出模 3 的合法方案。

本文章由GPT5.6-Thinking撰写

https://chatgpt.com/share/6aaa5efd-e9c0-83ec-8c7a-a89e286ac975

思路

设二进制串长度为 (L=n+m)。

二进制数除以 (3) 时，因为

所以只需要看 从右往左奇偶位置上的 1 的数量。

设其中有 (x) 个 1 位于偶数次幂的位置（也就是从右往左第 (1,3,5,\dots) 位），那么

因此必须满足

于是问题变成：

在固定的 n 个 1、m 个 0 下，让“奇数编号位置上的 1 的数量”模 3 等于 2n mod 3，然后贪心构造字典序最大/最小。

贪心

从左到右枚举每一位。

构造最大串时优先放 1；构造最小串时优先放 0。

尝试放完以后，只要判断剩下的位置能不能把条件补齐即可。

假设还剩：

• a 个 1
• O 个“从右往左奇数位置”
• E 个“从右往左偶数位置”
• 当前已经用了 c 个奇数位置上的 1

设剩下还要在奇数位置放 y 个 1。

显然：

同时需要

所以只要看这个区间里有没有对应模 3 的数即可，O(1) 判断。

第一位强制放 1，避免前导 0。

总复杂度为 O(n+m)，空间 O(n+m)。

C++14

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

#define int long long

bool solve(int n,int m,bool mx,string &s){
    int L=n+m;
    int O=(L+1)/2,E=L/2;
    int target=2*n%3;
    int one=n,zero=m,c=0;
    s="";

    for(int i=1;i<=L;i++){
        bool odd=((L-i)%2==0);
        int first=mx?1:0,second=mx?0:1;

        int choose=-1;
        for(int t=0;t<2;t++){
            int b=(t==0?first:second);
            if(i==1&&b==0) continue;
            if(b==1&&one==0) continue;
            if(b==0&&zero==0) continue;

            int no=O,ne=E,n1=one,nc=c;
            if(odd) no--;
            else ne--;

            if(b==1){
                n1--;
                if(odd) nc++;
            }

            int lo=max(0LL,n1-ne);
            int hi=min(n1,no);
            int need=(target-nc+3)%3;
            int x=lo+(need-lo%3+3)%3;

            if(x<=hi){
                choose=b;
                break;
            }
        }

        if(choose==-1) return false;

        s+=char('0'+choose);
        if(odd) O--;
        else E--;

        if(choose==1){
            one--;
            if(odd) c++;
        }else zero--;
    }

    return true;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin>>T;

    while(T--){
        int n,m;
        cin>>n>>m;

        string mx,mn;
        bool a=solve(n,m,1,mx);
        bool b=solve(n,m,0,mn);

        if(!a||!b){
            cout<<-1<<"\n"<<-1<<"\n";
        }else{
            cout<<mx<<"\n"<<mn<<"\n";
        }
    }
    return 0;
}

例如 n=5,m=5，程序会得到：

1110101000
1000101011

和样例一致。