题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(压位) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<vector>
#include<string>
using namespace std;
const int base = 1e9;
vector<int> Add(vector<int>& A, vector<int>& B)
{
    if(A.size() < B.size())     return Add(B, A);
    int m = A.size(), n = B.size(), t = 0;
    vector<int> res;
    for(int i = 0; i < m; i++)
    {
        t += A[i];
        if(i < n)   t += B[i];
        res.push_back(t % base);
        t /= base;
    }
    if(t)   res.push_back(t);
    return res;
}

int main()
{
    string a, b;
    cin >> a >> b;
    vector<int> A, B;
    for(int i = a.size() - 1, j = 0, s = 0, t = 1; i >= 0; i--)
    {
        s += (a[i] - '0') * t;
        t *= 10, j++;
        if(i == 0 || j == 9)
        {
            A.push_back(s);
            j = s = 0;
            t = 1;
        }
    }
    for(int i = b.size() - 1, j = 0, s = 0, t = 1; i >= 0; i--)
    {
        s += (b[i] - '0') * t;
        t *= 10, j++;
        if(i == 0 || j == 9)
        {
            B.push_back(s);
            j = s = 0;
            t = 1;
        }
    }
    auto res = Add(A, B);
    cout << res.back();      //输出第一个存的数，有可能不足9位，所以先输出
    for(int i = res.size() - 2; i >= 0; i--)
    {
        printf("%09d", res[i]);  //必须按9位不足补0格式输出， 有的数字实际达不到9位，但是对应于结果里相当于在前面加0
    }
    return 0;
}