3767 - A+B Problem加强版

有史以来做过的最难的A+B！

by zzq_666

这道题费劲了我许多心思，真的，如果还有小数就更麻烦了！（幸好没有小数） 一开始我就是当做普通的，简单的A+B，所以，我第一次提交了这段代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
  long long a,b;
  cin>>a>>b;
  long long c=a+b;
  cout<<c<<endl;
 return 0;
}

结果很快，题目就显示我做错了。 数据如下： 254364235870267340578439847259857 135862938562984372392352985672

这一看就不是简简单单的long long就可以解决的啊！ 于是，我参考了我之前做过的高精度加法，重新做了一次。 代码如下：

#include<bits/stdc++.h>
using namespace std;

string Add(string add1,string add2)
{
  string ans(max(add1.size(),add2.size())+1,'0');
  for(int i=ans.size()-1,l1=add1.size(),l2=add2.size();i>=0;i--)
  {
    int t=(ans[i]-'0')+(l1<1?0:add1[--l1]-'0')+
	(l2<1?0:add2[--l2]-'0');
    ans[i]=t%10+'0';
    ans[i-1]=(ans[i-1]-'0'+t/10)+'0';
  }
  for(;ans[0]=='0'&&ans.size()>1;ans.erase(0,1));
  return ans;
}

int main()
{
  string add1,add2;
  cin>>add1>>add2;
  cout<<Add(add1,add2)<<endl;
  return 0;
}

我满怀期待地交了上去，结果还是没过！ 数据如下： -12345678976234567898765234567 2345678765432345678764928365

还有负数！ 所以这道题还需要判断正负。

所以，要用我们学过的有理数加减法来对它更深的解刨。

规律如下： 如果符号一样，两个绝对值相加，符号取二者之一； 如果符号不一样，绝对值大的减小的，取绝对值更大的符号。

也就是说，好端端的加法还要用到减法！ 于是我就用了高精度减法补充了上去，代码如下：

#include<bits/stdc++.h>
using namespace std;

int Cmp(string add1,string add2)
{
  if(add1.length()!=add2.length())
    return add1.length()>add2.length();
  return add1>add2;
}

string Add(string add1,string add2)
{
  string ans(max(add1.size(),add2.size())+1,'0');
  for(int i=ans.size()-1,l1=add1.size(),l2=add2.size(); i>=0; i--)
  {
    int t=(ans[i]-'0')+(l1<1?0:add1[--l1]-'0')+
	(l2<1?0:add2[--l2]-'0');
    ans[i]=t%10+'0';
    ans[i-1]=(ans[i-1]-'0'+t/10)+'0';
  }
  for(; ans[0]=='0'&&ans.size()>1; ans.erase(0,1));
  return ans;
}

string Sub(string x,string y)
{
  string ans="";
  int i;
  for(i=y.length(); i<x.length(); i++)
	y='0'+y;
  for(i=x.length()-1; i>=0; i--)
  {
    char c=x[i]-y[i]+'0';
    if(c<'0')
    {
      x[i-1]--;
      c+=10;
    }
    ans=c+ans;
  }
  return ans;
}

int main()
{
  string add1,add2;
  cin>>add1>>add2;
  bool b1=true,b2=true;
  if(add1[0]=='-')
    add1.erase(0,1),b1=false;
  if(add2[0]=='-')
    add2.erase(0,1),b2=false;
  if(b1==b2)
  {
    if(!b1)
      cout<<'-';
    string ans=Add(add1,add2);
    for(; ans[0]=='0'&&ans.size()>1; ans.erase(0,1));
    cout<<ans<<endl;
  }
  else
  {
    bool b=b1;
    if(!Cmp(add1,add2))
      swap(add1,add2),b=b2;
    if(!b)
      cout<<'-';
    string ans=Sub(add1,add2);
    for(; ans[0]=='0'&&ans.size()>1; ans.erase(0,1));
    cout<<ans<<endl;
  }
  return 0;
}

提交了上去，终于解答正确了！ 如果有小数，还过不去呢！ 最后感叹一句：没想到一个A，B的加法花了我好几天，70行代码！