### 前言
這次是本人第二次考APCS意外取得4+4(觀念72分 實作250分壓線)。為了提供Python初學者更多資源，這次以Python作答實作題。
注意：本人對於一行輸入資料轉整數使用map，如果沒學過，把有map的輸入變成[int(x) for x in input().split()]，不過想考四五級分的同學，這一定要學！
開始講解
### [1. 裝飲料](https://zerojudge.tw/ShowProblem?problemid=o711)
#### 主要考點：陣列、for迴圈、if else、模擬
##### 解題邏輯：使用for迴圈取出每個資料，針對每個資料進行以下判斷：
1.目前高度在第一杯：計算增加高度(增加後高度最多到第一杯頂端)計算是否有剩下的飲料，若有，則計算在第二杯的增加高度(最多是第二杯的高度)
2.目前高度在第二杯：計算增加高度(增加高度最多是(第一杯高度加上第二杯高度減目前高度))
3.高度在第二杯頂端：剩下是0，跳出迴圈
[解答](https://hackmd.io/@HankLee0909/SylCd1rlJg)
心得：這題有許多寫法，我見到的都偏長，這題考試時我想的有點久，後面差點沒時間了。第一題有越來越難的趨勢。
### [2. 蒐集寶石](https://zerojudge.tw/ShowProblem?problemid=o712)
主要考點：二維陣列、模擬
解題邏輯：將輸入依序存到變數再依照題目要求完成即可。這算是歷屆第二題數一數二簡單的第二題。右轉90度可以用+1後%4實現。
[解答](https://hackmd.io/@HankLee0909/rys3oWBxke//)
心得：我寫這題時間和第一題差不多，這題不需要太多思考
### [3. 連鎖反應](https://zerojudge.tw/ShowProblem?problemid=o713)
主要考點：BFS、(二分搜逼近)
解題邏輯：此題第一反應應該是二分搜逼近，但在zerojudge 上只有3s，考試為4s。這裡為通過zerojudge的測資，不是用二分搜。首先，計算每個點被初始炸彈炸到的最小半徑，接著從半徑為1往上增加，並如果有半徑大於0的炸彈，進行連鎖反應。引爆q個即為答案。
[解答](https://hackmd.io/@HankLee0909/ByHC6yyMkl)
心得：考試時花時間在這題，某種意義上它比第四題難。
### [4. 搭到終點](https://zerojudge.tw/ShowProblem?problemid=o714)
主要考點：一維DP、前綴和(二分搜)
解題邏輯：先把公車依據到達的終點站由小到大排序，建構DP陣列。DP關係式：到達該站的方法dp[end]=所有在end站下車的公車的總方法，每個公車到達終點方法為從開始到終點前一站的方法總和=sum(dp[該公車起始站:end+1]) end+1是因為要把之前的加上，最後求餘數。
上述實做後應只有20%，觀察測資，m達到10^9 ，但公車結尾最多2 * 10^5 種。如果開一個長度為m的dp陣列，不僅慢而且記憶體容易超標，並且一直sum也很慢，所以TLE。要AC，首先要用前綴和求和，接著dp長度為(幾種不同的終點)，這樣長度最大為2 * (10^5) ，每次使用二分搜尋找起始和終點站的最佳位置，再用前綴和求區間和，並且邊計算邊求餘數減少記憶體，最後考慮搭不到m的情況。
[解答](https://hackmd.io/@HankLee0909/rk9sEzrbkl)
心得：以歷屆DP考題這次比較簡單
### 結語
這次整體偏難，觀念4級分以上從去年10月27.6%到今年剩8.2%，實作題4級分以上只有1.3%，APCS考試會越來越難。