[CQOI2013]二进制A+B

题号 NC19926
名称 [CQOI2013]二进制A+B
来源 [CQOI2013]

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

输入三个整数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;
}