题目描述

输入三个整数a, b, c，把它们写成无前导0的二进制整数。比如a=7, b=6, c=9，写成二进制为a=111, b=110, c=1001。接下来以位数最多的为基准，其他整数在前面添加前导0，使得a, b, c拥有相同的位数。比如在刚才的例子中，添加完前导0后为a=0111, b=0110, c=1001。最后，把a, b, c的各位进行重排，得到a’, b’, c’，使得a’+b’=c’。比如在刚才的例子中，可以这样重排：a’=0111, b’=0011, c’=1010。

你的任务是让c’最小。如果无解，输出-1。

样例

输入
7 6 9
输出
10

$a,b,c <= 2^{30}$

算法1

(暴搜 + 记忆化搜索优化 + 剪枝)

记得我上一次写暴搜,那还是我上一次写暴搜的时候

分析

拿到题没什么好的思路就只能想到暴搜

既然要暴搜，我们就要想好每次层需要维护什么状态以及，最终我们需要求什么

我们需要重排$a$和$b$的二进制表示并使它们的和可以由$c$重排得到

重排$a$和$b$我们可以枚举每一位$a$和$b$是0还是1，所以我们需要分别记录$a$和$b$可用的1的个数(0也可以但是直觉上就想维护1)

然后怎么知道最后的答案能否被$c$重排得到？

首先我们需要知道当$a$和$b$的某一位确定之后当前位的结果是多少

加法除了考虑当前位还需要考虑上一位的进位所以我们需要维护一个进位状态$carry$，然后就能知道当前位的结果了

知道每一位的结果我们就知道,重排后$a + b$的答案中1的个数$s$的大小，s和$c$中1的个数相同说明有解

我们也可以反向思考，如果当前位的结果是1，就将$c$中1消耗掉一个，最后如果$c$中的1恰好被消掉说明有解

所以我们再维护一个变量$s$表示$c$中可用的1有多少

dfs

我们定义$dfs(u,na,nb,s,ca)$

表示用$na$个1和$u - na$个0组成$a’$,用$nb$个1和$u - nb$个0组成$b’$, 由$a’ + b’ + ca(进位)$得到长度为$u$，且含有$s$个1的数的最小值

答案就是$dfs(len,num[a],num[b],num[c],0)$($num[a]，num[b],num[c]$分别表示$a,b,c$中1的个数，$len$为最大位数)

优化

可行性剪枝:

if(s < 0 || s > u) return INF;

如果当前$c$中可消耗的1的个数为负数了或者在未来无法消耗完了我们可以提前退出

记忆化搜索$(优化力度很大)$

我们用$vis[u][na][nb][s][ca]$表示当前状态是否访问过，用$f[u][na][nb][s][ca]$表示$dfs(u,na,nb,s,ca)$递归结束后的结果

如果$vis[u][na][nb][s][ca] = true$表示访问过，直接返回$f[u][na][nb][s][ca]$

时间复杂度 $O(30^4)$

参考文献

C++ 代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long LL;
const LL INF = 0x3f3f3f3f3f3f3f3fll;
const int N = 35;
LL f[N][N][N][N][3];
bool vis[N][N][N][N][3];
LL a,b,c;
int nums[5],len;

LL dfs(int u,int na,int nb,int s,int ca)
{
    LL &v = f[u][na][nb][s][ca];
    if(vis[u][na][nb][s][ca]) return v;
    vis[u][na][nb][s][ca] = true;
    if(s < 0 || s > u) return INF;
    if(u == 0)
    {
        if(ca == 1 || na != 0 || nb != 0 || s != 0) return INF;
        return f[u][na][nb][s][ca] = 0;
    }
    LL tmp;
    if(na >= 1 && nb >= 1)//a和b当前位都为1
    {
        tmp = dfs(u - 1,na - 1,nb - 1,s - ca,1);
        if(tmp < INF) tmp = tmp * 2ll + ca;
        v = min(v,tmp);
    }
    if(na >= 1)//a的当前为1，b为0
    {
        tmp = dfs(u - 1,na - 1,nb,s - (1 ^ ca),(1 + ca) >= 2);
        if(tmp < INF) tmp = tmp * 2ll + (1 ^ ca);
        v = min(v,tmp);
    }
    if(nb >= 1)//b的当前位为1，a为0
    {
        tmp = dfs(u - 1,na,nb - 1,s - (1 ^ ca),(1 + ca) >= 2);
        if(tmp < INF) tmp = tmp * 2ll + (1 ^ ca);
        v = min(v,tmp);
    }
    tmp = dfs(u - 1,na,nb,s - ca,0);//a，b当前位都为0
    if(tmp < INF) tmp = tmp * 2ll + ca;
    v = min(v,tmp);
    return v;
}

int main()
{
    scanf("%lld%lld%lld",&a,&b,&c);
    memset(f,0x3f,sizeof f);
    int res = 0;
    while(a)
    {
        nums[0] += (a & 1);
        a >>= 1;
        res ++;
    }
    len = max(len , res);
    res = 0;
    while(b)
    {
        nums[1] += (b & 1);
        b >>= 1;
        res ++;
    }
    len = max(len , res);
    res = 0;
    while(c)
    {
        nums[2] += (c & 1);
        c >>= 1;
        res ++;
    }
    len = max(len , res);
    LL t = dfs(len,nums[0],nums[1],nums[2],0);
    if(t >= INF) t = -1;
    printf("%lld\n",t);
    return 0;
}