题解 P4574 【[CQOI2013]二进制A+B】

· · 题解

题目大意：给定n位二进制数a,b,c，要求重组三个数的各个位，使得 a^\prime+b^\prime=c^\prime 且最小化 c^\prime。

不考虑位数限制，显然答案只与三个数中1的个数有关。

令x=cnta,y=cntb,z=cntc，其中 cntx 代表x中1的个数。

不妨令x\geqslanty。

以下用 x=10,y=5 来举例。

1. 若 z=1 ，构造方式如下：

000001111111111
011110000000001
100000000000000

证明：显然最低位肯定是 1+1=10 ，然后再往上肯定都是单个1，构造方式唯一。

2. 若1<z<y，构造方式如下：

0001111111111
0110000000111
1000000000110

证明： 若最低位为1+0=1，则去掉最低位后变成了 (x−1,y,z−1) 或 (x,y−1,z−1) 。

二者都需要 x+y−z+1 位，算上最低位有 x+y−z+2 位，而这种构造法只需要 x+y−z+1 位。

由数学归纳法可证最低位为 1+0=1 不优。

那么最低位为 1+1=10 就确定了。

然后……然后自己YY吧我没证出来不过应该是对的，感觉数学归纳法啥的能证。

3. 若 z=y ，构造方式如下：

01111111111
00000011111
10000011110

证明：这种构造方式保证 a^\prime 和 b^\prime 都是最小的，显然最优。

4. 若y<z\leqslantx，构造方式如下：

01111111111
00011111000
10011110111

证明：

显然 c^\prime 最小 x+1 位。

如果想要使 c^\prime 减小，只能将前面的那些0往前挪或将最后一个0往前挪。

显然前面那些0挪不动，只能将最后一个0往前挪(比如变成1001101111)。

这说明最后 z−y 位必须是 1+0=1。

那么去掉最后 z−y位，问题变成了 (x+y−z,y,y)。

由y=z的证明可得这种构造法是最优的。

5. 若x<z<x+y，构造方式如下：

0111111111100
0111000000011
1110111111111

证明：

显然答案至少 z+1 位，因为z个 1−x 个1一定会得到 z−x 个1，

而 z−x<y ，矛盾。

然后位数确定后证明就同上了。

若 z=x+y ，构造方式如下：

000001111111111
111110000000000
111111111111111

然后……就完事了。

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int Digit(int x) {
    int re=0;
    while(x)++re,x>>=1;
    return re;
}
int Count(int x) {
    int re=0;
    while(x)x^=x&-x,++re;
    return re;
}
int main() {
    int x,y,z,limit,ans;
    cin>>x>>y>>z;
    limit=max( max( Digit(x) , Digit(y) ) , Digit(z) );
    x=Count(x);
    y=Count(y);
    z=Count(z);
    if(x<y) swap(x,y);
    if(z<=y) ans=((1<<x)-1)+((1<<z)-1|((1<<y-z)-1<<x));
    else if(z<=x) ans=((1<<x)-1)+((1<<y)-1<<z-y);
    else if(z<=x+y) ans=((1<<x)-1<<z-x)+((1<<z-x)-1|((1<<x+y-z)-1<<z+z-x-y));
    else ans=-1;
    if(Digit(ans)>limit) ans=-1;
    cout<<ans<<endl;
    return 0;
}

ps：蒟蒻第一题题解不会排版，请见谅，管理员请放松一下要求，过了这篇题解，谢谢。