ZeroJudge 解題筆記：e806. 1.多項式計算 (Polynomial)

作者：王一哲
日期：2025年2月6日



ZeroJudge 題目連結：e806. 1.多項式計算 (Polynomial)

解題想法

這題用 Python 的 dict、defaultdict 或 C++ 的 map、unordered_map 比較方便。

Python 程式碼

使用時間約為 39 ms，記憶體約為 4.1 MB，通過測試。

from collections import defaultdict

n = int(input())  # 第一個多項式資料有 n 對數字
imax = 0  # 最高次方
line1 = list(map(int, input().split()))  # 第一個多項式資料
poly1 = defaultdict(int)  # 用字典儲存第一個多項式的次方、係數
for i in range(0, 2*n, 2):  # 依序由 line1 讀取資料，每次跳 2 格
    poly1[line1[i]] = line1[i+1]
    imax = max(imax, line1[i])
m = int(input())  # 第二個多項式資料有 m 對數字
line2 = list(map(int, input().split()))  # 第二個多項式資料
poly2 = defaultdict(int)  # 用字典儲存第一個多項式的次方、係數
for i in range(0, 2*m, 2):  # 依序由 line2 讀取資料，每次跳 2 格
    poly2[line2[i]] = line2[i+1]
    imax = max(imax, line2[i])
ans = [0]*(imax+1)  # 儲存答案用的串列，依序為 0 ~ imax 次項的係數
for i in range(imax+1):  # 依序讀取兩個多項式 0 ~ imax 次項的係數
    ans[i] = poly1[i] + poly2[i]
if all(ans[i] == 0 for i in range(imax+1)):  # 如果 ans 每項都是 0
    print("NULL!")  # 印出 NULL!
else:  # 否則依序印出次方及係數，若係數為 0 跳過此項
    for i in range(imax, -1, -1):  # 依序印出 imax 次方項 ~ 常數項
        if ans[i] != 0:
            print(f"{i:d}:{ans[i]:d}")

也可以使用預設的字典格式，但是從字典取值時，如果 key 值不存在會回傳錯誤訊息，程式碼第 16 到 19 行就是為了避免遇到這個問題。使用時間約為 23 ms，記憶體約為 3.8 MB，通過測試。

n = int(input())  # 第一個多項式資料有 n 對數字
imax = 0  # 最高次方
line1 = list(map(int, input().split()))  # 第一個多項式資料
poly1 = dict()  # 用字典儲存第一個多項式的次方、係數
for i in range(0, 2*n, 2):  # 依序由 line1 讀取資料，每次跳 2 格
    poly1[line1[i]] = line1[i+1]
    imax = max(imax, line1[i])
m = int(input())  # 第二個多項式資料有 m 對數字
line2 = list(map(int, input().split()))  # 第二個多項式資料
poly2 = dict()  # 用字典儲存第一個多項式的次方、係數
for i in range(0, 2*m, 2):  # 依序由 line2 讀取資料，每次跳 2 格
    poly2[line2[i]] = line2[i+1]
    imax = max(imax, line2[i])
ans = [0]*(imax+1)  # 儲存答案用的串列，依序為 0 ~ imax 次項的係數
for i in range(imax+1):  # 依序讀取兩個多項式 0 ~ imax 次項的係數
    if i not in poly1 and i not in poly2: ans[i] = 0  # 要排除 i 不在字典中的狀況
    elif i not in poly1: ans[i] = poly2[i]
    elif i not in poly2: ans[i] = poly1[i]
    else: ans[i] = poly1[i] + poly2[i]
if all(ans[i] == 0 for i in range(imax+1)):  # 如果 ans 每項都是 0
    print("NULL!")  # 印出 NULL!
else:  # 否則依序印出次方及係數，若係數為 0 跳過此項
    for i in range(imax, -1, -1):  # 依序印出 imax 次方項 ~ 常數項
        if ans[i] != 0:
            print(f"{i:d}:{ans[i]:d}")

C++ 程式碼

使用時間約為 4 ms，記憶體約為 456 kB，通過測試。

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;  // 第一個多項式資料有 n 對數字
    int imax = 0;  // 最高次方
    map<int, int> poly1, poly2;  // 用 map 儲存多項式的次方、係數
    for(int i=0; i<n; i++) {  // 讀取第一個多項式的次方、係數，更新 imax
        int p, c; cin >> p >> c;
        poly1[p] = c;
        imax = max(imax, p);
    }
    int m; cin >> m;  // 第二個多項式資料有 m 對數字
    for(int i=0; i<m; i++) {  // 讀取第二個多項式的次方、係數，更新 imax
        int p, c; cin >> p >> c;
        poly2[p] = c;
        imax = max(imax, p);
    }
    int ans[imax+1] = {0};  // 儲存答案用的陣列，依序為 0 ~ imax 次項的係數
    bool allzero = true;  // 相加後是否所有係數都是 0
    for(int i=0; i<=imax; i++) {  // 依序讀取兩個多項式 0 ~ imax 次項的係數
        ans[i] = poly1[i] + poly2[i];
        if (allzero && ans[i] != 0) allzero = false;  // 只要有任何一項係數不是 0，allzero 設定為 false
    }
    if (allzero) {  // 如果 ans 每項都是 0
        cout << "NULL!\n";  // 印出 NULL!
    } else {  // 否則依序印出次方及係數，若係數為 0 跳過此項
        for(int i=imax; i>=0; i--) {  // 依序印出 imax 次方項 ~ 常數項
            if (ans[i] != 0) cout << i << ":" << ans[i] << "\n";
        }
    }
    return 0;
}