P1633

我们可以设一个五维的状态，f[i][j][k][l][0/1],表示X中有i个1，Y中有j个1，Z中有k个1，当前比较到了第l位，且Z的第l位是0还是1.

对于X和Y的第l位，有两种选择，就是填0或1，所以有如下转移：

f[i][j][k][l][0]+0          ->f[i][j][k][l+1][0]   //0 0
                +(1ll<<l-1) ->f[i][j+1][k+1][l+1][0]    //0 1
                +(1ll<<l-1) ->f[i+1][j][k+1][l+1][0]    //1 0
                +(1ll<<l)   ->f[i+1][j+1][k+1][l+1][1]  //1 1

f[i][j][k][l][1]+0          ->f[i][j][k][l+1][0]    //0 0
                +(1ll<<l-1) ->f[i][j+1][k][l+1][1]      //0 1
                +(1ll<<l-1) ->f[i+1][j][k][l+1][1]      //1 0
                +(1ll<<l)   ->f[i+1][j+1][k+1][l+1][1]  //1 1

注意给第l位加个1相当于给原数加\(2^{l-1}\),而不是\(2^l\)

举个例子，对于1111和11111这两种第l位分别是0和1的情况：~~(01111前导零不用管，只是表示第l位为0而已)~~

//左->右为低位->高位
    l        l
11110 ->111100
i   0
j   0
11110 ->111110 
i   0
j   1       
11110 ->111110
i   1
j   0       
11110 ->111111
i   1
j   1

    l        l
11111 ->111110
i   0
j   0
11111 ->111101 
i   0
j   1       
11111 ->111101
i   1
j   0       
11111 ->111111
i   1
j   1

分别加上贡献以后，再取个最小值就行了。

边界是\(f[0][0][0][1][0]=0\),l从1开始.

对输入的a,b,c求出ll,na,nb,nc那么最终答案为\(\min(f[na][nb][nc][0,1,...,ll][0,1])\)

注：

\(f[i][j][k][l][0]+2^{l-1}\)不能转移给\(f[i][j+1][k+1][l][1]\),而是转移给\(f[i][j][k+1][l+1][0]\)

因为l没有移动位置，下次还是在第l位加1，所以会出现X或Y同一位加了两次1，出现错误。

~~其实l那一维可以滚存的，但我懒~~

Code:

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long 
using namespace std;
const int N=33,INF=5e18;
int f[N][N][N][N][2];
int n,a,b,c,na,nb,nc,la,lb,lc,ll;
void init() {
    memset(f,0x3f,sizeof f);
    na=0;nb=0;nc=0;la=0;lb=0;lc=0;
    while(a) {
        if(a&1)na++;
        la++;
        a>>=1;
    }
    while(b) {
        if(b&1)nb++;
        lb++;
        b>>=1;
    }
    while(c) {
        if(c&1)nc++;
        lc++;
        c>>=1;
    }
    ll=max(la,max(lb,lc));
}
void work() {
    f[0][0][0][1][0]=0;
    for(int i=0; i<=na; ++i) {
        for(int j=0; j<=nb; ++j) {
            for(int k=0; k<=nc; ++k) {
                for(int l=1; l<=ll; ++l) {
                    f[i][j][k][l+1][0]=min(f[i][j][k][l+1][0],min(f[i][j][k][l][0],f[i][j][k][l][1]));
                    f[i+1][j+1][k+1][l+1][1]=min(f[i+1][j+1][k+1][l+1][1],min(f[i][j][k][l][0],f[i][j][k][l][1])+(1ll<<l));//注意写法，1ll<<l要加括号

                    f[i][j+1][k+1][l+1][0]=min(f[i][j+1][k+1][l+1][0],f[i][j][k][l][0]+(1ll<<l-1));
                    f[i+1][j][k+1][l+1][0]=min(f[i+1][j][k+1][l+1][0],f[i][j][k][l][0]+(1ll<<l-1));
                    f[i][j+1][k][l+1][1]=min(f[i][j+1][k][l+1][1],f[i][j][k][l][1]+(1ll<<l-1));
                    f[i+1][j][k][l+1][1]=min(f[i+1][j][k][l+1][1],f[i][j][k][l][1]+(1ll<<l-1));             
                }
            }
        }
    }
}
signed main() {
    scanf("%lld",&n);
    for(int i=1; i<=n; ++i) {
        scanf("%lld%lld%lld",&a,&b,&c);
        init();//初始化
        work();//dp
        int ans=INF;
        for(int i=0; i<=ll; ++i) {
            int tmp1=f[na][nb][nc][i][0],cnt1=0;
            int tmp2=f[na][nb][nc][i][1],cnt2=0;
            while(tmp1>0)tmp1>>=1,cnt1++;
            while(tmp2>0)tmp2>>=1,cnt2++;
            if(cnt1<=ll && cnt1>0)ans=min(ans,f[na][nb][nc][i][0]);//所有满足条件的数中取最小值
            if(cnt2<=ll && cnt2>0)ans=min(ans,f[na][nb][nc][i][1]);
        }
        if(ans==INF)printf("-1\n");
        else printf("%lld\n",ans);
    }
    return 0;
}