此為詳細裝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 通過，遞推的最優解不僅時間很長，還超時了一個點。

不得不說，本題很考察思維，一步一步優化，到達最優。

轉載于:https://www.cnblogs.com/radiumlrb/p/5823263.html

總結

以上是生活随笔為你收集整理的A+B Problem 详细解答 (转载)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。