西北工业大学ACM基地2022年大培训试题题解:第四周F题
问题描述
给两个数字 a , b,求出a+b,其中(1<= a,b<=10^{500} )(1<=a,b<=10500)。(本题请使用C/C++编程,只用py的同学可以忽略本题)
输入
输入为两行,分别为数字 a 和 b
输出
输出为一行,计算后的结果
输入样例 1
10011
20022
输出样例 1
30033
题解
题解1
因数据超出数据类型所能储存的最大值,利用整型直接计算会产生数值溢出导致结果错误。常规思路是使用数组,模拟加法对每位的数进行运算。
题解2
开数组时,只能预先确定维度大小。为了使维度和当前运算相适应,节省时空,将数组改为动态数组。
源代码
// UOJ W4-F-2
#include <iostream>
#include <vector>
using namespace std;
vector<int> add(vector<int> &A, vector<int> &B)
{
vector<int> C;
if (A.size() < B.size())
return add(B, A);
int r = 0;
for (int i = 0; i < A.size(); ++i)
{
r += A[i];
if (i < B.size())
r += B[i];
C.push_back(r % 10);
r /= 10;
}
if (r)
C.push_back(r);
return C;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
vector<int> A, B;
string a, b;
cin >> a >> b;
for (int i = a.size() - 1; i >= 0; --i)
A.push_back(a[i] - '0');
for (int i = b.size() - 1; i >= 0; --i)
B.push_back(b[i] - '0');
auto C = add(A, B);
for (int i = C.size() - 1; i >= 0; --i)
cout << C[i];
return 0;
}
分析
复杂度:空间 $O\left(n\right)$,时间 $O\left(4n\right)$
评测结果:时间: 4ms
内存: 4MB