e806 - 1.多項式計算 (Polynomial)
題目描述
題目要求實作一個程式，能夠計算兩個多項式的和。輸入包含兩個多項式，每個多項式由其項數和各項的次方與係數組成。程式需要將兩個多項式相加，並輸出結果多項式，以次方降冪排序。如果相加後的結果多項式為空（所有係數都為 0），則輸出 "NULL!"。
解題思路
此題的核心在於模擬多項式的加法。由於次方數的範圍有限 (0 到 1000)，可以使用一個陣列 a 來儲存多項式的係數，陣列的索引代表次方數。程式首先讀取第一個多項式，將其係數儲存在陣列 a 中。然後讀取第二個多項式，並將其係數加到陣列 a 中對應的次方項上。最後，遍歷陣列 a，輸出所有係數不為 0 的項，按照次方降冪排序。如果陣列 a 中所有係數都為 0，則輸出 "NULL!"。
複雜度分析
- 時間複雜度: O(N + M + K)，其中 N 是第一個多項式的項數，M 是第二個多項式的項數，K 是陣列的大小 (1002)。讀取輸入需要 O(N + M)，計算多項式和需要 O(K)，輸出結果需要 O(K)。
- 空間複雜度: O(K)，其中 K 是陣列的大小 (1002)。主要空間消耗來自於儲存多項式係數的陣列
a。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
using namespace std;
int a[1002],t,it,all;
inline int read(){
int a(0),r(1);
char c('0');
while(c>='0'&&c<='9'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
if(c=='-'){
r=-1;
c=getchar_unlocked();
}
}
return a*r;
}
inline void write(int x) {
if(x==0)putchar_unlocked('0');
int stk[9],*ptr(&stk[0]);
if(x<0){
putchar_unlocked('-');
x*=-1;
}
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
int main(){
t=read();
while(t--){
it=read();
a[it]=read();
}
t=read();
while(t--){
it=read();
a[it]+=read();
}
for(int i=1000;i>=0;--i){
if(a[i]){
all=1;
write(i);
putchar_unlocked(':');
write(a[i]);
putchar_unlocked('\n');
}
}
if(!all){
putchar_unlocked('N');
putchar_unlocked('U');
putchar_unlocked('L');
putchar_unlocked('L');
putchar_unlocked('!');
}
}