# APCS實作題2025年1月第2題：字串操作
> 日期：2025年1月15日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=q182)
## 題目
### 問題描述
給一個字串 $S$，有三種字串操作，分別如下
1. **編號0**，兩兩交換：將字串內相鄰兩個字元交換，例如字串 "apcsntnu" 先分組成 (ap)(cs)(nt)(nu)，將會交換為 (pa)(sc)(tn)(un)，即得到 "pasctnun"。
2. **編號1**，兩兩排序：將字串內相鄰兩個字元按照字典序排序，字元的字典序為 $a < b < \dots < 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$ 個操作，請依序操作字串，輸出最後的字串結果。
<br />
### 輸入說明
第一行輸入一個字串 $S~(2 \leq |S| \leq 100)$，字串長度保證為偶數。接下來一行輸入一個正整數 $k$，接下來有 $k$ 行，每一行有一個數字，種類為 $0, 1, 2$。
子題配分
- 60%：$|S| \leq 10, k = 1$ 且保證操作為完美重排
- 40%：無限制
<br />
### 輸出格式
輸出操作完之後的字串內容。
<br />
### 範例輸入1
```
apcsntnu
1
2
```
### 範例輸出1
```
anptcnsu
```
### 範例輸入2
```
facebook
4
2
0
2
1
```
### 範例輸出2
```
bocfkoae
```
<br /><br />
## Python 程式碼
### 寫法1，利用字串的索引值，不自訂函式
費時最久約為 23 ms，使用記憶體最多約為 3.3 MB，通過測試。
```python=
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)
```
<br />
### 寫法2，利用字串的索引值，自訂函式
費時最久約為 20 ms，使用記憶體最多約為 3.4 MB，通過測試。
```python=
# 寫法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)
```
<br />
### 寫法3，利用字串切片 (slice) 及 zip
Python 的字串及串列的切片，語法為
```python
S[起點:終點:間隔]
```
取出的資料包含起點，起點預設值為開頭；不包含終點，終點預設值為結尾；間隔預設值為1，如果間隔為2每次跳兩格，如果間隔為-1會倒過來取值。如果想要將一個字串反向輸出，可以寫成
```python
S[::-1]
```
費時最久約為 22 ms，使用記憶體最多約為 3.3 MB，通過測試。
```python=
# 寫法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)
```
<br />
### 寫法4，先將字串轉成串列 (list)，再利用切片 (slice) 修改串列內容
這是我看到最有 Python 風格的寫法，但是對於初學者最難看懂。由於 Python 的字串不能透過索引值修改某個字元的內容，所以要先將字串轉成串列才行。費時最久約為 27 ms，使用記憶體最多約為 3.3 MB，通過測試。
```python=
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 接成字串再輸出
```
<br /><br />
## C++ 程式碼
### 寫法1，利用字串的索引值，不自訂函式
費時最久約為 3 ms，使用記憶體最多約為 352 kB，通過測試。
```cpp=
#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;
}
```
<br />
### 寫法2，利用字串的索引值，自訂函式
費時最久約為 3 ms，使用記憶體最多約為 344 kB，通過測試。
```cpp=
#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;
}
```
<br /><br />
---
###### tags:`APCS`、`Python`、`C++`
Sign in with Wallet
Connect another wallet