题号 NC19926
名称 [CQOI2013]二进制A+B
来源 [CQOI2013]
每日一题三期汇总贴~


如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

作者：jzdx（hjh）

算法1

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

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

分析

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

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

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

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

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

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

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

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

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

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

dfs

我们定义

表示用个1和个0组成,用个1和个0组成, 由得到长度为，且含有个1的数的最小值

答案就是(分别表示中1的个数，为最大位数)

优化

可行性剪枝:

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

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

记忆化搜索

我们用表示当前状态是否访问过，用表示递归结束后的结果

如果表示访问过，直接返回

时间复杂度

参考文献

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;
}

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目5月13日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴