题解：387. 二进制 A+B

题目

输入三个整数 ，将它们分别转换为无前导0的二进制整数。例如，若 ，则转换后的二进制形式为 。

接下来，以三个二进制数中位数最多的为准，对其他二进制数在高位补前导0，使 的二进制形式拥有相同的位数。延续上述例子，位数最多的二进制数为 （4位），补前导0后结果为 。

最后，对补零后 的所有二进制位进行整体重排（即三个数的每一位可以重新分配给 的对应位置，但总位数保持不变），得到新的二进制数 ，需满足等式 。例如上述例子中，可重排为 （此时 ，即 ）。

你的任务是找到满足条件的最小 （以十进制形式输出）；若不存在任何合法的重排方式，则输出 。

题解

俗话说的好，抄了题解，问了 AI，就要自己写一篇，不然对不起自己。

1. 一眼可以爆搜，考虑枚举每一位 的 选择方式，最后判断 即可；
2. 发现仅和个数有关，所以不用最后判断，而只是记录 各还能有多少 能使用；
3. 这个听起来就很像是状态，所以可以考虑加上记忆化， 表示 位各剩下 个可以用的最小 结果；
4. 发现这个状态定义其实并不够，因为转移的时候，位与位之间可以通过进位的方式从低位向高位进行影响；
5. 此时定下来搜索的方向为从低位到高位，并且再开一维 表示是否受到进位；

至于构造……
我更喜欢搜索！

代码：

#include<bits/stdc++.h>
#define LL long long

using namespace std;

const int MAXN = 35;
const LL INF = 0x3f3f3f3f3f3f3f3f;

LL a, b, c;
LL cnta, cntb, cntc, len;
LL f[MAXN][MAXN][MAXN][MAXN][2];

inline int bitLen(LL x) {
    int len = 1;
    while ((1LL << len) < x)
        len++;
    return len;
}
inline LL dfs(int pos, int aa, int bb, int cc, bool carry) {
    if (aa < 0 || bb < 0 || cc < 0)
        return INF;
    if (pos == len)
        return (!aa && !bb && !cc && !carry) ? 0 : INF;
    if (f[pos][aa][bb][cc][carry] != -1)
        return f[pos][aa][bb][cc][carry];

    LL res = INF;
    for (int x = 0; x <= 1; ++x)
        for (int y = 0; y <= 1; ++y) {
            LL sum = x + y + carry;
            LL z = sum & 1;
            if (aa >= x && bb >= y && cc >= z)
                res = min(res, (z << pos) + dfs(pos + 1, aa - x, bb - y, cc - z, sum > z));
        }
    return f[pos][aa][bb][cc][carry] = res;
}

int main() {
    freopen("ab.in", "r", stdin);
    freopen("ab.out", "w", stdout);

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> a >> b >> c;
    len = max({bitLen(a), bitLen(b), bitLen(c)});
    cnta = __builtin_popcount(a);
    cntb = __builtin_popcount(b);
    cntc = __builtin_popcount(c);

    memset(f, -1, sizeof(f));
    LL ans = dfs(0, cnta, cntb, cntc, 0);
    cout << (ans >= INF ? -1 : ans);
    return 0;
}