APCS實作題2025年1月第2題：字串操作

日期：2025年1月15日
作者：王一哲
ZeroJudge 題目連結

題目

問題描述

給一個字串

$S$，有三種字串操作，分別如下

1. 編號0，兩兩交換：將字串內相鄰兩個字元交換，例如字串 "apcsntnu" 先分組成 (ap)(cs)(nt)(nu)，將會交換為 (pa)(sc)(tn)(un)，即得到 "pasctnun"。
2. 編號1，兩兩排序：將字串內相鄰兩個字元按照字典序排序，字元的字典序為
   $a<b<\cdots <z$，例如字串 "family" 先分組成 (fa)(mi)(ly)，將會交換成 (af)(im)(ly)，即得到 "afimly"。
3. 編號2，完美重排：假設字串長度為
   $n$，將字串內的字元編號為
   $0,1,2,\dots ,n-1$，將字串分成兩半為
   $0,1,2,\dots ,\frac{n}{2}-1$ 和
   $\frac{n}{2},\frac{n}{2}+1,\frac{n}{2}+2,\dots ,n-1$，並且組合成
   $0,\frac{n}{2},1,\frac{n}{2}+1,\dots ,\frac{n}{2}-1,\frac{n}{2}+1$。例如 "apcsntnu" 拆成 "apcs" 和 "ntnu"，然後交錯成 "anptcnsu"。

給定

$k$ 個操作，請依序操作字串，輸出最後的字串結果。

輸入說明

第一行輸入一個字串

$S(2\le |S|\le 100)$，字串長度保證為偶數。接下來一行輸入一個正整數

$k$，接下來有

$k$ 行，每一行有一個數字，種類為

$0,1,2$。

子題配分

• 60%：
  $|S|\le 10,k=1$ 且保證操作為完美重排
• 40%：無限制

輸出格式

輸出操作完之後的字串內容。

範例輸入1

apcsntnu
1
2

範例輸出1

anptcnsu

範例輸入2

facebook
4
2
0
2
1

範例輸出2

bocfkoae

Python 程式碼

寫法1，利用字串的索引值，不自訂函式

費時最久約為 23 ms，使用記憶體最多約為 3.3 MB，通過測試。

S = input().strip()  # 輸入的字串
n = len(S)  # 字串長度
k = int(input())  # 操作次數
for _ in range(k):  # 執行 k 次
    op = int(input())  # 操作種類
    t = ""  # 儲存操作結果用的空字串
    if op == 0:  # 操作0，兩兩交換
        for i in range(0, n, 2):  # i 每次加 2
            t += S[i+1] + S[i]
    elif op == 1:  # 操作1，兩兩排序
        for i in range(0, n, 2):  # i 每次加 2
            a, b = S[i], S[i+1]  # 取出兩個字元 a, b
            if a <= b: t += a+b  # 如果 a <= b，將 a+b 接到 t 最後面
            else: t += b+a  # 反之，將 b+a 接到 t 最後面
    else:  # 操作2，完美重排
        for i in range(n//2):  # 執行 n//2 次
            t += S[i] + S[n//2 + i]
    S = t  # t 字串存到 S
print(S)

寫法2，利用字串的索引值，自訂函式

費時最久約為 20 ms，使用記憶體最多約為 3.4 MB，通過測試。

# 寫法2，利用字串的索引值，自訂函式
def zero(s):  # 操作0，兩兩交換
    t = ""  # 儲存操作結果用的空字串
    for i in range(0, len(s), 2):  # i 每次加 2
        t += s[i+1] + s[i]
    return t

def one(s):  # 操作1，兩兩排序
    t = ""  # 儲存操作結果用的空字串
    for i in range(0, len(s), 2):  # i 每次加 2
        a, b = S[i], S[i+1]  # 取出兩個字元 a, b
        if a <= b: t += a+b  # 如果 a <= b，將 a+b 接到 t 最後面
        else: t += b+a  # 反之，將 b+a 接到 t 最後面
    return t

def two(s):  # 操作2，完美重排
    t = ""  # 儲存操作結果用的空字串
    n = len(s)  # 字串長度
    for i in range(n//2):  # 執行 n//2 次
        t += S[i] + S[n//2 + i]
    return t

S = input().strip()  # 輸入的字串
k = int(input())  # 操作次數
for _ in range(k):  # 執行 k 次
    op = int(input())  # 操作種類
    if op == 0: S = zero(S)
    elif op == 1: S = one(S)
    else: S = two(S)
print(S)

寫法3，利用字串切片 (slice) 及 zip

Python 的字串及串列的切片，語法為

S[起點:終點:間隔]

取出的資料包含起點，起點預設值為開頭；不包含終點，終點預設值為結尾；間隔預設值為1，如果間隔為2每次跳兩格，如果間隔為-1會倒過來取值。如果想要將一個字串反向輸出，可以寫成

S[::-1]

費時最久約為 22 ms，使用記憶體最多約為 3.3 MB，通過測試。

# 寫法3，利用字串切片 (slice) 及 zip
S = input().strip()  # 輸入的字串
n = len(S)  # 字串長度
for _ in range(int(input())):  # 執行 k 次
    op = int(input())  # 操作種類
    t = ""  # 儲存操作結果用的空字串
    if op == 0:  # 操作0，兩兩交換
        for a, b in zip(S[::2], S[1::2]):
            t += b+a
    elif op == 1:  # 操作1，兩兩排序
        for a, b in zip(S[::2], S[1::2]):
            t += a+b if a <= b else b+a
    else:  # 操作2，完美重排
        for a, b in zip(S[:n//2], S[n//2:]):
            t += a+b
    S = t  # t 字串存到 S
print(S)

寫法4，先將字串轉成串列 (list)，再利用切片 (slice) 修改串列內容

這是我看到最有 Python 風格的寫法，但是對於初學者最難看懂。由於 Python 的字串不能透過索引值修改某個字元的內容，所以要先將字串轉成串列才行。費時最久約為 27 ms，使用記憶體最多約為 3.3 MB，通過測試。

S = list(input())  # 輸入的字串轉成串列
n = len(S)  # 串列長度
for _ in range(int(input())):  # 執行 k 次
    op = int(input())  # 操作種類
    if op == 0:  # 操作0，兩兩交換
        S[::2], S[1::2] = S[1::2], S[::2]
    elif op == 1:  # 操作1，兩兩排序
        for i in range(0, n, 2):  # 執行 n//2 次
            S[i:i+2] = sorted(S[i:i+2])            
    else:  # 操作2，完美重排
        S[::2], S[1::2] = S[:n//2], S[n//2:]
print("".join(S))  # 將 S 接成字串再輸出

C++ 程式碼

寫法1，利用字串的索引值，不自訂函式

費時最久約為 3 ms，使用記憶體最多約為 352 kB，通過測試。

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string S; cin >> S;  // 輸入的字串
    int n = (int)S.size();  // 字串長度
    int k; cin >> k;  // 操作次數
    for(int j=0, op; j<k; j++) {  // 執行 k 次
        cin >> op;  // 操作種類
        if (op == 0) {  // 操作0，兩兩交換
            for(int i=0; i<n; i+=2) {  // i 每次加 2
                char a = S[i];  // 暫存 S[i]
                S[i] = S[i+1];  // S[i] 重設為 S[i+1]
                S[i+1] = a;  // S[i+1] 重設為 a
            }
        } else if (op == 1) {  // 操作1，兩兩排序
            for(int i=0; i<n; i+= 2) {  // i 每次加 2
                char a = S[i], b = S[i+1];  // 取出兩個字元 a, b
                if (a > b) {  // 如果 a > b
                    S[i] = b; S[i+1] = a;  // S[i] 重設為 b，S[i+1] 重設為 a
                }
            }
        } else {  // 操作2，完美重排
            string t = S;  // 字串 S 暫存到 t
            for(int i=0; i<n/2; i++) {  // 執行 n/2 次
                S[2*i] = t[i]; S[2*i+1] = t[n/2+i];  // S[2*i] 重設為 t[i]，S[2*i+1] 重設為 t[n/2+1]
            }
        }
    }
    cout << S << "\n";
    return 0;
}

寫法2，利用字串的索引值，自訂函式

費時最久約為 3 ms，使用記憶體最多約為 344 kB，通過測試。

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

string zero(string s) {  // 操作0，兩兩交換
    string t = "";  // 暫存輸出結果的空字串
    for(int i=0; i<(int)s.size(); i+=2) t = t + s[i+1] + s[i];
    return t;
}

string one(string s) {  // 操作1，兩兩排序
    string t = "";  // 暫存輸出結果的空字串
    for(int i=0; i<(int)s.size(); i+=2) {
        if (s[i] <= s[i+1]) t = t + s[i] + s[i+1];
        else t = t + s[i+1] + s[i];
    }
    return t;
}

string two(string s) {  // 操作2，完美重排
    string t = "";  // 暫存輸出結果的空字串
    int n = (int)s.size();  // 字串長度
    for(int i=0; i<n/2; i++) t = t + s[i] + s[n/2+i];
    return t;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string S; cin >> S;  // 輸入的字串
    int k; cin >> k;  // 操作次數
    for(int j=0, op; j<k; j++) {  // 執行 k 次
        cin >> op;  // 操作種類
        if (op == 0) S = zero(S);
        else if (op == 1) S = one(S);
        else S = two(S);
    }
    cout << S << "\n";
    return 0;
}

---

tags:APCS、Python、C++