题解：P1633 二进制

· · 题解

P4574 来的。

好玩。

主播主播不会 DP 怎么办？没事，强行构造把它办！

（准确来讲是分类讨论······）

设 f(x) 为 x 的二进制中 1 的个数（默认 f(a)\ge f(b)）。

然后有解的情况就可以分成三类（默认满足长度限制）。

第一类：1\le f(x)< f(b)。

基础格式为：

以左边为第一位
111111100000
100000011100
000000000010
（这里给出 f(a)=7，f(b)=4，f(c)=1 的例子）

然后 f(c) 每多一，就多把 b 的一个 1 靠到最左边：

以左边为第一位
111111100000
110000011000
010000000100
（这里给出 f(a)=7，f(b)=4，f(c)=2 的例子）

然后这部分的长度需求为 f(a)+f(b)-f(c)+1。

第二类：f(b)\le f(x)\le f(a)。

基础格式为：

以左边为第一位
111111100000
111100000000
011100010000
（这里给出 f(a)=7，f(b)=4，f(c)=4 的例子）

然后 f(c) 每多一，就多把 b 的 1 的联通块往右移一位：

以左边为第一位
111111100000
011110000000
101110010000
（这里给出 f(a)=7，f(b)=4，f(c)=5 的例子）

然后这部分的长度需求为 f(a)+1。

第三类：f(a)< f(x)\le f(a)+f(b)。

基础格式为：

以左边为第一位
011111110000
100001110000
111110111000
（这里给出 f(a)=7，f(b)=4，f(c)=8 的例子）

然后 f(c) 每多一，就多把 b 的一个 1 靠到最左边同时把 a 的 1 的联通块往右移一位：

以左边为第一位
001111111000
110000011000
111111101100
（这里给出 f(a)=7，f(b)=4，f(c)=9 的例子）

然后这部分的长度需求为 f(c)+1（注意当 f(c)=f(a)+f(b) 时不需要加一）。

最后非以上三类的无解以及注意在每种情况中判一下是否满足长度限制就可以了。

注意多测清空。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,a,b,c,na,nb,nc,ca,cb,cc,la,lb,lc,ans,ksm[100];
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>a>>b>>c,na=a,nb=b,nc=c,ksm[1]=1,ca=0,cb=0,cc=0,la=0,lb=0,lc=0,ans=0;
        for(int i=2;i<=63;i++)ksm[i]=ksm[i-1]*2;
        while(na)ca+=na%2,na>>=1,la++;
        while(nb)cb+=nb%2,nb>>=1,lb++;
        while(nc)cc+=nc%2,nc>>=1,lc++;
        if(ca<cb)swap(a,b),swap(ca,cb),swap(la,lb);
        if(1<=cc&&cc<cb){
            if(ca+cb-cc+1>max(la,max(lb,lc)))cout<<"-1";
            else{
                for(int i=2;i<=cc;i++)ans+=ksm[i];
                cout<<ans+ksm[ca+cb-cc+1];
            }
        }
        else if(cb<=cc&&cc<=ca){
            if(ca+1>max(la,max(lb,lc)))cout<<"-1";
            else{
                for(int i=1;i<=cc-cb;i++)ans+=ksm[i];
                for(int i=cc-cb+2;i<=cc;i++)ans+=ksm[i];
                cout<<ans+ksm[ca+1];
            }
        }
        else if(ca<cc&&cc<=ca+cb){
            if(cc+1-(cc==ca+cb)>max(la,max(lb,lc)))cout<<"-1";
            else{
                for(int i=1;i<=cc+1-ca-cb+cc-1;i++)ans+=ksm[i];
                for(int i=cc+1-ca-cb+cc+1;i<=cc+1;i++)ans+=ksm[i];
                cout<<ans;
            }
        }
        else cout<<"-1";
        cout<<"\n";
    }
    return 0;
}