AcWing 791. 高精度加法

观察题目

第一眼看题：这不就是大淼题 /(/text {A + B}/) 吗？

再一看，看到数据范围 /(1 /leq 整数长度 /leq 100000/)，很显然，/(C++/) 中自带的数据类型肯定不行。

怎么办？

算法思路

观察到题目给出的整数长度数组存的下，因此我们可以先读入两个字符串，然后转成数组。

还记得小学一年级老师教的“列竖式”吗？

回想一下，列竖式有这样几个步骤：

1. 从最低位开始算起；
2. 首先把这一位对应的两个数字相加，如果相加的和 $ /geq 10$，则需要进位，让下一位 $ + 1$（这里注意如果有进位，在进行下一次操作时还要加上之前进位的值）；
3. 重复 /(2/) 操作。

同理，我们可以用代码模拟这个过程。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;

vector<int> add(vector<int> a, vector<int> b)
{
    int t = 0; //t存进位
    vector<int> c; //c存答案
    for (int i = 0; i < a.size() || i < b.size(); i ++ )
    {
        if (i < a.size())
        {
            t += a[i]; //这里要+=，加上上次的进位
        }
        if (i < b.size())
        {
            t += b[i]; //同上
        }
        c.push_back(t % 10);
        t /= 10;
    }
    if (t)
    {
        c.push_back(1);
    }
    return c;
}

int main()
{
    string x, y;
    cin >> x >> y;
    vector<int> a, b;
    //转数组
    for (int i = x.length() - 1; i >= 0; i -- )
    {
        a.push_back(x[i] - '0');
    }
    for (int i = y.length() - 1; i >= 0; i -- )
    {
        b.push_back(y[i] - '0');
    }
    auto z = add(a, b);
    for (int i = z.size() - 1; i >= 0; i -- )
    {
        printf("%d", z[i]);
    }
    return 0;
}

/(/text {Python}~yyds!/)

print(input() + input())