首页 > 代码库 > A+B Problem 详细解答 (转载)

A+B Problem 详细解答 (转载)

此为详细装13版

转载自:https://vijos.org/discuss/56ff2e7617f3ca063af6a0a3

 

全文如下,未作修改,仅供围观,不代表个人观点:

 

你们怎么都在做网络流,不就是一道简单的递推吗   发表于2016-04-02 10:29

而且你们假惺惺的用网络流,过程中还是要用加法,我一个加法都没用。

#include <cstdio>int m, n, a[32768][32768];int main(){    scanf("%d%d", &m, &n);    for (int i = 1; i <= m; ++i) {        a[i][0] = i;        for (int j = 1; j <= n; ++j) {            a[0][j] = j;            a[i][j] = ++a[i - 1][j];            --a[i - 1][j];        }    }    printf("%d\n", a[m][n]);}

根据加法的性质,0 为加法单元,满足 m + 0 = m, 0 + n = n
然后就是裸推了:i + j = i + (j - 1) + 1

但是这样会超时,而且在 Vijos 上测数组太大了,编译就错误了。所以要进行优化,合并一个状态:
设 F(i) = i + n, 则 F(0) = n, F(i) = F(i - 1) + 1

#include <cstdio>int m, n, a[32768];int main(){    scanf("%d%d", &m, &n);    a[0] = n;    for (int i = 1; i <= m; ++i) {        a[i] = ++a[i - 1];        --a[i - 1];    }    printf("%d\n", a[m]);}

此时已经可以通过了,然而,本着精益求精的态度,进一步可以用滚动数组优化,变成这样:

#include <cstdio>int m, n, ans;int main(){    scanf("%d%d", &m, &n);    ans = n;    while (m--) ++ans;    printf("%d\n", ans);}

这是递推做法的最优解了。然而,事实上,还可以用位运算做,才是真正的最优解。
首先,加法分为两个步骤,一个是数字加,一个是进位。
因为单位二进制中 1 + 1 = 0, 1 + 0 = 1, 0 + 0 = 0, 0 + 1 = 1
正好符合异或的性质。
进位的部分则为 a & b。
但是第一位不可能进位,所以整体移动一位,即 (a & b) << 1.
那么 a + b = (a ^ b) + ((a & b) << 1);
出现了加号!可是这是可以递归的,故程序优化如下:

#include <cstdio>int m, n;int add(int a, int b){    if (a == 0) return b;    if (b == 0) return a;    int s = a ^ b;    int t = (a & b) << 1;    return add(s, t);}int main(){    scanf("%d%d", &m, &n);    printf("%d\n", add(m, n));}

显然,该程序时间复杂度为 Ø(log max{a, b})
因为这是一个尾递归,所以我们可以通过迭代消除它。

#include <cstdio>int m, n;int main(){    scanf("%d%d", &m, &n);    int u = m & n;    int v = m ^ n;    while (u) {        int s = v;        int t = u << 1;        u = s & t;        v = s ^ t;    }    printf("%d\n", v);}

即为本题最优解。
在 Vijos 上看不出差距,在洛谷上,位运算解法 2ms 通过,递推的最优解不仅时间很长,还超时了一个点。

不得不说,本题很考察思维,一步一步优化,到达最优。

A+B Problem 详细解答 (转载)