[CQOI2013]二进制A+B

做法：构造

思路：

说不明白，参考了别人的题解，给几组情况就能够理解明白了
设x,y,z是a,b,c二进制中1的个数
假设x>y

分类讨论

1) z=1

000001111111111
011110000000001
100000000000000

2) 1<z<y

0001111111111
0110000000111
1000000000110

3) z=y

01111111111
00000011111
10000011110

4) y<z⩽x

01111111111
00011111000
10011110111

5) x<z<x+y

0111111111100
0111000000011
1110111111111

6) z=x+y

000001111111111
111110000000000
111111111111111

可以用bitset构造模拟a'和b'即可

代码

// Problem: [CQOI2013]二进制A+B
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/problem/19926
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
#define debug(a) cout<<#a<<":"<<a<<"\n"
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=100010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

int calc(ll n){
    int c=0;
    while(n){
        c++;
        n>>=1;
    }
    return c;
}

void solve(){
    ll a,b,c;cin>>a>>b>>c;
    int len=calc(max({a,b,c}));
    bitset<31> x(a),y(b),z(c);
    if(x.count()<y.count()) swap(x,y),swap(a,b);
    bitset<31> aa,bb;
    if(z.count()<=x.count()){
        for(int i=0;i<x.count();i++) aa[i]=1;
        if(z.count()<=y.count()){
            for(int i=0;i<z.count();i++) bb[i]=1;
            for(int i=x.count(),j=0;j<y.count()-z.count();i++,j++) bb[i]=1;
        }
        else{
            for(int i=z.count()-y.count(),j=0;j<y.count();i++,j++) bb[i]=1;
        }
        if(aa.to_ulong()+bb.to_ulong()>=(1ll<<len)) cout<<"-1\n";
        else cout<<aa.to_ulong()+bb.to_ulong()<<"\n";
    }
    else if(z.count()<=x.count()+y.count()){
        for(int i=z.count()-x.count(),j=0;j<x.count();i++,j++) aa[i]=1;
        int yy=y.count();
        for(int i=0;i<z.count()-x.count();i++,yy--) bb[i]=1;
        for(int i=z.count()-x.count()+x.count()-1;yy>0;i--,yy--) bb[i]=1;
        if(aa.to_ulong()+bb.to_ulong()>=(1ll<<len)) cout<<"-1\n";
        else cout<<aa.to_ulong()+bb.to_ulong()<<"\n";
    }
    else cout<<"-1\n";
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int t;cin>>t;while(t--)
    solve();
    return 0;
}