本文章由GPT5.6-Thinking撰写

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

思路

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

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

$$2^0\equiv1,\quad 2^1\equiv-1,\quad 2^2\equiv1,\quad 2^3\equiv-1\pmod 3$$

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

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

$$num\equiv x-(n-x)=2x-n\pmod3$$

因此必须满足

$$x\equiv 2n\pmod3$$

于是问题变成：

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

贪心

从左到右枚举每一位。

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

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

假设还剩：

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

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

显然：

$$\max(0,a-E)\le y\le\min(a,O)$$

同时需要

$$c+y\equiv 2n\pmod3$$

所以只要看这个区间里有没有对应模 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

和样例一致。