Editorial for 字串操作 (APCS 2025-01 中級)

簡潔題意

給一個長度為偶數的字串 \(S\)，依序執行 \(k\) 個操作：操作 \(0\)＝相鄰兩個一組、組內交換；操作 \(1\)＝相鄰兩個一組、組內由小到大；操作 \(2\)＝拆成前後兩半再交錯排列（完美重排）。輸出做完所有操作後的字串。（\(2 \le |S| \le 100\)、\(1 \le k \le 100\)）

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

  • 子題 1（\(60\) 分）：\(|S| \le 10\)、\(k = 1\)，且唯一的操作為操作 \(2\)。
  • 子題 2（\(40\) 分）：無額外限制。

先拿下子題組 1（60 分）：只做一次完美重排

子題組 1 保證 \(|S| \le 10\)、\(k = 1\)，而且唯一的操作一定是操作 \(2\)。所以只要會做完美重排就有 60 分，另外兩種操作可以先完全不管。

完美重排的做法：把字串分成前後兩半（各 \(n/2\) 個字元），開一個新的空字串，輪流把「前半的第 \(i\) 個、後半的第 \(i\) 個」接到後面。用 string（10.7）配 += 字串加法（10.8）：

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

int main() {
    string s;
    int k, op;
    cin >> s >> k >> op;   // 子題組 1 保證 k = 1 且 op 一定是 2

    int n = (int)s.size();
    string ans = "";
    for (int i = 0; i < n / 2; i++) {
        ans += s[i];           // 前半段的第 i 個
        ans += s[n / 2 + i];   // 後半段的第 i 個
    }
    cout << ans << endl;
    return 0;
}

三個重點：

  • k 和 op 雖然值都固定（\(1\) 和 \(2\)），還是要照輸入格式讀進來，不然讀到的 s 之後就沒對齊輸入了。
  • 結果接在新的字串 ans 上，不要邊讀 s 邊改 s（原因見完整解法）。
  • 拿範例 1 驗證：apcsntnu 要變成 anptcnsu。

交這個版本時範例 2 會顯示 WA（那筆有四次操作）——這是正常的。APCS 逐筆給分，子題組 1 的 12 筆測資照樣全過，穩拿 60 分。

從 60 分到 100 分

補上操作 \(0\) 和操作 \(1\)，再用迴圈把 \(k\) 個操作依序做完。好消息是：這兩種操作都只要「每次跳兩格」的一個迴圈就能完成。

完整解法（100 分）

外層用 for 迴圈跑 \(k\) 輪，每輪先讀入 op，再依 op 做對應的事。

操作 0：兩兩交換。 索引 \(i\) 從 \(0\) 開始、每次加 \(2\)，交換 s[i] 和 s[i + 1]。交換直接用內建的 swap 函式（上冊 7.6；記得 #include <algorithm>）：

for (int i = 0; i < n; i += 2) {
    swap(s[i], s[i + 1]);
}

例：abdc 分組 (ab)(dc)，交換後是 bacd。

操作 1：兩兩排序。 每一組只有兩個字元，所謂「排序」其實就是一句話：左邊比右邊大就交換。字元可以直接用 > 比大小（8.3）：

for (int i = 0; i < n; i += 2) {
    if (s[i] > s[i + 1]) {
        swap(s[i], s[i + 1]);
    }
}

例：abdc 分組 (ab)(dc)——第一組已經有序不動、第二組交換，結果 abcd。注意不能把整條字串拿去排序：family 整條排序會得到 afilmy，但正確答案是各組內排序的 afimly。

操作 2：完美重排。 和子題組 1 完全一樣。這裡回答「為什麼要用新字串」：交錯之後，位置 \(1\) 要放的是後半段的第一個字元，如果直接寫回 s，原本的 s[1] 還沒被用到就先被蓋掉了，後面再讀就是錯的資料。所以先把結果接在新字串 next 上，做完再 s = next; 存回去。

例：abdc 拆成 ab 和 dc，交錯成 adbc。

寫完可以用一條短字串把三種操作各驗一次（自己手算對答案）：abdc 三種操作的結果分別是 bacd、abcd、adbc——三種結果都不一樣，正好能分辨三段程式有沒有寫錯或接錯。

每次操作掃過字串一次，時間複雜度 \(O(kn)\)。

常犯錯誤
  1. 操作 1 把整條字串排序：只能「每組內」排序，組跟組之間不能互換。family 整條排序＝afilmy（錯）、逐組排序＝afimly（對）。
  2. 操作 2 邊讀邊寫同一條字串：前面的寫入會蓋掉後面還要讀的字元，一定要先寫到新字串再存回去。
  3. 操作 2 做完忘了 s = next;：交錯結果算好了卻沒存回 s，下一個操作還是拿舊字串在做。
  4. 只做了第一個操作：\(k\) 個操作要全部依序做完，別忘了外層迴圈（子題組 1 的程式直接交就是這種情況，只拿 60 分）。
  5. 分組迴圈寫成 i++：兩兩一組要 i += 2；寫成 i++ 會讓每個字元被前後兩組重複處理，操作 0 會變成整條字串平移，完全不是題目要的。
參考程式碼
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string s;
    int k;
    cin >> s >> k;

    int n = (int)s.size();
    for (int j = 0; j < k; j++) {
        int op;
        cin >> op;

        if (op == 0) {
            // 兩兩交換
            for (int i = 0; i < n; i += 2) {
                swap(s[i], s[i + 1]);
            }
        } else if (op == 1) {
            // 兩兩排序：左邊比右邊大就交換
            for (int i = 0; i < n; i += 2) {
                if (s[i] > s[i + 1]) {
                    swap(s[i], s[i + 1]);
                }
            }
        } else {
            // 完美重排：接到新字串再存回去
            string next = "";
            for (int i = 0; i < n / 2; i++) {
                next += s[i];
                next += s[n / 2 + i];
            }
            s = next;
        }
    }
    cout << s << endl;
    return 0;
}