# APCS 範例 - Python 詳解
:::info
此為自 2025 年十月開始的新版 APCS 大學程式設計先修檢測，程式實作之題目範例解答與詳細說明
由於範例題來源於歷屆試題，此會附上其 ZeroJudge 的網址，以便自行練習與判分
題目來源：[APCS 官網](https://apcs.csie.ntnu.edu.tw/index.php/questionstypes/previousexam/)
解答作者：@Chuen666666（部分解法使用 AI）
如有任何可改進、錯誤、不懂想詢問者，歡迎與我聯絡
（想從很基礎的地方開始學 Python 也可以找我喔）
LINE: chuen666666
DC: chuen666666
:::
## [初級題本範例](https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2025/08/01_APCS-%E7%A8%8B%E5%BC%8F%E5%AF%A6%E4%BD%9C%E5%88%9D%E7%B4%9A%E9%A1%8C%E6%9C%AC%E7%AF%84%E4%BE%8B.pdf)
### 七言對聯（[g275.](https://zerojudge.tw/ShowProblem?problemid=g275)）
不需要一次讀入所有輸入，因為是兩行為一個對聯，因此我們只需要每次讀入兩行（`a` 和 `b`）即可
由於看到題目要求的輸出值中有 `None`，因此這裡我想寫一個自訂函式來處理
我們設定一個字串 `ans` 用以存答案（當然用 list 也可以，但這裡由於輸出格式原因，str 比較方便），然後分別進行三個規則的判斷
注意！這三行不互斥（也就是可能同時出現），因此要用三個 `if`，不能用 `elif` 或 `else`
最後，可以利用 `if ans` 的方式來判斷 `ans` 是否為空，空則回傳 `None`
```python=
def sol():
a, b = list(map(int, input().split())), list(map(int, input().split()))
ans = ''
if (a[1]==a[3] or a[1]!=a[5]) or (b[1]==b[3] or b[1]!=b[5]):
ans += 'A'
if a[-1] != 1 or b[-1] != 0:
ans += 'B'
if a[1]==b[1] or a[3]==b[3] or a[5]==b[5]:
ans += 'C'
return ans if ans else None
for _ in range(int(input())):
print(sol())
```
### 裝飲料（[o711.](https://zerojudge.tw/ShowProblem?problemid=o711)）
這裡我的解法不一定是最有效率解，但邏輯應該是比較好理解的
首先，我們為了求高度，得先把正方形邊長 `w1` 和 `w2` 作一次平方，使它變為底面積，同時，為了追蹤兩容器是否滿，也要計算出兩容器所剩體積 `left1` 和 `left2`
最後，答案的部分只需要使用一個變數 `up` 來存即可，由於所求僅要求最大值，一開始我們需要將數值設為一個足夠小的數值（高度不可能 < 0，因此這裡直接設為 `0`）
我們要逐一處理每次倒入水時的液面狀況，因此使用一個 for-loop 來跑 `c`（即每次倒水的量）
我們可以把每次倒入水分為以下四種情況：
1. 第一杯的量足夠裝下這次倒入的量
2. 第一杯還沒滿，但倒入會令它滿出來
3. 第一杯已滿，且倒入時第二杯足夠裝下第一杯滿出來的量
4. 第一杯已滿，且倒入時第二杯會滿出來（或剛好滿）
其中，第一杯會滿（原本就滿了或倒完後會滿）的情況，我把第一杯與第二杯的上升量與杯狀態分開處理
具體的杯子處理邏輯可見下方程式的註解
```python=
input() #程式用不到此數值，故放一個空輸入
w1, w2, h1, h2 = map(int, input().split())
c = list(map(int, input().split()))
w1, w2 = w1**2, w2**2 #邊長轉底面積
up = 0 #最大上升高度（即所求）
left1, left2 = w1*h1, w2*h2 #兩杯剩餘體積
for i in c:
if left1 >= i: #倒進的量未滿過第一杯
up = max(up, i//w1)
left1 -= i
else: #倒進的量會滿過第一杯
h_ = 0 #為了計入第一杯上升量+第二杯上升量，用一個臨時變數
if left1 > 0: #若第一杯未滿，將第一杯倒滿
h_ += left1 // w1
i -= left1
left1 = 0
if left2 > i: #倒進的量未滿過第二杯
h_ += i // w2
left2 -= i
else: #倒進的量會滿過第二杯，將第二杯倒滿
h_ += left2 // w2
up = max(up, h_)
break #兩杯皆滿，結束
up = max(up, h_)
print(up)
```
### 遊戲選角（[m931.](https://zerojudge.tw/ShowProblem?problemid=m931)）
雖然這題理論上用最小堆來做效率會更高，但考量到這題初級（理論上不用會任何演算法就可以過），我會以最簡單直覺的方式來做這題
這題非常簡單，核心思想就是輸出兩數平方和第二高的那組數據
首先，我們以 tuple 的形式讀入 $n$ 筆資料，並放在一個 list 中（這裡示範以 list comprehension 來輸入，不會這種寫法的話可以學一下，對於檢定與檢賽這種不要求可讀性的場合很實用）
使用 `sort()` 來排序，排序規則（`key=`）則設為題目要求的 $功擊力^2+防禦力^2$
由於 `sort()` 會把 list 由小到大排，要取第二大就要使用 `[-2]`
又因為最開始是以 tuple 來存每組數據，這裡用 `*` 來 unpack（解包），tuple 裡的內容會被拆開後傳入 `print()` 中，`print()` 預設又是以空格來隔開每個引數，就可以很簡單地達成題目要求的輸出格式（`<n> <m>`）
```python=
arr = [tuple(map(int, input().split())) for _ in range(int(input()))]
arr.sort(key=lambda i: i[0]**2 + i[1]**2)
print(*arr[-2])
```
## [中級題本範例](https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2025/08/02_APCS-%E7%A8%8B%E5%BC%8F%E5%AF%A6%E4%BD%9C%E4%B8%AD%E7%B4%9A%E9%A1%8C%E6%9C%AC%E7%AF%84%E4%BE%8B.pdf)
### 特殊位置（[k732.](https://zerojudge.tw/ShowProblem?problemid=k732)）
這是我最初的想法，應該也是最直覺的想法之一，但這種寫法會跑非常多次迴圈，因此效率非常差，差到只能通過第一子題（60 分）
首先，我們將輸入的資料存成一個二維陣列 `arr`，接著，使用一個 set `ans` 來計入不重覆的座標點（其實用 list 也可以），然後去跑迴圈
迴圈的部分，先是要跑過一整個 `arr`，去檢查每個點
然後針對每個點，我們先用一個臨時變數 `s` 來存目前座標的周邊（曼哈頓）距離範圍所有點之值的總和
接著再跑一次整個 `arr`，檢查其是否於指定距離內，若是，則加到 `s` 中
最後，若依題目要求的條件，若 $s \equiv A[i][j](\mod 10)$（即在除以 10 的情況下同餘），則表示 $A[i][j]$ 符合「特殊位置」，將其存入 `ans` 中
輸出的部分，首先先輸出符合的筆數（即 `ans` 的長度）
接著，再依序將每組座標以解包（`*`）的方式印出，排序的部分則使用 `sorted()`
（註：只有 `sorted()` 可以排序所有 iterable，`sort()` 屬於 list 的 method，只能使用在 list 上）
```python=
n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
ans = set()
for i in range(n):
for j in range(m):
now = arr[i][j]
s = 0
for a in range(n):
for b in range(m):
if abs(a-i) + abs(b-j) <= now:
s += arr[a][b]
if s%10 == now%10:
ans.add((i, j))
print(len(ans))
for i in sorted(ans):
print(*i)
```
若要通過全部測資（即第二子題），我們就得將迴圈的次數減少
我們先前的迴圈邏輯是暴力將所有範圍跑一次
雖然為了檢查每個點是否符合，最外面兩層迴圈仍必須把整個 `arr` 跑完
但裡面的迴圈其實可以根據檢查到的點來排除不可能的範圍，以達到明顯減少迴圈次數的效果
要確定哪邊是或不是必要範圍，我們就得先來看看曼哈頓距離的圖形及定義
其定義為：若有兩點 $P(x_0,y_0),Q(x_1,y_1)$，則此兩點的曼哈頓距離為 $d(A,B)=|(x_1-x_0)+(y_1-y_0)|$
現在的情況是，我們要找給定距離的範圍，若觀察其圖形，不難發現它會呈一菱形，最長的部分就是上下左右凸出部分，其值正好等於給定距離
因此，我們的限制範圍就只需要做在目前位置的上下左右各加上給定距離（即該點所對應的值）即可（形成一個長方或正方形）
```python=
n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
ans = set()
for i in range(n):
for j in range(m):
now = arr[i][j]
s = 0
for a in range(max(0, i-now), min(n, i+now+1)): #使用 max() 和 min() 是為了避免跑出範圍
for b in range(max(0, j-now), min(m, j+now+1)):
if abs(a-i) + abs(b-j) <= now:
s += arr[a][b]
if s%10 == now%10:
ans.add((i, j))
print(len(ans))
for i in sorted(ans):
print(*i)
```
###### 其實真正改的地方只有只有 L10 和 L11 的範圍部分
### 蒐集寶石（[o712.](https://zerojudge.tw/ShowProblem?problemid=o712)）
這題我有看到有人使用 `itertools` 的 `cycle()` 來做轉彎的 function
不過因為我不會用，所以這裡我會用徒手寫出來的解法，兩種方法都可以參考看看
首先，終止條件為「走到格子內無寶石」，我們無法得知它的具體次數，因此此處只能使用 while-loop 而非 for-loop
在初始狀態下，我們把 `score` 和 `daimon` 設為 0，來記錄分數與目前拿到的寶石數
以及利用 `face` 來記錄面向
（為了讓它保持「右→下→左→上」的循環，我們可以使用 int 配合取模（取餘數）操作來轉向）
我定義了一個函式 `front()` 用來看「面對的方向的前方格子」的座標
這麼做的好處是：
1. 在看前一格是否合法（也就是判斷轉完後是否需要再繼續轉）時，可以更方便判斷前方那格是否合法
2. 往前走時，直接做變數賦值，就可以往前走
接著進入到主程式，就是依照題目的規則照順序寫即可（詳見程式中的註解）
```python=
m, n, k, r, c = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(m)]
score = daimon = 0
face = 0 # 0右 1下 2左 3上
def front(r, c, face):
if face == 0:
c += 1
elif face == 1:
r += 1
elif face == 2:
c -= 1
else:
r -= 1
return (r, c)
while True:
if arr[r][c] == 0: #規則1
break
#規則2
score += arr[r][c]
daimon += 1
arr[r][c] -= 1
#規則3
if score % k == 0:
face = (face+1) % 4 #右轉，也就是把面朝方向+1，但>=4時回到就0，故用取模操作計算
#規則4
for _ in range(4):
ft = front(r, c, face) #設一個變數來記錄目前的前方格子，才不用每次查看時都調用一次函式，效率更高
if 0 <= ft[0] < m and 0 <= ft[1] < n and arr[ft[0]][ft[1]] != -1:
break
face = (face+1) % 4
else:
break
r, c = ft
print(daimon)
```
### 字串解碼（[i400.](https://zerojudge.tw/ShowProblem?problemid=i400)）
這題光看題目的話其實有點難想像如何實作，在這種狀況下建議去看題目的範例說明和範例測資來理解題意與思考如何實作
這題因為會把一個一個放到答案堆的最前或最後，因此會使用到佇列（可想像成對於從頭部或尾部新增資料的效率較高的 list）
但其實若不會使用佇列（queue），也可以手寫一個 str 或 list 來自己實作一個
因為要解密，因此上面的步驟要反著做回來（也可以用測資和範例說明來想）
L33 和 L34 也是一樣概念
這裡題目提及的變數我都用一樣的名稱去命名，這樣寫邏輯時才不用再轉換一次，減少思時間
剛好題目要求的轉換方式被寫成了 $t=f(s,e)$，很直觀地可以想到做一個函式出來
首先，因為 `n` 在整個程式中（函式內或函式外）都不會被改變，因此不用特地把它作為引數傳入
直接使用 `global` 來取用即可（開發軟體時不建議此寫法，但競賽與檢定推薦）
接著，建立一個 `dq` 來放答案（此處可使用 str 或 list 代替，但效率較差）
接下來就是照著題目邏輯、順序相反來寫即可
完成整個函式後，調用順序也必須反著來（可參考題目範例二）
最後把更新完的 `t` 輸出即可
```python=
#使用 deque 版
#ZeroJudge 測資：26ms, 3.7MB
from collections import deque
m, n = map(int, input().split())
e = [input() for _ in range(m)]
t = input()
def f(s, e):
global n
ans = deque() #放答案
#步驟2：從後往前把 t[i] 放回去
for i in range(n-1, -1, -1):
if e[i] == '0':
ans.appendleft(s[i]) #從左把元素加入，使用 list 的話相當於 list = [t[i]] + list
else:
ans.append(s[i])
#步驟1：若 1 的個數為奇數，再半對調一次
if e.count('1') % 2 == 1 and n > 1:
if n % 2 == 0:
ans = deque(list(ans)[n//2:] + list(ans)[:n//2]) #deque 不支援切片，因此先轉 list 再切，再轉回 deque
else:
ans = deque(list(ans)[n//2+1:] + list(list(ans)[n//2]) + list(ans)[:n//2])
return ''.join(ans) #把 deque 轉成字串
for i in range(m-1, -1, -1): #倒著還原
t = f(t, e[i])
print(t)
```
```python=
#不使用 deque 版（以 str 代替之）
#ZeroJudge 測資：22ms, 3.4MB
m, n = map(int, input().split())
e = [input() for _ in range(m)]
t = input()
def f(s, e):
global n
ans = '' #放答案
#步驟2：從後往前把 t[i] 放回去
for i in range(n-1, -1, -1):
if e[i] == '0':
ans = s[i] + ans
else:
ans += s[i]
#步驟1：若 1 的個數為奇數，再半對調一次
if e.count('1') % 2 == 1 and n > 1:
if n % 2 == 0:
ans = ans[n//2:] + ans[:n//2]
else:
ans = ans[n//2+1:] + ans[n//2] + ans[:n//2]
return ans
for i in range(m-1, -1, -1): #倒著還原
t = f(t, e[i])
print(t)
```
## [中高級題本範例](https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2025/08/03_APCS-%E7%A8%8B%E5%BC%8F%E5%AF%A6%E4%BD%9C%E4%B8%AD%E9%AB%98%E7%B4%9A%E9%A1%8C%E6%9C%AC%E7%AF%84%E4%BE%8B.pdf)
:::warning
從中高級開始，解法皆為 AI 生成
若有 ZeroJudge 對應題目，則已確保程式可通過所有測資
:::
### 迷宮探訪（[j124.](https://zerojudge.tw/ShowProblem?problemid=j124)）
基本上到了中高級開始，就要會一些演算法才有辦法寫了
以此題而言就非常明顯，題目直接提到了「樹狀」，因此這題想必會運用到圖論
事實上，這題可以使用 BFS 或 stack（堆壘）來得到最佳解（皆 $O(n)$ 時間）
```python=
#遞迴 DFS 解
arr = list(map(int, input().split()))
idx, total = 1, 0
def dfs(v): #v 就是父節點，負責依序扣掉子節點的絕對值，再加到答案上
global idx, total
deg = 3 if v % 2 == 1 else 2 #奇數編號有 3 個子節點，偶數則 2 個
for _ in range(deg): #把所有子節點跑一次（利用遞迴來優先把一條路走到底，再走下一條，就是 DFS 的核心思想）
x = arr[idx]
idx += 1
if x == 0: #遇 0 直接跳過，不用處理
continue
total += abs(v-x)
dfs(x)
dfs(arr[0]) #最上層節點即首項（依題意）
print(total)
```
```python=
#Stack 模擬 DFS 解（不使用 deque，但要用也行）
arr = list(map(int, input().split()))
stack = [(arr[0], 3 if arr[0] % 2 == 1 else 2)] #奇數編號有 3 個子節點，偶數則 2 個
idx, total = 1, 0
while stack: #使用 while-loop + stack 代替遞迴，模擬 DFS 效果
v, deg = stack.pop() #以每個元素都形如 (父節點, 子節點數) 儲存，此處把唯一一項拿出並賦值給變數
for _ in range(deg):
x = arr[idx]
idx += 1
if x == 0: #遇 0 直接跳過，不用處理
continue
total += abs(v-x)
stack.append((x, 3 if x % 2 == 1 else 2)) #把更新後的值加回堆中
print(total)
```
### 先加後乘與函數（[j607.](https://zerojudge.tw/ShowProblem?problemid=j607)）
看到題目提到 $f()$ 中可以放入其他值（包括另一個 $f()$）就可以想象到了本題會用到遞迴
針對三種運算（加法、乘法與函數），我們可以以其優先級來建立三個函式（`high()`、`mid()`、`low()`）
接著依其題意來寫函式即可
```python=
inp = input().strip()
def high(i): #最高層的運算：(*) > (+)。"處理乘法鏈"
v, i = mid(i)
while i < len(inp) and inp[i] == '*':
n, i = mid(i + 1)
v *= n
return (v, i)
def mid(i): #加法層級運算：(+) 比 (*) 晚處理。"處理加法鏈"
v, i = low(i)
while i < len(inp) and inp[i] == '+':
n, i = low(i + 1)
v += n
return (v, i)
def low(i): #最基礎的運算：數字直接回傳、f(...) 進括號並 call high()。"處理最小單位"
if inp[i].isdigit():
n = 0
while i < len(inp) and inp[i].isdigit():
n = n * 10 + int(inp[i])
i += 1
return (n, i)
elif inp[i] == 'f':
i += 2 #跳過 "f("
args = []
while True:
v, i = high(i)
args.append(v)
if inp[i] == ',':
i += 1
else:
break
i += 1 #跳過 ")"
return (max(args)-min(args), i)
else:
raise ValueError("Unexpected character: " + inp[i])
ans, _ = high(0)
print(ans)
```
### 連鎖反應（[o713.](https://zerojudge.tw/ShowProblem?problemid=o713)）
這題在 ZeroJudge 上其實相當吃虧，因為題目事實上有提及「每一筆測試資料的執行時間限制均為 1 秒，Python 程式的執行時間限制為 4 秒」
但在 ZJ 中，它似乎沒有把時間限制開這麼大（3 秒）
在真實的 APCS 測驗中，並不會有這種情況發生，題本若有特別注明，判分系統就會那樣跑
本題主要其實就是考 BFS，至於二分搜，聽說考試時可用，但上了 ZJ 會 TLE
正宗 BFS + 二分搜：（ZJ 會 TLE）
```python=
from collections import deque
# 移動方向
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def bfs(mid):
q = deque([(start_x, start_y, mid)])
cnt = 1
vis = [[0] * n for _ in range(m)]
vis[start_x][start_y] = mid + 1
while q and cnt < t:
x, y, l = q.popleft()
if l == 0:
continue
for k in range(4):
nx, ny = x + dx[k], y + dy[k]
if not (0 <= nx < m and 0 <= ny < n):
continue
if a[nx][ny] == -1:
continue
new_l = max(l - 1, a[nx][ny])
if new_l <= vis[nx][ny] - 1:
continue
q.append((nx, ny, new_l))
if vis[nx][ny] == 0:
cnt += 1
vis[nx][ny] = new_l + 1
return cnt >= t
# 輸入
m, n, t = map(int, input().split())
a = []
start_x = start_y = -1
for i in range(m):
row = list(map(int, input().split()))
for j, val in enumerate(row):
if val == -2:
start_x, start_y = i, j
a.append(row)
# 二分搜尋
l, r, ans = 0, m * n, -1
while l <= r:
mid = (l + r) // 2
if bfs(mid):
ans = mid
r = mid - 1
else:
l = mid + 1
print(ans)
```
不用二分搜：（ZJ 可 AC，來源於 ZJ 解答區）
```python=
def main() -> int:
from sys import stdin
from itertools import chain, count
e = stdin.readline
m, n, q = map(int, e().split())
if q == 1: # 特判
return 0
sentinel = (-1,) # 每行最後加上一堵牆 作為sentinel
n += 1 # 因為加上了sentinel 每行寬度+1
# 將輸入壓成一維
l = list(chain.from_iterable(chain(map(int, e().split()), sentinel) for _ in range(m)))
size = len(l) # 壓一維以後的長度 避免出界
for idx, v in enumerate(l): # 找到寶藏
if v == -2:
l[idx] = 0
break
d = (1, n, -1, -n)
vis = {idx}
bfs0, bfs1 = [idx], []
step = {idx: 0} # 紀錄與寶藏之間的步數 用來剪枝
for ans in count(1): # 窮舉答案
nxt0 = []
for i in bfs0:
for di in d:
ni = i + di
# 判斷出界或石頭
if not 0 <= ni < size: continue
lv = l[ni]
if lv == -1: continue
s = step.get(ni)
if s is not None: continue # 已造訪 跳過
# 擴散
step[ni] = ans
nxt0.append(ni)
vis.add(ni)
if len(vis) >= q: return ans
if lv > 0: # 還能傳播再加入下一輪bfs
bfs1.append((ni, lv - 1))
bfs0 = nxt0
while bfs1:
nxt1 = []
for i, v in bfs1:
for di in d:
ni = i + di
# 判斷出界或石頭
if not 0 <= ni < size: continue
lv = l[ni]
if lv == -1: continue
if ni in vis: # 已經傳播過
# 如果更新了該格子的傳播壽命才傳播
if v <= lv: continue
# 在寶藏陷阱覆蓋範圍內的也要判斷是否能更新傳播壽命
s = step.get(ni)
if s is not None and v <= ans - s: continue
lv = v
else:
# 新的格子 連鎖反應
vis.add(ni)
if len(vis) >= q: return ans
# 取較大的壽命傳播
if v > lv: lv = v
# 擴散
l[ni] = lv
if lv > 0: # 還能傳播再加入nxt
nxt1.append((ni, lv - 1))
bfs1 = nxt1
print(main())
```
## [高級題本範例](https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2025/08/04_APCS-%E7%A8%8B%E5%BC%8F%E5%AF%A6%E4%BD%9C%E9%AB%98%E7%B4%9A%E9%A1%8C%E6%9C%AC%E7%AF%84%E4%BE%8B.pdf)
### 美食博覽會（[g278.](https://zerojudge.tw/ShowProblem?problemid=g278)）
### 低地距離（[f315.](https://zerojudge.tw/ShowProblem?problemid=f315)）
### 平緩步道（[j.125](https://zerojudge.tw/ShowProblem?problemid=j125)）
Sign in with Wallet
Connect another wallet