Just OI-ACM

二进制 a+b

 
  • Apr 13, 2019

Problem

Source: BZOJ 3107, CQOI 2013

Description

输入三个整数 $a, b, c$，把它们写成无前导 0 的二进制整数。比如 $a=7, b=6, c=9$，写成二进制为 $a=111, b=110, c=1001$。接下来以位数最多的为基准，其他整数在前面添加前导 0，使得 $a, b, c$ 拥有相同的位数。比如在刚才的例子中，添加完前导 0 后为 $a=0111, b=0110, c=1001$。最后，把 $a, b, c$ 的各位进行重排，得到 $a’, b’, c’$，使得 $a’+b’=c’$。比如在刚才的例子中，可以这样重排：$a’=0111, b’=0011, c’=1010$。

你的任务是让 $c’$ 最小。如果无解，输出-1。

数据规模：$a,b,c \leq 2^{30}$

Input

输入仅一行，包含三个整数 $a, b, c$。

Output

输出仅一行，为 $c’$ 的最小值。

Sample Input

7 6 9

Sample Output

10

 

Solution

$f(t, i, j, k, p)$：从低位枚举到第 $t$ 位，$A$ 已放 $i$ 个 1，$B$ 已放 $j$ 个 1，$C$ 已放 $k$ 个 1，进位为 $p$（若 $p=0$，表示该状态无进位；否则表示有进位）时的最小 $C’$ 值

同时枚举 $A’$ 和 $B’$ 的第 $t$ 位是放 0 还是 1，并结合上一位的进位算出该位是否有进位和 $C’$ 的该位上是 0 还是 1。设该位上 $A’$、$B’$ 与上次进位之和为 $\text{res}​$，则有：

\[f \Big(t, i+x, j+y, k+(\text{res}​ \& 1), \text{res} >> 1 \Big ) = \min \bigg ( f(t-1, i, j, k, p) + \Big ( (\text{res}​ \& 1)<<(t-1) \Big ) \bigg )\]

其中 $x,y = 0 /1$。

Code

Github (C++)

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iomanip>
using namespace std;

const int inf = 0x7fffffff;
int f[2][40][40][40][2];
int n, m, p, n1, m1, p1, L;

void Init() {
    scanf("%d%d%d",&n,&m,&p);
    n1 = 0, m1 = 0, p1 = 0;
    int Max = max(n, max(m, p));

    while(n) {
        if(n & 1) n1++;
        n >>= 1;
    }

    while(m) {
        if(m & 1) m1++;
        m >>= 1;
    }

    while(p) {
        if(p & 1) p1++;
        p >>= 1;
    }

    while(Max) {
        L++;
        Max >>= 1;
    }
}

void Dp() {
    for(int t = 0; t <= 1; t++)
        for(int i = 0; i<= n1; i++)
            for(int j = 0; j <= m1; j++)
                for(int k = 0; k <= p1; k++)
                    for(int p = 0; p <= 1; p++) f[t][i][j][k][p] = inf;

    int t = 0;
    f[t][0][0][0][0] = 0;

    for(int l = 1; l <= L; l++) {
        t = !t;
        for(int i = 0; i <= n1; i++)
            for(int j = 0; j <= m1; j++)
                for(int k = 0; k <= p1; k++)
                    for(int p = 0; p <= 1; p++)
                        if(f[!t][i][j][k][p] != inf) {
                            for(int x = 0; x <= 1; x++)
                                for(int y = 0; y <= 1; y++) {
                                    int res = x + y + p;
                                    f[t][i + x][j + y][k + (res & 1)][res >> 1] = min(f[t][i + x][j + y][k + (res & 1)][res >> 1], f[!t][i][j][k][p] + ((res & 1) << (l - 1)));
                                }
                            f[!t][i][j][k][p] = inf;
                        }
    }

    if(f[t][n1][m1][p1][0] != inf) printf("%d",f[t][n1][m1][p1][0]);
    else printf("-1");
}

int main() {
    Init();
    Dp();
    return 0;
}
Search