d056 - 10013 - Super long sums
題目描述
題目要求計算兩個長度最長為 1,000,000 的數字的和。輸入包含多組測試案例，每組案例包含一個數字的長度 M，以及 M 行的數字對，每個數字對代表一個數字的一位。輸出為兩個數字的和，長度為 M。
解題思路
這題的核心在於處理大數加法。由於數字的長度可能很大，無法使用內建的整數類型來直接計算。因此，需要將數字儲存為字串，然後逐位進行加法運算。程式碼首先讀取數字的長度 M，然後讀取 M 行的數字對，將它們儲存到一個字串中。接著，從字串的最後一位開始，逐位進行加法運算。如果某一位的和超過 9，則將進位加到前一位。最後，輸出計算得到的和。
複雜度分析
- 時間複雜度: O(M)，其中 M 是數字的長度。因為程式碼需要遍歷字串的每一位來進行加法運算。
- 空間複雜度: O(M)，因為程式碼需要儲存字串。
程式碼
#include <iostream>
#include <string>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int w;
int n;
char b,c;
cin >> w;
while(w--){
cin >> n;
string a;
while(n--){
cin >> b >> c;
a+=b+c-48;
}
for(int i=a.length()-1;i>0;i--){
if(a[i]>'9'){
a[i]-=10;
a[i-1]++;
}
}
if(a[0]>'9'){
cout << '1';
a[0]-=10;
}
if(w!=0)
cout << a << "\n\n";
else
cout << a << "\n";
}
}