2025/11 APCS高級 心得跟思路紀錄

內文包括許多Latex語句，使用閱讀器等工具閱讀可能造成閱讀障礙。

插播廣告，這週五是校內賽榕資盃，如果我中山一階沒過就會參加，然後會有多一篇比賽文。

先講結論

2025/11/28更新
公布成績：第一題90、第二題30、第三題100，總分220分，五級分過了！
完全是沒有預料到的狀況，這次分數並沒有完全照著題本上的內容執行，執行時間也蠻寬鬆的，意外的幫到我了。

好，真糟糕，漏掉很多細節，還有很多知道的演算法沒做出來。新的機制的高級麻煩在沒有基礎體熱身，還有對於不熟的演算法根本沒時間慢慢想，一定來不及（我的線段樹嗚嗚）

順帶一提，高級實作分數線如下
五級：150+
四級：100+
其餘不給分

他甚至設計了子題拿滿也沒有四級分的機制，我終於意識到北市學科能力競賽的好了

以下解題思路為個人看法，歡迎在最下面留言區理性討論。（我菜勿噴）

郭10竟然一晚上肝出題解了:0 我就不付code了，他應該寫得比較好
本文以簡化題目跟提供方向為主。

第一題 抽牌遊戲

題目說明

輸入整數k（$2<=k<=6$）代表牌的堆數，接下來有k行以空格分開，包含一整數n（$n<=12$），後面接著n組資料，每組資料包含一大寫字母代表牌面文字及一整數代表分數。

規則如下：每次拿取牌堆頂的兩張相同牌面的牌，獲得兩張牌的分數。此操作可以執行到沒有可以拿取的牌為止。

輸出：一整數代表最大可獲得分數

第一子題（30分）：$k=3$
第二子題（70分）：無特別限制

範例輸入

3
3 A 10 B 20 A 10
3 B 20 C 30 A 10
3 A 10 B 20 C 10

範例輸出

100

說明：

1. 從牌堆一拿出A，從牌堆三拿出A，獲得20分
2. 從牌堆一拿出B，從牌堆二拿出B，獲得40分
3. 從牌堆二拿出C，從牌堆三拿出C，獲得40分

總分100分

解題思路

題目類型：遞迴（我的）、DP（優化，由AI贊助播出）

這題就是直接遞迴去做，用vector<int>存每個牌堆開到哪個位置。我的Java腦讓我忘記C++裡面map可以用vector當key，所以漏掉這個優化，大概要被TLE了。

到底要多菜才會忘記C++的map可以用vector當key啊

第二題 影印排程

題目說明

給定整數n（$n>=2$）代表工作數量，接著有k行輸入包含三整數s代表工作最早能開始的時間、e代表工作最晚能結束的時間、t代表工作需要的時間。

影印工作之間不許等待，即若有兩工作

1 5 3
2 9 4

在t=1時開始工作作業1，在t=4時即可以開始作業2。

同時只能有一個工作進行，對於每個工作希望在工作間能讓影印機最長休息r秒（$r = min(e_i - s_{i-1})$)，保證只少有一種排列方式能夠使每個工作皆可完成。

輸出：最長休息時間r

第一子題（30分）：$n<=3$
第二子題（70分）：無特別限制

範例輸入

2
1 5 3
2 9 4

範例輸出

1

說明：工作一在t=1開始，t=4結束，工作二在t=5開始，t=9結束，中間休息1秒。

解題思路

題目類型：貪心（由AI贊助播出）

大致上就是貪心，以先結束的工作先執行，但要注意前一個工作的結束時間。我是對貪心完全沒辦法，我甚至暴力列舉子題一，細節上我還是不知道怎麼做再請各位指教（或是轉而面向我的AI）

我真的該花點時間學習貪心演算法了

第三題 堆疊排序

題目說明

手上有兩個堆疊(stack)能夠pop拿出頂部的東西及push東西進去（先進後出），其中堆疊一是空的，堆疊二有n個整數($n < 20000$)，試利用以下操作

1. 從任一堆疊pop後push到另一堆疊
2. 從任一堆疊pop後輸出

使得輸出為從小到大的順序，求pop需使用到的最少次數。

輸入：整數n，接著有一行n個以空格分開的整數代表堆疊二的內容（第一個數字為堆疊頂部）

輸出：一整數代表最少pop次數

第一子題（30分）：$n<=100$
第二子題（70分）：無特別限制

範例輸入

4
2 3 1 4

範例輸出

7

說明

1. pop 2 到堆疊一，變成[2], [3 1 4]
2. pop 3 到堆疊一，變成[3 2], [1 4]
3. pop 1 輸出，變成[3 2], [4]
4. pop 3 到堆疊二，變成[2], [3 4]
5. pop 2 輸出，變成[], [3 4]
6. pop 3 輸出，變成[], [4]
7. pop 4 輸出，變成[], []

總共7次pop

解題思路

題目類型：BFS（可能只有30分）、線段樹（移動優化）

這題可以簡化成一維地圖上面依序找點，到目的地後刪除該點，求總距離最短（BFS搜尋）。（可以想像堆疊一開口向右，堆疊二開口向左，中間分隔就是走路的人）

這題我直接記錄每個點的位置，透過比大小判斷往左或往右（有點貪心的味道？），走到的點就設為0，然後每次走的距離就加上去。但是中間想到線段樹可以用（有學過，甚至是兩週前看過）但是不知道怎麼實作所以沒辦法。（我甚至很認真的畫了一個計算紙的樹）

如果沒有線段樹會TLE我可能會哭出來。

結語

這次其實有很多思路是查了之後馬後砲的，主要是對於演算法不熟悉不夠靈活運用，期待下次能做的更好。