【洛谷】题解 P1633 【二进制】

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

    }

}