A+B的各种姿势

作者: shad0w_walker(admin) 分类: 空分类 发布时间: 2015-05-15 17:18 ė 6 2条评论

众所周知,A+B Problem和P-NP问题、连续统假设以及哥德巴赫猜想等等世界未解难题一样,是举世闻名的难题。这个问题如此的著名以及如此的难以至于几乎任何一个OJ都会把A+B Problem放在Problem Set的第一位,并且任何一个有头脑的ACMer都曾经也将会把大量的精力花在解这道题目上。经过几代人不懈的努力,如今,A+B Problem已经找到了解法,但是A+B Problem是如此的难如此的美妙以至于人们对它的研究永远不会停止。每天每时每刻,都有无数A+B Problem的代码在各个OJ平台上提交,而A+B Problem也成为几乎每个OJ提交量最大没有之一的题目。

今天,我怀着极其崇敬的心情,为大家介绍A+B  Problem。

zhuangbi5

 

A+B Problem的内容其实非常简单,正如“任一大于2的偶数都可写成两个质数之和”一样简洁明了:

输入两个整数A和B,输出A+B的值。

现给出几种处理A+B Problem的姿势
我们可以不妨假设A和B都是非负整数,A、B中有负数的话稍加处理即可。

 


第一种姿势

点击此处 展开代码 毁灭世界


这段代码估计是迄今为止发现的HDOJ1000(A+B  Problem)最短代码了,代码极其简短,短到只有一行仅57B,短到很多本地编译器都无法编译通过

它的缺点是只能对int范围内的数进行计算

 


第二种姿

点击此处 展开代码 毁灭世界×2


这个程序的原理是把A和B转化成二进制数然后模拟二进制加法,全程位运算!(加法用异或,进位用与和或)

由于懒得处理成高精度所以计算范围是long long
zhuangbi3


第三种姿

点击此处 展开代码 毁灭世界×3


这个程序依然是A+B Problem(谁让我讲的就是这个呢),算法是「高精度」,把每一位存在数组里然后模拟加法的「竖式」运算。理论上可以对计算任意位数的数进行处理

但我写的高精度仍不是最优美的,可以在每个数组元素里存多位,这样能提高算法的时间效率、空间效率
zhuangbi1


第四种姿

点击此处 展开代码 毁灭世界×4


恩。。。。。。在A+B Problem的研究领域里,用FFT写A+B等价于「脱裤子放屁」。
这个就是是用傅里叶变换计算A+B的程序。。。 俗话说得好,没有用FFT写过A+B的人不足以谈无聊。

装完逼就跑,真TM刺激

zhuangbi2


第五种姿势

点击此处 展开代码 毁灭世界×5


这是A+B的网络流做法,在两点间构建两条流量分别为a和b的边,然后求最大流23333

由吊炸天的奚政提供!

 

本文出自shad0w_walker,转载时请注明出处及相应链接。

本文永久链接: https://www.sdwalker.com/archives/223.html

2条评论

  1. Ivy_End 2015年5月15日 22:00 回复

    还有压位dp,网络流做法呢?

    1. shad0w_walker(admin)
      shad0w_walker(admin) 2015年5月16日 18:51 回复

      已补!Orz Ivy_End大大!

发表评论

电子邮件地址不会被公开。 必填项已用*标注

返回顶部