题解：超大整数加法

题意分析

题目要求我们计算两个超大整数（最多$1,000,000$位）的和。输入给出两个数的每一位数字，输出它们的和。需要注意：

1. 两个数的位数相同（可能补前导零）
2. 和的位数不超过$N$
3. 需要处理进位问题

解题思路

1. 逐位相加：从最低位开始，逐位相加并处理进位
2. 进位处理：当前位和≥$10$时，向高位进位$1$
3. 结果存储：将计算结果逆序存储，最后再反转输出

实现步骤

1. 输入处理：读取两个数的每一位数字
2. 从低位到高位计算：
   • 对应位相加
   • 处理进位
3. 结果处理：
   • 将结果数字反转
   • 输出最终结果

代码注释

#include<iostream>
#include<cstring>  // 用于memset函数
#include<cstdio>   // 用于scanf/printf
#include<cstdlib>  // 标准库头文件
#include<map>      // 未使用，可移除
#include<algorithm>// 未使用，可移除
#include<queue>    // 未使用，可移除
#define ll long long
#define inf 0x3f3f3f3f  // 未使用，可移除

using namespace std;

int a[1000010], b[1000010];  // 存储两个大数的各位数字
char s[1000010], s1[1000010]; // s存储中间结果，s1存储最终结果

int main() {
    int n;
    scanf("%d", &n);  // 读取数字位数N
    
    // 初始化数组为0
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    
    // 读取两个大数的每一位数字
    for(int i = 1; i <= n; i++) {
        scanf("%d%d", a+i, b+i);  // 同时读取两个数的第i位
    }
    
    int l = 0;  // 记录结果长度
    // 从最低位(第n位)到最高位(第1位)计算
    for(int i = n; i >= 1; i--) {
        int j = a[i] + b[i];  // 当前位相加
        
        if(j >= 10) {  // 需要进位
            s[l++] = (j % 10) + '0';  // 存储个位数
            if(i >= 2) {
                b[i-1] += 1;  // 向高位进位
            }
        } else {  // 不需要进位
            s[l++] = j + '0';  // 直接存储结果
        }
    }
    
    // 将结果反转（因为我们是逆序计算的）
    int t = 0;
    for(int i = l-1; i >= 0; i--) {
        s1[t++] = s[i];
    }
    s1[t] = '\0';  // 字符串结束符
    
    printf("%s\n", s1);  // 输出结果
    return 0;
}

复杂度分析

1. 时间复杂度：$O(N)$
   • 需要遍历所有位数两次（计算和反转）
2. 空间复杂度：$O(N)$
   • 需要存储两个输入数和结果