此为详细装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 通过,递推的最优解不仅时间很长,还超时了一个点。

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

最新文章

  1. ligerDialog的使用
  2. C#栈
  3. iOS黑客技术相关
  4. ubuntu 中增加鼠标右键菜单,为Windows 的exe 程序快速增加桌面快捷键
  5. hibernate.cfg.xml文件的说明
  6. 基于HTML5 Canvas的网页画板实现教程
  7. android 豆瓣客户端 视频
  8. Myeclipse 激活代码 8.6以前的版本
  9. 华硕A450c详细清灰拆机教程
  10. MySQL 的数据目录
  11. 【SparkStreaming学习之二】 SparkStreaming算子操作
  12. myBatis简学
  13. aix装python
  14. Thymeleaf-语法整理
  15. C++解析三
  16. LeetCode - Find Duplicate Subtrees
  17. spring boot 多数据源 + 事务控制
  18. Hive权限管理
  19. ICLR 2014 International Conference on Learning Representations深度学习论文papers
  20. android 带RadioButton的Dialog

热门文章

  1. 关于DCMTK3.6.0源代码编译的总结
  2. error: library dfftpack has Fortran sources but no Fortran compiler found解决方法
  3. django-cms 代码研究(八)app hooks
  4. Spring事务传播、隔离等级
  5. FileOutputStream与FileInputStream互相转换
  6. global-local-static-object
  7. 【转】Solr从数据库导入数据(DIH)
  8. 在eclipse中配置一个简单的spring入门项目
  9. codeforces C. Vasily the Bear and Sequence 解题报告
  10. js如何往数组Array中添加元素