Editorial for 造字程式 (APCS 2023-01 中級)

簡潔題意

長度 \(K\) 的小寫字串 \(S\)，做 \(Q\) 次操作。每次操作給一個 \(1 \sim K\) 的排列 \(P\)：舊字串第 \(i\) 個字元搬到新字串第 \(P_i\) 個位置，新字串就是下一次的舊字串。對前 \(R\) 個位置各輸出一行：第 \(j\) 行是第 \(1\) 次到第 \(Q\) 次操作後，新字串第 \(j\) 個位置的字元依序接起來（\(1 \le R \le K \le 20\)、\(1 \le Q \le 20\)）。

依正確通過的測試資料筆數給分，其中：

  • 子題組 1（\(60\) 分）：\(R = 1\)。
  • 子題組 2（\(40\) 分）：無額外限制。

先拿下子題組 1（60 分）：照排列搬字元，每次只記第一格

一次操作就是「搬家」：舊字串的第 \(i\) 格搬到新字串的第 \(P_i\) 格。兩件事要注意：

  1. 要開一條新字串，不能在原字串上直接搬。搬的時候目的地的舊字元可能還沒被搬走就被蓋掉了——跟 \(s\) 同長度、先填滿空白的 string next(K, ' ')（10.7 的「\(n\) 個同一字元」初始化）就是那條新字串。
  2. 題目的位置從 \(1\) 數、C++ 的索引從 \(0\) 數（上冊 6.3）：第 \(P_i\) 個位置是 next[p - 1]。排列的數字不用先存成陣列，讀一個搬一個就好。

搬完 s = next; 整條複製過去（10.6），新字串就變成下一次操作的舊字串。\(R = 1\) 時只要記第一格：每次操作完把 s[0] 接到答案 line 後面（10.8 的 +=），\(Q\) 次做完印出來，剛好長度 \(Q\)。

#include <iostream>
#include <string>
using namespace std;

int main() {
    int K, Q, R;
    string s;
    cin >> K >> Q >> R >> s;        // 子題組 1 保證 R = 1：只要記第 1 個位置

    string line = "";               // 每次操作後第 1 個位置的字元，依序接起來
    for (int q = 0; q < Q; q++) {
        string next(K, ' ');        // 新字串：先開好 K 格
        for (int i = 0; i < K; i++) {
            int p;
            cin >> p;
            next[p - 1] = s[i];     // 舊字串第 i 格（0-base）搬到新字串第 p 個（1-base）
        }
        s = next;                   // 新字串變成下一次操作的舊字串
        line += s[0];
    }
    cout << line << '\n';
    return 0;
}

拿範例 1 對一次：abcde 經過四次操作依序是 baced、acdeb、cdeab、dbcea，第一格依序 b、a、c、d。這份程式交上去，範例 2 和子題組 2 會 WA（只印了一行）——這是正常的，逐筆給分之下子題組 1 的 \(60\) 分穩穩到手。

從 60 分到 100 分：每個位置各一條字串

題目要的輸出是「直的」：每次操作產生一條新字串（橫的），但第 \(j\) 行要的是第 \(j\) 個位置跨越 \(Q\) 次操作的字元。所以不能每次操作印一行，要先收集：開 \(R\) 條字串 rows[0] ~ rows[R-1]（vector<string>，10.7 的 string 陣列），每次操作完把 s[j] 接到 rows[j] 後面，最後一行一條印出來。子題組 1 的 line 就是 rows[0]。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    int K, Q, R;
    string s;
    cin >> K >> Q >> R >> s;

    vector<string> rows(R);         // rows[j]＝第 j 個位置每次操作後的字元，依序接起來
    for (int q = 0; q < Q; q++) {
        string next(K, ' ');        // 新字串：先開好 K 格
        for (int i = 0; i < K; i++) {
            int p;
            cin >> p;
            next[p - 1] = s[i];     // 舊字串第 i 格（0-base）搬到新字串第 p 個（1-base）
        }
        s = next;                   // 新字串變成下一次操作的舊字串
        for (int j = 0; j < R; j++) rows[j] += s[j];
    }
    for (int j = 0; j < R; j++) cout << rows[j] << '\n';
    return 0;
}

運算量：\(Q \le 20\) 次操作、每次搬 \(K \le 20\) 格，小到不用算。

測過再交：範例 2 剛好 R = K

範例 1 只看第一格、範例 2 是 \(R = K = 4\)（每一格都要印）——「只印前 \(R\) 行、\(R\) 比 \(K\) 小」的二維情況兩個範例都沒有。補幾筆手算得動的：

輸入 正確輸出 這一筆在測什麼
3 2 2 ／ abc ／ 2 3 1 ／ 2 3 1 cb ／ ac \(R < K\) 的二維；同一個排列做兩次，第二次要從第一次的結果繼續（新字串沒存回去的程式印 cc／aa；搬的方向反了的程式印 bc／ca）
4 2 3 ／ abcd ／ 1 2 3 4 ／ 4 3 2 1 ad ／ bc ／ cb 恆等排列不動、再整串反過來；\(K = 4\) 但只印 \(R = 3\) 行
2 1 2 ／ ab ／ 2 1 b ／ a \(Q = 1\)：每行只有一個字元
1 3 1 ／ z ／ 1 ／ 1 ／ 1 zzz \(K = 1\)：怎麼搬都是自己

四筆都親眼看過正確，這題就穩了。

常犯錯誤
  • 搬的方向反了（寫成 next[i] = s[p - 1]）：題目是「舊的第 \(i\) 個搬到新的第 \(P_i\) 個」——範例 1 印 bdeb（該印 bacd）。
  • 在原字串上直接搬：還沒搬走的字元先被蓋掉——範例 1 印 aaca。
  • 忘了 \(1\)-base 轉 \(0\)-base（next[p] = s[i]）：第 \(K\) 個位置寫到字串外面、第 \(0\) 格永遠是空白——範例 1 印出一串空白。
  • 新字串沒存回 s：每次都拿原始字串在搬——範例 1 印 bbbb。
  • 每次操作印一行（橫的）：題目要每個位置一行（直的）——範例 1 印成四行 b／a／c／d。
  • 只記最後一次操作的結果：範例 1 印 d。