Editorial for 字串解碼 (APCS 2022-06 中級)


簡潔題意

一次轉換 \(t = f(s, e)\):\(s\) 是大寫字母字串、\(e\) 是同長度的 \(0/1\) 字串。第一步:\(e\) 裡 \(1\) 的個數是奇數就把 \(s\) 前後兩半對調(長度奇數時正中間的字元不動),偶數就不動。第二步:依序看 \(e[i]\),是 \(0\) 就從 \(s\) 的最前面拿一個字元當 \(t[i]\),是 \(1\) 就從最後面拿。編碼=用編碼表 \(e_0, e_1, \ldots, e_{m-1}\) 依序轉換 \(m\) 次。給你編碼表和編碼後的字串,求原始字串(\(m, n \le 100\))。

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

  • 子題組 1(\(60\) 分):\(m = 1\)。
  • 子題組 2(\(40\) 分):無額外限制。

先拿下子題組 1(60 分):一張表,把兩步倒著走回去

題目描述的是編碼,要我們做的是解碼——把 \(f\) 倒著做。編碼是「先對調、再一個一個拿」,解碼就反過來:先把拿走的放回去,再對調回來

倒推第二步(放回去)。 看 \(t\) 的每個位置 \(i\):e[i]0 的那些字元,當初是從 \(s\) 前面依序拿走的——所以它們照原順序排在 \(s\) 的前段;e[i]1 的那些是從後面拿走的,最早拿的是 \(s\) 的最後一個字,所以越晚拿到的越靠前。程式就是兩條字串 frontback0 的字元 front += t[i] 接在後面,1 的字元 back = t[i] + back 接在前面string+ 串接,10.8;一個 char 也能直接跟 string 相加),掃完 front + back 就是拿走之前的 \(s\)。掃的時候順便數 \(1\) 有幾個。

倒推第一步(對調回來)。 對調兩次等於沒動,所以當初有對調(\(1\) 的個數是奇數)就再對調一次:長度偶數時 s.substr(half) + s.substr(0, half)——後半接前半;長度奇數時中間那個字元 s[half] 要留在中間,前後兩半各長 halfsubstr10.8 的取子字串,只給起點就一路取到結尾。

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

int main() {
    int m, n;
    cin >> m >> n;                  // 子題組 1 保證 m = 1:只有一張編碼表
    string e, t;
    cin >> e >> t;                  // e 是 0/1 字串,t 是收到的訊息

    // 倒推第二步:e[i] 是 0 的字元當初是從前面拿走的,照順序放回前面;
    //             e[i] 是 1 的字元是從後面拿走的,越晚拿的越靠前,所以一個個接到 back 的前面
    string front = "", back = "";
    int ones = 0;
    for (int i = 0; i < n; i++) {
        if (e[i] == '0') {
            front += t[i];
        } else {
            back = t[i] + back;
            ones++;
        }
    }
    string s = front + back;

    // 倒推第一步:1 的個數是奇數,當初前後半對調過,再對調一次就回來了
    if (ones % 2 == 1) {
        int half = n / 2;
        if (n % 2 == 0) {
            s = s.substr(half) + s.substr(0, half);
        } else {
            s = s.substr(half + 1) + s[half] + s.substr(0, half);   // 正中間的字元留在原地
        }
    }
    cout << s << '\n';
    return 0;
}

拿範例 1 對一次:CABAD10110——front 收到 ADback 倒著收 CBA 變成 ABC,拼起來 ADABC;\(1\) 有三個、對調回來 BCAAD。這份程式交上去,範例 2 和子題組 2 會 WA——這是正常的,逐筆給分之下子題組 1 的 \(60\) 分穩穩到手。

從 60 分到 100 分:m 張表從最後一張倒著解

編碼表有 \(m\) 張:\(s_0\) 用 \(e_0\) 變 \(s_1\)、再用 \(e_1\) 變 \(s_2\)……最後 \(e_{m-1}\) 變成收到的 \(s_m\)。解碼時最後做的要最先解:先用 \(e_{m-1}\) 把 \(s_m\) 解回 \(s_{m-1}\),再用 \(e_{m-2}\)……一路解到 \(s_0\)。所以迴圈要從 m - 1 倒著跑到 0

子題組 1 那段「解一張表」的程式原封不動搬進一個函式 decode(t, e)(上冊 7.1),參數用 const string& 傳參考、不複製(10.6);編碼表用 vector<string> 一次讀進來(10.7 的 string 陣列),主程式就只剩一個倒著跑的迴圈。

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

// 把一次轉換 t = f(s, e) 倒推回去:給轉換後的 t 和編碼表 e,回傳轉換前的 s
string decode(const string& t, const string& e) {
    int n = (int)t.size();
    string front = "", back = "";
    int ones = 0;
    for (int i = 0; i < n; i++) {
        if (e[i] == '0') {
            front += t[i];          // 從前面拿走的,照順序放回前面
        } else {
            back = t[i] + back;     // 從後面拿走的,越晚拿的越靠前
            ones++;
        }
    }
    string s = front + back;
    if (ones % 2 == 1) {            // 當初前後半對調過:再對調一次
        int half = n / 2;
        if (n % 2 == 0) {
            s = s.substr(half) + s.substr(0, half);
        } else {
            s = s.substr(half + 1) + s[half] + s.substr(0, half);
        }
    }
    return s;
}

int main() {
    int m, n;
    cin >> m >> n;
    vector<string> table(m);        // 編碼表 e[0] ~ e[m-1]
    for (int j = 0; j < m; j++) cin >> table[j];
    string s;
    cin >> s;                       // 收到的訊息 s[m]

    for (int j = m - 1; j >= 0; j--) {   // 從最後一次轉換倒著解回去
        s = decode(s, table[j]);
    }
    cout << s << '\n';
    return 0;
}

運算量:每張表掃一遍 \(n\) 個字元、substr 再抄一遍,\(m \le 100\) 張總共不到 \(10^5\) 步。

測過再交:範例 1 是奇數長度,範例 2 是三張表

範例 1 只有一張表但長度是奇數;範例 2 長度偶數、有對調,卻是三張表——子題組 1 的程式沒有任何一筆「偶數長度」的範例可以驗。自己補:

輸入 正確輸出 這一筆在測什麼
1 41000BCDA ABCD 偶數長度+奇數個 \(1\) 的對調,\(m = 1\):子題組 1 版就能驗
1 3111XYZ XYZ 全是 \(1\):先對調、再從後面拿三次=整串反過來,結果看起來像沒動。從後面拿的字元沒反過來接的程式印 ZYX;忘了對調的也印 ZYX
1 11Z Z 長度 \(1\):對調時「正中間不動」剛好就是整串
2 3001010ABC ACB 兩張表、手算得動:先用 010 解回 BCA,再用 001 解回 ACB。順著 \(e_0\) 先解的程式印 BAC;一張表內「先對調再放回」順序反了的程式也印 BAC

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

常犯錯誤
  • 編碼表順著解(從 \(e_0\) 開始):範例 1 只有一張表、照樣過;範例 2 印 EWYQRT(該印 QWERTY);自測表第 4 列印 BAC
  • 一張表內倒推順序反了(先對調、再放回去):範例 1 印 DACBA;範例 2 剛好過;自測表第 4 列印 BAC
  • 從後面拿走的字元沒反過來接back += t[i]):範例 1 印 BACAD;自測表第 2 列印 ZYX
  • 忘了對調回來,或奇偶判斷反了:範例 1 印 ADABC
  • 奇數長度時把正中間的字元也搬走:範例 1 印 ABCAD;範例 2 長度偶數抓不到。
  • 照編碼方向做(寫了 \(f\) 而不是它的反函式):範例 1 印 AACBD