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\) 的最後一個字,所以越晚拿到的越靠前。程式就是兩條字串 front、back:0 的字元 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] 要留在中間,前後兩半各長 half。substr 是 10.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 對一次:CABAD 配 10110——front 收到 A、D,back 倒著收 C、B、A 變成 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 4 / 1000 / BCDA |
ABCD |
偶數長度+奇數個 \(1\) 的對調,\(m = 1\):子題組 1 版就能驗 |
1 3 / 111 / XYZ |
XYZ |
全是 \(1\):先對調、再從後面拿三次=整串反過來,結果看起來像沒動。從後面拿的字元沒反過來接的程式印 ZYX;忘了對調的也印 ZYX |
1 1 / 1 / Z |
Z |
長度 \(1\):對調時「正中間不動」剛好就是整串 |
2 3 / 001 / 010 / ABC |
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。