你们怎么都在做网络流,不就是一道简单的递推吗

而且你们假惺惺的用网络流,过程中还是要用加法,我一个加法都没用。
c++
#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
c++
#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]);
}

此时已经可以通过了,然而,本着精益求精的态度,进一步可以用滚动数组优化,变成这样:
c++
#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);
出现了加号!可是这是可以递归的,故程序优化如下:
c++
#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})
因为这是一个尾递归,所以我们可以通过迭代消除它。
c++
#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 通过,递推的最优解不仅时间很长,还超时了一个点。

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

11 条评论

  • @ 2016-11-15 21:01:18

    %%%

  • @ 2016-09-14 20:57:14

    #include<bits/stdc++.h>
    int main(int a,int b,int s)
    {
    if (!s)
    {
    printf("%d",b==0?a:main(a^b,(a&b)<<1,0));
    exit(0);
    }
    scanf("%d%d",&a,&b);
    main(a,b,0);
    }
    233333

  • @ 2016-08-23 16:30:18

    装B~~~~

  • @ 2016-08-23 16:28:55

    装B~~~~~~~~

  • @ 2016-08-05 20:03:48

    ++就是x=x+1,还是用到加号了

  • @ 2016-07-08 22:25:53

    ....

  • @ 2016-07-02 10:32:22

    楼下,认真你就输了

  • @ 2016-07-02 10:31:53

    不错,%%%。

  • @ 2016-04-07 17:56:07

    我有O(1)的算法 - -

    cin>>a>>b;
    cout<<a+b;

    • @ 2017-02-14 12:36:38

      我还有o(a + b)的算法。
      int main () {
      int a, b, ans = 0;
      cin >> a >> b;
      for (int i = 1; i <= a + b; ++ i)
      ++ ans;
      cout << ans << endl;
      return 0;
      }

  • @ 2016-04-03 13:17:27
    #include<cstdio>
    using namespace std;
    int main(){
        int n,m;
        scanf("%d%d",&n,&m);
        printf("%d",n+m);
        return 0;
    }
    
  • @ 2016-04-02 10:33:53

    什么鬼

  • 1

信息

ID
1000
难度
9
分类
(无)
标签
(无)
递交数
73496
已通过
28188
通过率
38%
被复制
200