题解 P1633 【二进制】

木木！ · 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);
    }
}