自动搬运

查看原文

来自洛谷，原作者为

	TYxxj will der dich rief dir geben!

搬运于2025-08-24 22:01:33，当前版本为作者最后更新于2021-01-27 10:59:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

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

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

不妨令x$\geqslant$y。

以下用 $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$\leqslant$x，构造方式如下：

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：蒟蒻第一题题解不会排版，请见谅，管理员请放松一下要求，过了这篇题解，谢谢。