题意

给定两个大非负整数，求他们的和

限制：整数长度不大于10000

方法

python3

python自带高精度处理, 直接用python计算即可

代码

while True:
    try:
        print(int(input())+int(input()))
    except:
        break

复杂度分析

时间复杂度: 读入和计算，全是线性的，所以总时间复杂度为$O(n)O(n)$

空间复杂度: 主要耗在读入上$O(n)O(n)$

模拟

我们模拟逐步计算加法，注意进位。

以样例数据为例子9876543210+1234567890

我们先补充1个前导零再加09876543210+01234567890

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);i++)


int main(){
    char v0[10010];
    char v1[10010];
    while(~scanf("%s",v0+1)){
        scanf("%s",v1+1);
        v0[0] = v1[0] = '0'; // 前导零
        int l0 = strlen(v0);
        int l1 = strlen(v1);
        char *p0 = v0;
        char *p1 = v1;
        if(l0 < l1){ // 保证 p1 不大于 p0, 且 p1 加入 p0
            swap(p0,p1);
            swap(l0,l1);
        }
        int r = 0;
        int i = 0;
        while( i < l1 || r != 0 ){
            r += (l0-1-i >= 0 ? p0[l0-1-i]-'0':0)+(l1-1-i>=0?p1[l1-1-i]-'0':0); // 数值加法
            p0[l0-1-i] = '0' + (r%10); // 结果
            r /=10; // 进位
            i++;
        }
        printf("%s\n",p0+(p0[0] == '0')); // 判断前导零
    }
    return 0;
}

复杂度分析

时间复杂度: 对于每个计算我们最坏情况，和最大长度相关，所以空间复杂度为$O(n)O(n)$

空间复杂度: 我们主要消耗在原始数据的读入和处理上，空间复杂度为$O(n)O(n)$