# APCS實作題2023年1月第2題：造字程式 > 日期：2023年9月27日 > 作者：王一哲 > 題目來源：112年1月實作題第2題 > [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=j606) <br /> ## 題目 ### 問題描述 有一個長度 $K$ 的的初始字串 $S$，每個字元都是小寫的英文字母。 接下來有 $Q$ 次的修改，每次的修改會把舊的字串重新排列成一個新的字串。 更具體來講，每次修改時會給一個 $1$ ~ $K$ 的排列 $P = [P_1, P_2, \dots, P_K]$，要將舊字串的第 $i$ 的字元複製到新字串的第 $P_i$ 個字元。 例子： - 若舊字串是 "abac"，且 $P = [4, 1, 3, 2]$，可以得到新字串 "bcaa"。 - 若舊字串是 "bcaa"，且 $P = [1, 2, 3, 4]$，可以得到新字串 "bcaa"。 - 若舊字串是 "bcaa"，且 $P = [2, 3, 4, 1]$，可以得到新字串 "abca"。 在 $Q$ 的修改中，每次修改出來的新字串會被當成下一次修改中的舊字串，而第一次修改時使用的舊字串就是初始字串。 題目另外會給一個數字 $R$，請依照下面定義的順序輸出 $R$ 行，每行 $Q$ 個字元 - 輸出操作 $1$ ~ $Q$ 的新字串的第 $1$ 個字元 - 輸出操作 $1$ ~ $Q$ 的新字串的第 $2$ 個字元 - ... - 輸出操作 $1$ ~ $Q$ 的新字串的第 $R$ 個字元 <br /> ### 輸入說明 第一行有三個整數 $K, Q, R$ 第二行是長度 $K$ 的初始字串 接下來有 $Q$ 行，每行有是一個 $1$ ~ $K$ 的排列 - 60%：$R = 1, 1 \leq K, Q \leq 20$ - 40%：$1 \leq R \leq K \leq 20, 1 \leq Q \leq 20$ <br /> ### 輸出說明 請依照題目敘述輸出 $R \times Q$ 個字元 <br /> ### 範例一：輸入 ``` 5 4 1 abcde 2 1 3 5 4 5 1 2 4 3 4 1 2 3 5 3 1 4 5 2 ``` ### 範例一：正確輸出 ``` bacd ``` <br /> ### 範例二：輸入 ``` 4 3 4 abac 4 1 3 2 1 2 3 4 2 3 4 1 ``` ### 範例二：正確輸出 ``` bba ccb aac aaa ``` <br /> ## Python 程式碼 於 ZeroJudge 測試結果，最長運算時間約為 21 ms，使用記憶體最多約為 3.3 MB，通過測試。 ```python= K, Q, R = map(int, input().split()) # 讀取 K, Q, R sp = list(input()) # 讀取初始字串並存成元素為字元的串列 sp sc = [""]*K # 儲存新字串內容的串列 sc data = ["" for _ in range(K)] # 儲存每次操作第1 ~ K個字元的串列 for _ in range(Q): # Q 次操作 pos = list(map(int, input().split())) # 依序讀取操作內容 for i in range(K): sc[pos[i]-1] = sp[i] # 取出 sp 對應的字元放入 sc 對應的位置 for i in range(K): data[i] += sc[i] # 依序讀取 sc 的字元，加到 data 中每個字串最後面 sp = sc.copy() # 更新 sp 的內容，要用 copy() 複製串列內容 for i in range(R): print(data[i]) # 印出答案 ``` <br /><br /> ## C++ 程式碼 於 ZeroJudge 測試結果，最長運算時間約為 8 ms，使用記憶體最多約為 348 kB，通過測試。 ```cpp= #include <iostream> #include <string> using namespace std; int main() { int K, Q, R; cin >> K >> Q >> R; // 讀取 K, Q, R string sp; cin >> sp; // 讀取初始字串 sp string sc = sp; // 儲存新字串為 sc string data[K]; // 儲存每次操作第1 ~ K個字元的字串陣列 for(int i=0; i<Q; i++) { // Q 次操作 int pos[K]; for(int j=0; j<K; j++) cin >> pos[j]; // 依序讀取操作內容 for(int j=0; j<K; j++) sc[pos[j]-1] = sp[j]; // 取出 sp 對應的字元放入 sc 對應的位置 for(int j=0; j<K; j++) data[j] += sc[j]; // 依序讀取 sc 的字元，加到 data 中每個字串最後面 sp = sc; // 更新 sp 的內容 } for(int i=0; i<R; i++) cout << data[i] << endl; // 印出答案 return 0; } ``` <br /><br /> --- ###### tags:`APCS`、`Python`、`C++`