HDU 1047 Integer Inquiry：大整數加法多組求和

題目大意

輸入 T 組測試資料。每組包含多行大整數（每行 ≤ 200 位），以單行 0 結束該組。輸出每組所有大整數之和，組之間空行分隔。

高精度加法設計

• 同 HDU 1042，十進制低位在前陣列 data[200]。
• 支援 operator= (char*)、operator+ (BigNumber&)、print()。
• 加法核心：逐位相加 + 進位，迴圈條件 q || i<len || j<a.len 同時處理兩數長度不同與最高位進位。

核心加法實作

BigNumber BigNumber::operator+(BigNumber& a) {
    BigNumber z;
    int q = 0, i = 0, j = 0;
    for (; q || i < len || j < a.len; ++i, ++j) {
        int p = data[i] + a.data[j] + q;
        z.data[i] = p % 10;
        q = p / 10;
    }
    z.len = i;
    while (z.len > 1 && !z.data[z.len - 1]) --z.len;
    return z;
}

主程式流程

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        BigNumber ans = "0";  // 關鍵：每組重新歸零
        char s[200];
        while (scanf("%s", s) == 1) {
            if (s[0] == '0' && s[1] == '\0') break;  // 遇單獨 0 結束組
            ans = ans + BigNumber(s);
        }
        ans.print();
        if (T) printf("\n");  // 組間空行
    }
    return 0;
}

關鍵避坑點（原碼註釋）

1. 賦值運算子必須 memset(data,0,sizeof(data))：否則上一組殘留數據導致錯誤（原碼標註 ① 處）。
2. 每組開始前 ans = "0" 重置：避免跨組累加。
3. 輸入結束判斷：s[0]=='0' && s[1]=='\0' 精確匹配單獨「0」行，避免誤判「10」、「100」等。

完整優化代碼（C++11）

#include <cstdio>
#include <cstring>

const int NMAX = 200;

struct BigNumber {
    int data[NMAX];
    int len;
    BigNumber() : len(1) { memset(data, 0, sizeof(data)); }
    BigNumber(const char* str) { *this = str; }
    BigNumber& operator=(const char* str) {
        memset(data, 0, sizeof(data));  // 必須清零
        len = strlen(str);
        for (int i = 0; i < len; ++i)
            data[i] = str[len - i - 1] - '0';
        return *this;
    }
    BigNumber operator+(const BigNumber& a) const {
        BigNumber z;
        int q = 0, i = 0, j = 0;
        for (; q || i < len || j < a.len; ++i, ++j) {
            int p = data[i] + a.data[j] + q;
            z.data[i] = p % 10;
            q = p / 10;
        }
        z.len = i;
        while (z.len > 1 && !z.data[z.len - 1]) --z.len;
        return z;
    }
    void print() const {
        for (int i = len - 1; i >= 0; --i) putchar('0' + data[i]);
        putchar('\n');
    }
};

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        BigNumber ans = "0";
        char s[NMAX];
        while (scanf("%s", s) == 1) {
            if (s[0] == '0' && s[1] == '\0') break;
            ans = ans + BigNumber(s);
        }
        ans.print();
        if (T) putchar('\n');
    }
    return 0;
}

複雜度與測試

• 單次加法 O(位數)，位數 ≤ 200，極快。
• 總時間 O(T × 數量 × 位數)，輕鬆通過。
• 測試樣例：

Input:
2
123
456
0
99999999999999999999
1
0

Output:
579

100000000000000000000

結語

HDU 1047 是高精度加法的純熟練度測試。核心模板與 HDU 1042 高度相似，關鍵差異在於「多組輸入、每組以 0 終止、組間空行」。掌握「清零賦值、進位迴圈條件、輸入邊界判斷」三大細節，即可穩健 AC。建議將高精度加/減/乘/除/比較封裝為統一 BigInt 庫，配合單元測試，構建個人算法工具箱。