T1. 波蘭表達式

題目鏈接：SOJ D1087

此題為 2023 年 12 月三級第三題原題，見 2023 年 12 月青少年軟編等考 C 語言三級真題解析中的 T3。

T2. 多項式相加

題目鏈接：SOJ D1088

我們經常遇到兩多項式相加的情況，在這里，我們就需要用程序來模擬實現把兩個多項式相加到一起。首先，我們會有兩個多項式，每個多項式是獨立的一行，每個多項式由系數、冪數這樣的多個整數對來表示。

如多項式 $2x^{20}?x^{17}+5x^9?7x^7+16x^5+10x4+22x^2?15$，對應的表達式為：2 20 -1 17 5 9 -7 7 16 5 10 4 22 2 -15 0。

為了標記每行多項式的結束，在表達式后面加上了一個冪數為負數的整數對。同時輸入表達式的冪數大小順序是隨機的。我們需要做的就是把所給的兩個多項式加起來。

時間限制：1 s
內存限制：64 MB

• 輸入
  輸入包括多行。
  第一行整數 $n$，表示有多少組的多項式需要求和，$1<n<100$。
  下面為 $2n$ 行整數，每一行都是一個多項式的表達式。表示 $n$ 組需要相加的多項式。每行長度小于 $300$。
• 輸出
  輸出包括 $n$ 行，每行為 $1$ 組多項式相加的結果。在每一行的輸出結果中，多項式的每一項用 [x y] 形式的字符串表示，$x$ 是該項的系數、$y$ 是該項的冪數。要求按照每一項的冪從高到低排列，即先輸出冪數高的項、再輸出冪數低的項。 系數為零的項不要輸出。
• 樣例輸入

  2
  -1 17 2 20 5 9 -7 7 10 4 22 2 -15 0 16 5 0 -1
  2 19 7 7 3 17 4 4 15 10 -10 5 13 2 -7 0 8 -8
  -1 17 2 23 22 2 6 8 -4 7 -18 0 1 5 21 4 0 -1
  12 7 -7 5 3 17 23 4 15 10 -10 5 13 5 2 19 9 -7
  

• 樣例輸出

  [ 2 20 ] [ 2 19 ] [ 2 17 ] [ 15 10 ] [ 5 9 ] [ 6 5 ] [ 14 4 ] [ 35 2 ] [ -22 0 ]
  [ 2 23 ] [ 2 19 ] [ 2 17 ] [ 15 10 ] [ 6 8 ] [ 8 7 ] [ -3 5 ] [ 44 4 ] [ 22 2 ] [ -18 0 ]
  

• 提示
  第一組樣例數據的第二行末尾的 8 -8，因為冪次 $?8$ 為負數，所以這一行數據結束，8 -8不要參與計算。

思路分析

此題考查模擬算法，屬于基礎題。

可以用結構體存儲多項式中每一項的系數和指數，然后將兩個多項式分別按照指數非遞增的順序進行排序。接下來采用雙指針依次遍歷兩個多項式，對于每一個指數，需要做的就是合并同類項：

• 如果 $poly\_a_i$ 的系數與 $poly\_b_j$ 的指數相等，則將兩個多項式中與當前指數相等的所有項（同類項）的系數都累加起來；
• 如果 $poly\_a_i$ 的指數大于 $poly\_b_j$，則將多項式 $poly\_a$ 中與當前指數相等的所有項的系數累加起來；
• 如果 $poly\_a_i$ 的指數小于 $poly\_b_j$，則將多項式 $poly\_b$ 中與當前指數相等的所有項的系數累加起來；

每個指數對應的系數累加完畢之后，檢測當前系數是否為 $0$，如果不為 $0$，則輸出當前項的系數和指數。

/** Name: T2_1.cpp* Problem: 多項式相加* Author: Teacher Gao.* Date&Time: 2025/03/07 22:47*/#include <bits/stdc++.h>using namespace std;struct node {int x, y;node () {}node (int _x, int _y) : x(_x), y