自动搬运

查看原文

来自洛谷，原作者为

	木木！ 那不该在时间中存在的，便经不住时间的洗礼

搬运于2025-08-24 21:27:19，当前版本为作者最后更新于2019-12-09 20:37:20，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

dalao 都用 DP，我发一发贪心的题解。

DP 题硬生生被做成了思维题

首先，不考虑长度限制，只考虑两个数字的 1 的个数。设 A 中 1 的个数为 $an$，B 中为 $bn$，C 中为 $cn$。

如果 $an+bn<cn$ 的话，显然无解，因为 1 不可能被凭空创生而来。如果 $an+bn=cn$ 的话，只需要不产生进位，即让两个加数的二进制表示全部错开就好。然后考虑 $an+bn>cn$ 的情况。

在这种情况下，我们需要通过进位消掉 $an+bn-cn$ 个 1，然后保证答案最小。

容易发现，可以简单地使用连续进位来消掉任意个数的 1：

 11111
+   1
------
100000

消掉的 1 的个数即为第一个加数的长度。

严格来说，消掉的 1 的个数的范围为 $[0,an+bn-1]$。因为，我们可以这样子：

 11111     1
+     111111
--------------
100000000000

（空格为 0）

可行性可以保证。然后就是考虑最优性。

很显然，对于这样一组连续进位，两个加数在连续进位之前的位必须都是 0。也就是说，算式里面最多只能有一组连续进位。如果有两组连续进位，可以将这两组合并，然后偷掉一个位（全 0 位显然可以直接抠掉），这样两个加数都会变小，和也会变小。

唯一的进位处就在那个连续进位的地方。

同理，这个连续进位必须在最高位。如果不是的话，可以交换顺序使它在最高位，然后偷掉一个位。

基本框架就确定了，由于消掉的 0 的个数确定，连续进位的长度也确定了，然后只需要在这个基础上贪心地将 1 用完就好了。

在这个连续进位式骨架上，我们可以做的事情包括将一个连续进位中的改成 1，以及在后面跟单独一个 1。容易证明，最优的解就是尽量用 1 填那个进位中的空，如果还有多余的 1，就在后面跟。

举个例子，例如 $an=4$，$bn=5$，$cn=5$。首先计算 $an+bn-cn=4$，所以可以先列连续进位式骨架：

 1111
+   1
----
10001

然后，还有 $an+bn-(an+bn-cn+1)=4$ 个多余的 1，其中三个可以填到空中，剩余一个放在末尾：

 1111
+11111
------
111101

程序指示 30+31=61，符合条件，并且正确。

代码如下：

int a,b,c;
scanf("%d%d%d",&a,&b,&c);
		
const int l = max({
	32-__builtin_clz(a),
	32-__builtin_clz(b),
	32-__builtin_clz(c)
});

const int an = __builtin_popcount(a);
const int bn = __builtin_popcount(b);
const int cn = __builtin_popcount(c);

if(an+bn<cn || !cn)
{
	printf("-1\n");
	continue;
}
if(an+bn-cn == 0)
{
	printf("%d\n",allone(cn)); // cn个1
	continue;
}
if(an+bn-cn+1+max(2*cn-an-bn,0) > l) // 计算最终长度的式子
{
	printf("-1\n");
	continue;
}

const int diff = an+bn-cn;
int ans = 1<<diff;
for(int i=diff+1; i<an+bn; ++i)
{
	if(i-diff < diff) // 往空里填数
	{
		ans |= 1<<(i-diff);
	}
	else // 往末尾加数
	{
		ans = (ans<<1)|1;
	}
}
printf("%d\n",ans);

然后交上去，就会发现这份代码只能得 20 分。

如果 $an=4$，$bn=2$，$cn=3$，这个程序会给出下面的加式：

 111
+111
----
1110

实际上，加式是这个：

 1111
+ 11
-----
10101

这个只需要注意一下就好了。稍微修改一下代码，加一个特判，就可以 A 了。时间复杂度 $\Theta(\log n)$，常数极小，耗时 2ms-3ms，就是程序运行的基础时间。

附 AC 代码：

#include <cstdio>
#include <algorithm>
using namespace std;

inline int slen(int an,int bn,int cn) // 计算最终长度
{
	return max({an+bn-cn+1+max(2*cn-an-bn,0),an+1,bn+1});
}

inline int allone(int dig) // dig 个 1 组成的数字
{
	return (1<<dig)-1;
}

int main()
{
	int t;
	scanf("%d",&t);
	for(int asdf=1; asdf<=t; ++asdf)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		
		const int l = max({
			32-__builtin_clz(a),
			32-__builtin_clz(b),
			32-__builtin_clz(c)
		});

		const int an = __builtin_popcount(a);
		const int bn = __builtin_popcount(b);
		const int cn = __builtin_popcount(c);

		if(an+bn<cn || !cn)
		{
			printf("-1\n");
			continue;
		}
		if(an+bn-cn == 0)
		{
			printf("%d\n",allone(cn));
			continue;
		}
		if(slen(an,bn,cn) > l)
		{
			printf("-1\n");
			continue;
		}

		const int diff = an+bn-cn;  // 连续等式的长度
		const int flen = slen(an,bn,cn); // 最终结果的长度
		int ans = (1<<(flen-1))+allone(flen-diff-1); // 最终结果的骨架（连续进位式再加上末尾的1）

		for(int i=flen; i<an+bn; ++i)
		{
			ans |= 1<<(i-diff); // 因为末尾的 1 已经被加上，可以直接往空格里填 1
		}
		printf("%d\n",ans);
	}
}