最後更新日期 2024 / 01 / 01
筆者只是一個滿級的考生
以下內容都是根據個人經驗給出的建議
考試名額不多
很快就會被搶完
所以開放報名第一時間記得趕快上去搶
然後第一次應考前一定要先下載官方的虛擬環境練習
並且留意自己習慣的編輯器、IDE 有沒有在環境裡面
如果沒有的話就要事先練習好其他軟體的操作方式
APCS 的實作題每次考試總共會有 4 題
每題 20 筆測資
每筆測資只要對了就可以獲得 5 分
所以就算沒辦法拿滿分
寫多少算多少
一定要傳上去
如果只是要拿二級的話
其實練習方式還蠻廣的
基本上所有"會寫程式的人"都可以達到這個等級
也就是說
不管你想去寫網頁、開發遊戲、刷題目都應該可以達到 2 級這個目標
APCS 的 3 級範圍非常吃實作能力
需要邏輯清晰且可以處理複雜的操作才能達到 3 級
一個比較複雜的例子:APCS 2022/10 貨運站
而且在第二題當中
二維陣列操作出現的的頻率非常高
必須非常熟悉二維陣列
最後建議想達到 3 級分的話可以多練歷屆 APCS 第二題
不過如果你的目標是更高的級分
其實不需要刷太多歷屆第二題
通常隨著能力提升實作能力也會自然提升
4 級跟 5 級的範圍其實差不多
不過最大的差別就是要拿到 4 級只需要知道比較淺的知識就行了
那想達到 4/5 級的話就非常吃演算法和資料結構的運用能力
非常推薦這份 AP325 講義
題目的部分
很常出現經典題或者經典題稍微改編
所以也很建議去 CSES 這個很多經典題的 Judge 多刷點題
可以配合 CSES 寶典 一起讀
集結了多位 APCS 滿級分的出題者與驗題者
我們在每個月都會辦一場 APCS 模擬賽
如果還不清楚自己練習方向或想測試實力的話
歡迎加入 Discord 群組參與模擬賽
重點是完全免費!!
這次 APCS 跟 ISSC 撞期 然後我就放掉 APCS 跑去打 ISSC : D 下一次要慢三天才能報了 qwq數線上有一隻老鼠 且有 n 個食物散落在數線上 老鼠可以選擇一直往左或一直往右 求最多可以吃到幾個食物及最後吃食物的位置把問題轉換一下 就變成是在問老鼠左邊還是右邊食物比較多、最左邊或最右邊的食物在哪裡 於是只要簡單維護一下就可以幾個變數就可以解出來了基本語法cppusing namespace std;signed main { int x, n, tmp; cin x n; int cntl = 0, cntr = 0; 左邊與右邊食物數量 int maxv = -1e5, minv = 1e5; 用最大與最小值維護最後停在的食物位置 while n-- { cin tmp; if tmp = x cntr++; 如果食物在左邊 if tmp = x cntl++; 如果食物在右邊 maxv = maxmaxv, tmp; minv = minminv, tmp; } if cntl cntr cout cntl " " minv endl; 往做邊走解更優 else cout cntr " " maxv endl; 否則決定往右邊走}在一個 n times m 大小的表格上每格裡都有一張牌 你可以水平或垂直消除數值為 x 的兩張牌並獲得 x 分,但中間不能有其他牌 求最多能獲得多少分枚舉每張牌,嘗試上或左匹配是否存在相同的牌即可 使用 -1 紀錄已經匹配掉的牌至於為什麼只要匹配左上不用考慮右下 是因為左跟右、還有上跟下是相對關係我比較在意的地方是 本來以為這個動作需要重複多次才能匹配所有牌 結果竟然一次就過了,不知道是不是 ZeroJudge 測資太弱 🤔或者其實有辦法證明這個作法最多只需要一次更新關於這個問題,感謝 MSQRT 電神的補充 確實 Zerojudge 測資有疏失 已加強程式碼!二維陣列、模擬cppusing namespace std;int tb5050; 表格signed main { int n, m; cin n m; 輸入資料 for int i = 0; i n; i++ { for int j = 0; j m; j++ { cin tbij; } } int ans = 0; 重複執行匹配動作至少 nm 次以配對所有卡牌 for int = 0; 1000; ++ { for int i = 0; i n; i++ { for int j = 0; j m; j++ { if tbij == -1 continue; 嘗試往上配對 if i 0 { int k = i-1; while k = 0 tbkj == -1 k--; if tbij == tbkj { 配對成功 ans += tbij; 增加分數 tbij = tbkj = -1; 將兩張牌紀錄乘已匹配 continue; 匹配成功後即可忽略這張牌 } } 嘗試往左配對 if j 0 { int k = j-1; while k = 0 tbik == -1 k--; if tbij == tbik { 配對成功 ans += tbij; 增加分數 tbik = tbij = -1; 將兩張牌紀錄乘已匹配 continue; 匹配成功後即可忽略這張牌 } } } } } cout ans endl;}一個 n times m 的表格上每格有一個水管 水管分成 H、I、F、7、L 等類型 每種水管可能連接到上、下、左、右其中某些方向 求將水管連起來後最大連通塊本題詳細題意建議直接進 ZeroJudge 題目頁面查看簡單來說只要對整張圖做 DFS 並一邊維護連通塊大小即可 比較麻煩的地方就是建圖而已 這份程式碼部份參考了 dreamoon 老師的 code 才得以把它改得這麼乾淨的 時間複雜度 Onm圖論、DFS BFScppusing namespace std; 上 右 下 左mapchar, vectorint mask{ {'X', {1,1,1,1}}, {'I', {1,0,1,0}}, {'H', {0,1,0,1}}, {'L', {1,1,0,0}}, {'7', {0,0,1,1}}, {'F', {0,1,1,0}}, {'J', {1,0,0,1}}, {'0', {0,0,0,0}},};vectorint graph500000; 存圖bool vis500000; 紀錄造訪過的點int ans = 0, cur = 0;int n, m; 對每座標分配一個 idint id int x, int y { return x m + y;} DFS 並維護連通塊大小void dfsint id { cur++; visid = true; for auto u : graphid { if visu continue; visu = true; dfsu; }}signed main { cin n m; vectorstring vn; for int i = 0; i n; i++ cin vi; 建立整張圖 for int i = 0; i n; i++ { for int j = 0; j m; j++ { 上配下 if i + 1 n maskvij2 maskvi + 1j0 { graphidi, j.pushbackidi + 1, j; graphidi + 1, j.pushbackidi, j; } 左配右 if j + 1 m maskvij1 maskvij + 13 { graphidi, j.pushbackidi, j + 1; graphidi, j + 1.pushbackidi, j; } } } 對每一個節點做 DFS for int i = 0; i n; i++ { for int j = 0; j m; j++ { cur = 0; dfsidi, j; ans = maxans, cur; 嘗試更新答案 } } cout ans endl;}題目~~廢話~~劇情就不多寫了 簡單來說就是求最大連續子序列合,但可以跳過 k 個元素在不考慮 k 的情況下 這是一個非常經典的問題 解法的話也非常多元 以現在這題來說 Kadane's Algorithm 應該會是比較好做的那如果把 k 的條件加進去呢? 把測資範圍仔細讀過之後可以注意到 k leq 20 考慮動態規劃的作法 我們定義 dpi 為考慮陣列前 i 個元素的最佳解 然後我們可以往前跳過不超過 k 個 因此 dpi 可以從 dpi-1、dpi-2 cdots dpi-k-1 轉移過來取 max 但我們還需要紀錄總共已經使用了幾個金牌 所以再開一個維度來維護這個資訊綜合以上幾點,我們可以推出這樣的轉移式 定義 dpij 為考慮前 i 個元素且使用 j 個金牌的最佳解 轉移的部份 dpij = max{1 leq l leq k}dpi-l-1j-l + vali最後照著轉移式把程式寫出來就好ㄌ時間複雜度 On times k^2更新感謝 Colten 提出了 更好的作法 dpij 一樣是代表在第 i 天使用 j 個金牌的最佳解 不過轉移的部份只需要對 dpi-1j-1 和 dpi-1j + vali 取 max 就可以 兩個狀態分別代表在第 i 天使用和不使用金牌 時間複雜度直接少了一個 k 降到 On times k 下面程式碼也用這個寫法實現然後根據 吳邦一教授的說法 原本 On times k^2 的作法如果使用 Python 的話時間應該不會過動態規劃cppusing namespace std;int v200000;int dp20000030;signed main { int n, k; cin n k; for int i = 1; i = n; i++ { 第 i 天 cin vi; 因為只會依賴到之前的狀態所以可以邊讀入邊做 for int j = 0; j = k; j++ { 使用 j 個金牌 if j 0 dpij = dpi-1j-1; 使用金牌 dpij = maxdpij, dpi-1j + vi; 不使用金牌 } } int ans = 0; 在所有合法狀態中取得最佳解 for int i = 0; i = k; i++ { for int j = 1; j = n; j++ { ans = max{ans, dpji, 0LL}; } } cout ans endl;}整體來說 這次 APCS 其實不算太難(? 第三題實做比較麻煩一點以外 最後一題 DP 轉移式也還算好推
APCS事情是這樣的,前陣子在開發的網頁背景有個星空,於是就想說不如來加點星空的閃爍特效吧!於是就先寫了這樣的 CSS:alt text不過這樣當然是不夠的,每個星星同時閃爍太不自然了,於是我加了一點隨機的 delay:alt text看起來是會隨機閃爍了,但在頁面剛載入進去的時候因為很多星星都還在 delay 中,畫面特別的空虛。這時候我就想了,有沒有可能讓 CSS 動畫從中途開始播放?上網一查,原來還真的可以!只要把 animation-delay 的值改成負數就行了!比如說 animation-delay: -3s 就是指從 3 秒開始的動畫。於是最後我把程式碼改成了這樣:alt text~~GIF 錄起來品質好像不是很好,但還是放一下好了~~
Web給予一堆數字 1 sim n 但中間缺少了一個 你的任務是找出那個缺少的數字已知數字 1 sim n 的總和為 sum^n{k=1}k 可以透過梯形公式 frac{n1 + n}{2} 快速求出來 所以我們只要用期望的 1 sim n 總和減掉輸入的所有數字就可以算出答案了cppusing namespace std; main { iosbase::syncwithstdiofalse;cin.tie0; int n, sum = 0; cin n; for int i = 0; i n-1; i++ { int tmp; cin tmp; sum += tmp; } cout 1 + n n 2 - sum endl;}
CSES