---
title: 'APCS 2025/06 實作題題解 — C++'
disqus: hackmd
---
# APCS 2025/06 實作題題解 — C++
:::info
:bulb: 此筆記為APCS 2025年06月實作題考試的題目詳解。每一題的題解都包含解題思路、C++範例程式碼。
:::
## 第一題 小心陷阱 (ZeroJudge q836.)
### [題目](https://zerojudge.tw/ShowProblem?problemid=q836)
:::success
在一維數線上進行一場模擬遊戲。遊戲規則如下：
初始位置為 $0$。
初始生命值為 $k$（$1 ≤ k ≤ 20$）。
當前生命值為 $v$ 時，角色會往右跳 $v$ 格，也就是從位置 $p$ 移動到 $p + v$。
每次移動後，如果落在 $x_1$ 或 $x_2$ 的倍數上，會損失生命值：
若落在 $x_1$ 的倍數，生命值減少 $y_1$。
若落在 $x_2$ 的倍數，生命值減少 $y_2$。
若同時是 $x_1$ 和 $x_2$ 的倍數，生命值總共減少 $y_1 + y_2$。
當生命值小於等於 $0$ 時，遊戲結束，輸出當前所在的位置。
:::
### 輸入 / 輸出說明
| **輸入說明** | **輸出說明** |
|:-:|:-:|
|  |  |
### 解題思路
:::warning
這題難度讓我覺得很像是送分題。
直接用 while 迴圈在生命值 v > 0 時繼續執行 p = p + v，然後每次右移後的 p 去分別取 x1、x2 的餘數，若是 x1 或 x2 的倍數則扣除相應的 y1 或 y2 生命值。
:::
### 範例程式碼
```C++=
#include <iostream>
using namespace std;
int main()
{
int k, x1, x2, y1, y2, p = 0, v;
cin >> k >> x1 >> y1 >> x2 >> y2;
v = k; //當前生命值 (其實也可以直接用 k)
while (v > 0) {
p = p + v;
if (p % x1 == 0) //位置在 x1 的倍數
v -= y1; //扣除 y1 點生命值
if (p % x2 == 0) //位置在 x2 的倍數
v -= y2; //扣除 y1 點生命值
}
cout << p;
return 0;
}
```
### 運行結果
<font color="#00BB00">**AC**</font> (3ms, 336KB)
## 第二題 轉盤得分 (ZeroJudge q837.)
### [題目](https://zerojudge.tw/ShowProblem?problemid=q837)
:::success
你有 m 個輪盤，每個輪盤上有 $n$ 格，每格上寫有一個小寫英文字母（`a` ~ `z`）。一場遊戲有 $k$ 個回合。
每個回合，每個輪盤會基於上一個回合結束的狀態做轉動，然後計算當前狀態的得分：
每個輪盤的轉動可以是正數（順時針）、負數（逆時針）或 0（不轉）。
當所有輪盤都轉動完畢後，觀察它們對齊位置上的字元。
對於每一個位置（從上到下的每一格），統計出現次數最多的字元，並將該字元的出現次數計入分數。
每個回合的得分為這 $n$ 格的對齊統計加總。
最終總得分為所有回合的得分總和。
範例
一開始有三個輪盤：apcsie, taiwan, icpeda，三個輪盤的轉動距離分別是：1 0 -4
結果：
eapcsi ← apcsie 右轉 1
taiwan ← 不動
daicpe ← icpeda 左轉 4
分數計算：
第一格: (e, t, d) 出現最多的字元出現 1 次
第二格: (a, a, a) 出現最多的字元出現 3 次
第三格: (p, i, i) 出現最多的字元出現 2 次
第四格: (c, w, c) 出現最多的字元出現 2 次
第五格: (s, a, p) 出現最多的字元出現 1 次
第六格: (i, n, e) 出現最多的字元出現 1 次
這次轉動後的分數是 $10=1+3+2+2+1+1$
:::
### 輸入 / 輸出說明
| **輸入說明** | **輸出說明** |
|:-:|:-:|
|  |  |
### 解題思路
:::warning
這題我就直接紀錄他轉動後的字串起始字元位置。例如 taiwan 轉 1 的話，我就存 e 那個位置當開始，後面要找第 i 格就用 (e的位置 + i) % n 就可以了。
這邊要存起始位置可以透過 `(起始位置 - distance) % n` 得到（因為右轉是正數，但他其實是要前找起始位置，索引值往前要用減），但是這邊要注意他可能一次轉超過 n 格，直接用會造成右轉超過 n 格時剛剛的方法會是負的，從而得到錯誤答案，但因為題目限制在 -100 到 100 之間，我就直接偷懶用 `(起始位置 - distance + n * 100) % n`，透過加 n * 100 就可以保證即便是右轉距離（distance）超過 100 次也會是正確的位置，就可以直接得到轉後的起始位置了。
得到起始位置後就用剛剛說的找第 i 格的方式，即 `(起始位置 - distance + n * 100) % n`，再利用 point[第 i 格的字元編號]++，並比較 point[第 i 格的字元編號] 與之前出現最多次的字元次數（我這邊是用 max），將大的保留在 max，結束一格後把 max 加入 total 中就可以了。
<題外話> 偷偷的跟你們說，其實你隨便加個超過 100 的數字就可以了，答案也會是對的喔！
因為他相當於就是把初始位置平移，每一格得到的最多次數的字元會一樣，只是順序不同。
舉個例子：
假設題目是
3 6 1
apcsie
taiwan
icpeda
1 0 -4
然後我把 `(起始位置 - distance + n * 100)` 改成 `(起始位置 - distance + 100)`
原本 `(起始位置 - distance + n * 100)` 他的每一格順序是
第一格: (e, t, d) 出現最多的字元出現 1 次
第二格: (a, a, a) 出現最多的字元出現 3 次
第三格: (p, i, i) 出現最多的字元出現 2 次
第四格: (c, w, c) 出現最多的字元出現 2 次
第五格: (s, a, p) 出現最多的字元出現 1 次
第六格: (i, n, e) 出現最多的字元出現 1 次
答案是 $10=1+3+2+2+1+1$
改成 `(起始位置 - distance + 100)` 就會變成會先平移 100 % n = 4 格
第一格: (s, a, p) 出現最多的字元出現 1 次 （原本的第五格）
第二格: (i, n, e) 出現最多的字元出現 1 次 （原本的第六格）
第三格: (e, t, d) 出現最多的字元出現 1 次 （原本的第一格）
第四格: (a, a, a) 出現最多的字元出現 3 次 （原本的第二格）
第五格: (p, i, i) 出現最多的字元出現 2 次 （原本的第三格）
第六格: (c, w, c) 出現最多的字元出現 2 次 （原本的第四格）
答案是 $10=1+1+1+3+2+2$，一樣喔！
:::
### 範例程式碼
```C++=
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int i, j, m, n, k, max, total = 0, word;
int distance, top[30]={}, point[26];
string s[30];
cin >> m >> n >> k;
for (i=0;i<m;i++)
cin >> s[i];
while (k > 0) {
max = 0;
for (i=0;i<m;i++) {
cin >> distance; //轉動距離
//移動字串開始的位置 (top[j] 都是存字串開始的位置，由左而右)
//用減是因為右轉反而最上面的字元索引在原本的字元的前面
//加 100 是為了 top - distance 是負的可以正確到對的位置(題目說最多距離+-100)
top[i] = (top[i] - distance + n * 100) % n;
}
for (i=0;i<n;i++) {
memset(point, 0, sizeof(point)); //point 清零，用於紀錄字元出現次數
max = 0; //紀錄這格出現次數最多的字元的次數
for (j=0;j<m;j++) {
//出現的字元的字典編號
word = s[j][(top[j]+i)%n] - 'a'; //(top[j]+i)%n 可以得到第 i 格的字元位置
point[word]++; //出現的字元次數加 1
if (point[word] > max) //比之前的字元出現的次數多
max = point[word]; //更新為這格最佳
}
total += max; //出現次數最多的字元的次數加到總和
}
k--;
}
cout << total;
return 0;
}
```
### 運行結果
<font color="#00BB00">**AC**</font> (2ms, 352KB)
## 第三題 貪心闖關 (ZeroJudge q838.)
### [題目](https://zerojudge.tw/ShowProblem?problemid=q838)
:::success
小花參加一個搬沙包挑戰賽，關卡有 $n$ 個，編號由 $1$ ~ $n$，初始時，每個關卡有若干個沙包。
選手會選擇一個仍有沙包的關卡，將其所有的沙包搬至編號順序下一個仍有沙包的關卡，若選擇的關卡為當前仍有沙包的關卡中編號最大的，則把沙包搬出關卡即可。
沙包被搬完的關卡標示為完成，意即不會再有沙包被搬進此關卡，挑戰會持續進行直到所有關卡完成，或小花選手無法一次搬動當下任何關卡的所有沙包，小花一次可搬動的沙包上限為 $t$ 個。
每成功搬動 $w$ 個沙包則得 $w$ 分，小花打算採用以下貪心的策略完成挑戰，請計算小花的總分：
• 選擇當前關卡中沙包最少的關卡，若有超過一個關卡有當前最少的沙包，則選擇編號最小的關卡
• 重複以上步驟直到挑戰結束 以測資一為範例：
•選擇關卡4，搬1個沙包到關卡5，得1分，關卡狀態更新為 (4 4 2 0 10 3)
•選擇關卡3，搬2個沙包到關卡5，得2分，關卡狀態更新為 (4 4 0 0 12 3)
•選擇關卡6，已經是當前仍有沙包的關卡中編號最大的，所以將沙包移出關卡就好，得3分，關卡狀態更新為 (4 4 0 0 12 0)
•選擇關卡1，搬4個沙包到關卡2，得4分，關卡狀態更新為 (0 8 0 0 12 0)
•選擇關卡2，搬8個沙包到關卡5，得8分，關卡狀態更新為 (0 0 0 0 20 0)
•所有關卡中沙包最少的為20個，超過小花一次能搬動的上限8個，所以挑戰結束，總分為 1+2+3+4+8=18
:::
### 輸入 / 輸出說明
| **輸入說明** | **輸出說明** |
|:-:|:-:|
|  |  |
### 解題思路
:::warning
這題經過觀察後可以發現當前一個還有沙包的關卡（未完成的關卡）的沙包數 ≤ 新關卡的沙包數**且小花搬得動未完成的關卡的沙包數**，則可以直接將未完成的關卡的沙包數加到新的關卡的沙包數，然後將未完成的關卡的沙包數移出（已經被搬完了），最後將搬了前面未知數關卡的沙包數後得到的新關卡的沙包數加入後續的比較中。
也就是說我們可以透過堆疊（stack）的後進先出（Last In First Out，LIFO）的特性完成這題。詳細步驟如下：
1. 當堆疊內還有未完成關卡且前一個未完成關卡的沙包比較少，就將總分與新關卡的沙包數分別加上前一個未完成關卡的沙包，將前一個未完成關卡移除堆疊。
2. 若新關卡的沙包數仍然可以被小花搬動，則將新關卡加入堆疊中。
3. 完成所有關卡一輪後，剩下的堆疊內還有搬得動的未完成關卡都是可以搬得動的（第二步杜絕了搬不動的關卡），就將剩下的關卡的沙包數都加入總分中。
<註> 第 3 步剩下的都會依序移出，是題目中的 `若選擇的關卡為當前仍有沙包的關卡中編號最大的，則把沙包搬出關卡即可。` 這個條件
:::
### 範例程式碼
```C++=
#include <bits/stdc++.h>
using namespace std;
int main ()
{
ios::sync_with_stdio(false);
cin.tie(0);
int i, n, t;
long long int total = 0, sandbag;
stack<long long int> stk;
cin >> n >> t;
for (i=0;i<n;i++) {
cin >> sandbag; //輸入關卡沙包數
//堆疊內還有未完成關卡 & 前一個未完成關卡的沙包比較少
while (stk.size() > 0 && stk.top() <= sandbag) {
total += stk.top(); //總分增加前一個未完成關卡的沙包
sandbag += stk.top(); //此關卡沙包加上前一個未完成關卡的沙包
stk.pop(); //前一個未完成關卡移出堆疊
}
if (sandbag <= t) //此關卡是否搬得動
stk.push(sandbag); //搬得動的話就將此關卡加入堆疊
}
while (stk.size() > 0) { //堆疊內還有搬得動的未完成關卡
total += stk.top(); //總分增加關卡的沙包數
stk.pop();
}
cout << total;
return 0;
}
```
### 運行結果
<font color="#00BB00">**AC**</font> (66ms, 344KB)
## 第四題 分組遊戲 (ZeroJudge q839.)
### [題目](https://zerojudge.tw/ShowProblem?problemid=q839)
:::success
有 $n$ 個物品，編號為 $1$ 到 $n$。每對物品 $(i, j)$ 之間有一個正整數距離 $D[i][j]$，其中 $D[i][i]=0$，且 $D[i][j] = D[j][i] > 0$。
你需要將這些物品分成恰好 $k$ 組，每組至少包含一個物品，且每個物品只能分在其中一組。
分組後，對於所有 $1 ≤ i < j ≤ n$，如果物品 $i$ 和 $j$ 分在同一組，則將 $D[i][j]$ 設為 $∞$（無限大），否則保持原距離。
接下來，考慮整個距離矩陣中剩下的 $D[i][j]$ 值（即不同組的物品之間的距離），你要最大化其中的最小值。
以範例 $2$ 為例，分成 {1, 4}, {2, 5}, {3} 會使得距離矩陣變為 (以 - 標記為 $∞$)
```
0 5 6 - 3
5 0 3 4 -
6 3 0 4 7
- 4 4 0 5
3 - 7 5 0
```
最小值為 $3$
:::
### 輸入 / 輸出說明
| **輸入說明** | **輸出說明** |
|:-:|:-:|
|  |  |
### 解題思路
:::warning
這題我用二分搜尋法 + DFS 去做。
我們要找出在將所有物品分組後，其他不同組物品 (i,j) 之間的距離 D[i][j] 中的最小值。我們需要讓這個最小值盡可能地大。而題目中 D[i][j] 有可能到 $10^8$，若使用循序搜尋可能會 TLE，因此我們需要使用二分搜尋法找出 distance。
而二分搜尋法中的重點就是當我們使用 DFS 找出小於 distance 的物品分為一組時，若將其分為 team（我自訂的變數）組的話，如果 team >= k（超過 k 組可以合併為 k 組，但小於 k 組不行）就代表這個 distance 是可以滿足的，就可以繼續找大於這個 distance 中滿足的下一個 distance。
DFS 就去找每一個物品與其他物品的距離小於 distance 的，把每一個滿足的都分到同一組，盡可能把組內物品最大化，組數最小化（這樣才可以保證 distance 最大化）。
:::
### 範例程式碼
```C++=
#include <bits/stdc++.h>
using namespace std;
int visited[500];
int dfs(int n, int start, int d[500][500], int distance)
{
int i;
for (i=0;i<n;i++) {
//兩個物品距離小於規定的 distance & 還沒被分過組
if (d[start][i] < distance && visited[i] == 0) {
visited[i] = 1; //設為已分過組
dfs(n, i, d, distance); //繼續找有沒有還可以分為一組的
}
}
}
int allow(int n, int k, int d[500][500], int distance)
{
int i, team = 0;
memset(visited, 0, sizeof(visited));
for (i=0;i<n;i++) {
if (visited[i] == 0) { //還沒被分過組
visited[i] = 1; //設為已分過組
dfs(n, i, d, distance); //找有沒有還可以分為一組的
team++; //組數 + 1
}
}
if (team >= k) //分為 k 組以上
return 1;
return 0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int i, j, n, k;
int left = 1e9, right = 0, mid, ans;
int d[500][500];
cin >> n >> k;
for (i=0;i<n;i++) {
for (j=0;j<n;j++) {
cin >> d[i][j];
if (d[i][j] < left) //找最小距離
left = d[i][j];
if (d[i][j] > right) //找最大距離
right = d[i][j];
}
}
while (left <= right) {
mid = (left + right) / 2;
if (allow(n, k, d, mid) == 1) {
ans = mid;
left = mid + 1;
}
else
right = mid - 1;
}
cout << ans;
return 0;
}
```
### 運行結果
<font color="#00BB00">**AC**</font> (49ms, 1.3MB)
###### tags: `APCS實作題`
:::danger
查看更多資訊請至：https://www.tseng-school.com/
:::
Sign in with Wallet
Connect another wallet