最後更新日期 2024 / 01 / 01
頁面待完成…
一個在因倍數相關題目可以用到的小技巧 程式碼大概像這樣 可以得到 On log n 的時間複雜度cppfor int i = 0; i n; i++ { for int j = 0; j n; j += i { to something }}n log n approx sum{k=1}^n frac 1 k = 1 + frac 1 2 + frac 1 3 + frac 1 4 + cdots + frac 1 n br
Math筆者只是一個滿級的考生 以下內容都是根據個人經驗給出的建議考試名額不多 很快就會被搶完 所以開放報名第一時間記得趕快上去搶然後第一次應考前一定要先下載官方的虛擬環境 並且留意自己習慣的編輯器、IDE 有沒有在環境裡面 如果沒有的話就要事先練習好其他軟體的操作方式APCS 的實作題每次考試總共會有 4 題 每題 20 筆測資 每筆測資只要對了就可以獲得 5 分 所以就算沒辦法拿滿分 寫多少算多少 一定要傳上去- 基本程式語法如果只是要拿二級的話 其實練習方式還蠻廣的 基本上所有"會寫程式的人"都可以達到這個等級 也就是說 不管你想去寫網頁、開發遊戲、刷題目都應該可以達到 2 級這個目標- 二維陣列- 複雜模擬APCS 的 3 級範圍非常吃實作能力 需要邏輯清晰且可以處理複雜的操作才能達到 3 級 一個比較複雜的例子：APCS 202210 貨運站 而且在第二題當中 二維陣列操作出現的的頻率非常高 必須非常熟悉二維陣列 最後建議想達到 3 級分的話可以多練歷屆 APCS 第二題不過如果你的目標是更高的級分 其實不需要刷太多歷屆第二題 通常隨著能力提升實作能力也會自然提升- 排序- 搜尋- 貪心- 遞迴- 動態規劃- 資料結構4 級跟 5 級的範圍其實差不多 不過最大的差別就是要拿到 4 級只需要知道比較淺的知識就行了 那想達到 45 級的話就非常吃演算法和資料結構的運用能力 非常推薦這份 AP325 講義題目的部分 很常出現經典題或者經典題稍微改編 所以也很建議去 CSES 這個很多經典題的 Judge 多刷點題 可以配合 CSES 寶典 一起讀集結了多位 APCS 滿級分的出題者與驗題者 我們在每個月都會辦一場 APCS 模擬賽 如果還不清楚自己練習方向或想測試實力的話 歡迎加入 Discord 群組 重點是完全免費！！
APCS兩個人到一個 n times m 大的迷宮裡探險 在迷宮裡只能往右和往下走 而入口在 1, 1 出口在 n, m 求離開迷宮最多能帶走多少寶藏 迷宮示意圖如下problem image應該不難聯想到這題 CSES - Grid Paths 只要把狀態開成四維 分別代表第一個人的 xy 座標及第二個人的 xy 坐標 然後可以推出：begin{equation}dpijkl = gridij + text{max} begin{cases} dpi-1jk-1l dpi-1jkl-1 dpij-1k-1l dpij-1kl-1 end{cases}end{equation}不過加上 gridij 的部份有些細節要處理 詳細轉移的部份自己看下面的程式碼在本地測試了一下就順利通過了範測 ouob結果剛剛的作法傳上去之後很快就拿到 TLE 了 於是就想說順便來嘗試看看最近剛學到的壓常小技巧cpp加上去後通過了更多比測資但依然還是 TLE又仔細思考了一下題目 發現 i + j neq k + l 的狀態一定不合法 所以就把不合法的狀態 continue 掉然後就神奇的成功壓常 AC 了 :Dcppusing namespace std;const int MAXN = 1e2 + 3;const int INF = 32000;int mpMAXNMAXN;int dpMAXNMAXNMAXNMAXN;signed main { iosbase::syncwithstdio0; cin.tie0; cout.tie0; int n, m; cin n m; 把邊界都設定為 -INF for int i = 0; i = n + 1; i++ { for int j = 0; j = m + 1; j++ { for int k = 0; k = n + 1; k++ { for int l = 0; l = m + 1; l++ { if i == 0 || i == n+1 || j == 0 || j == m+1 || k == 0 || k == n+1 || l == 0 || l == m+1 { dpijkl = -INF; } } } } } 初始狀態 dp0000 = 0; dp0101 = 0; dp1010 = 0; dp0110 = 0; dp1111 = 0; 輸入整張地圖 for int i = 1; i = n; i++ { for int j = 1; j = m; j++ { cin mpij; } } DP for int i = 1; i = n; i++ { for int j = 1; j = m; j++ { for int k = 1; k = n; k++ { for int l = 1; l = m; l++ { 一點點剪枝 if i + j = k + l continue; if mpij == -1 || mpkl == -1 { dpijkl = -INF; continue; } 轉移 dpijkl = max{ dpi-1jk-1l, dpi-1jkl-1, dpij-1k-1l, dpij-1kl-1, }; 拿到寶藏增加分數 dpijkl += mpij == 1 + mpkl == 1 i = k || j = l; } } } } 輸出答案 cout maxdpnmnm, short0 endl;}
TIOJ