程式解題社網站 程式解題社網站上線了！
NTUCPC OJ 現在支援 Rust ！
NTUCPCPC 2026 初賽 & 決賽題目已公開！ 連結
YTP 2026 題目已公開！ 連結
1492 . 粒子合成
TopCoder
Tags
Description
這個世界上有 $n$ 種粒子，依序以前 $n$ 個大寫英文字母表示（$\texttt{A}, \texttt{B}, \texttt{C}, \dots$）。物理學家整理出了一張合成表 $G$，歸納粒子合成的規律：對每一種粒子 $x$，將相鄰的兩個粒子 $x$ 合成之後，會得到一個粒子 $G(x)$（同樣是這 $n$ 種粒子之一）。
除了粒子之外，自然界中還存在一種「親和場」。親和場會圈住軌道上連續的一段區域，使場內的粒子親和性大幅提高，因此場內的粒子必須先彼此合成完畢，才會與場外的粒子發生反應。每個親和場以一對標記 (、) 框出它的左右邊界。任意兩個親和場不會只有部分重疊，也就是說它們要嘛互不相交，要嘛其中一個完全包含於另一個之內。
你正在操作一台粒子合成裝置。裝置的軌道上由左到右排著一列共 $m$ 個元素，每一個元素要嘛是一個粒子，要嘛是某個親和場的邊界。
對於一段不含親和場的粒子序列，我們定義「化簡」：只要序列中存在相鄰且相同的兩個粒子 $x$，就取位置最靠右的那一對，把這兩個粒子一起替換成單一個 $G(x)$；不斷重複此動作，直到序列中不再有任何相鄰且相同的粒子為止。
我們以下列方式定義最終的合成結果：
- 取任何一個「最內層」的親和場（即它的內部不再含有其他親和場），把場內的粒子序列 化簡。化簡完成後，這個場便消散，化簡後的內容留在原本的位置。
- 重複步驟 1，直到整列中不再有任何親和場為止。
- 最後，把整列剩下的粒子序列再化簡一次。
此時的序列便為最終的合成結果。
Input Format
第一行有兩個整數 $n$ 與 $m$。
第二行為一個長度為 $n$ 的字串 $G(p_1)G(p_2)\dots G(p_n)$，其中 $p_i$ 為第 $i$ 種粒子。
第三行有一個長度為 $m$ 的字串，由左到右描述整列；每個字元為一個大寫英文字母（代表一個粒子），或是字元 ( 或 )（代表親和場的邊界標記）。
- $1 \leq n \leq 26$
- $1 \leq m \leq 2 \times 10^ 5$
- 所有親和場的邊界標記皆合法配對
- 每一個親和場內至少含有一個粒子
Output Format
輸出一行字串，為合成後由左到右的粒子序列。
Sample Input 1
2 3 BA AAA
Sample Output 1
AB
Sample Input 2
2 5 BA (AA)A
Sample Output 2
BA
Sample Input 3
2 4 BA AAAA
Sample Output 3
A
Hints
範測 1 解釋：
合成表為 $G(\texttt{A})=\texttt{B},\ G(\texttt{B})=\texttt{A}$，序列為 AAA，沒有親和場。化簡時取最右邊的相鄰相同對（第 $2$、$3$ 個粒子）合成為 $G(\texttt{A})=\texttt{B}$，序列變成 AB，已沒有相鄰相同的粒子，故輸出 AB。
範測 2 解釋：
序列為 (AA)A，其中 (AA) 是一個親和場。先讓場內的 AA 化簡為 $G(\texttt{A})=\texttt{B}$，場消散後整列變成 BA，已無法再合成，故輸出 BA。
範測 3 解釋：
合成表為 $G(\texttt{A})=\texttt{B},\ G(\texttt{B})=\texttt{A}$，序列為 AAAA。取最右一對（第 $3$、$4$ 個）合成為 B，得 AAB；再取最右的相鄰相同對（第 $1$、$2$ 個）合成為 B，得 BB；最後 BB 合成為 $G(\texttt{B})=\texttt{A}$，得 A。整個過程是一連串的連鎖合成，最終只剩一個粒子，故輸出 A。
Problem Source
2026 YTP 國中組決賽 p4
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測試資料 | 0 |
| 2 | 3~16 | 序列中不含任何親和場 | 3 |
| 3 | 17~38 | $m \le 3000$ | 5 |
| 4 | 0~52 | 無額外限制 | 7 |