最後更新日期 2024 / 01 / 01

調和級數

簡介

一個在因倍數相關題目可以用到的小技巧
程式碼大概像這樣
可以得到 O(nlogn) 的時間複雜度

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j += i) {
        // to something
    }
}

公式

nlognk=1n1k=1+12+13+14++1n

例題

https://codeforces.com/contest/1850/problem/F
https://cses.fi/problemset/task/1081/

推薦文章

APCS 實作滿級完全攻略

筆者只是一個滿級的考生 以下內容都是根據個人經驗給出的建議考試名額不多 很快就會被搶完 所以開放報名第一時間記得趕快上去搶然後第一次應考前一定要先下載官方的虛擬環境 並且留意自己習慣的編輯器、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

個人推薦書籍列表

這份清單會持續更新喔 table tr th封面th th書名th th簡介th th評價th tr tr tdimg src=" width=300td td原子習慣td td本書介紹了習慣的強大力量,且提出了多個有別於傳統框架的習慣養成法td td從早上起床到夜晚入睡,人類生活中很大部分的一切都受習慣所控制。我從沒想過,習慣竟然強大到是足以改變人的一生。以前我們總是被教導著,養成一個好習慣就是要靠強大的意志力,看完之後才知道,原來那些我們認為意志力很強大的人,往往是最少用到意志力的td tr tr tdimg src=" width=300td td六分鐘日記的魔法td td以正向心理學、習慣、自我反省等多種理論研究構成,一本通往快樂、更充實人生的日記td td待補td trtable

Other

很多最短路演算法

每次選擇最近的節點 嘗試透過該節點來更新相鄰節點距離將所有節點距離初始化為 infty 起點為 0 選擇目前距離起點最近的節點 如果目前節點距離加上相鄰節點與目前節點距離小於起點到相鄰節點的距離就更新cppfor int i = 1; i = n; i++ distancei = INF;distancex = 0;q.push{0, x};while q.empty { int a = q.top.second; q.pop; 絕對不會更新到的話直接 continue 掉 if a.first distnow.second continue; for auto u : adja { int b = u.first, w = u.second; if distancea + w distanceb { distanceb = distancea + w; 因為要讓距離小的排在前面所以加負號 q.push{-distanceb, b}; } }}這個演算法是由某個 DP 概念延伸出來的 最初的轉移式大概長這樣定義: dpkij 為 i 到 j 的最短距離,且只能經過額外的 k 個點轉移式: mathrm {dp} i,j,k=mathrm {min} {Big }mathrm {dp} i,j,k-1,mathrm {dp} i,k,k-1+mathrm {dp} k,j,k-1{Big }依照 DP 轉移式枚舉每個點做轉移就好了 實作上由於 k 是按照順序轉移的所以可以把空間壓到二維 記得要注意迴圈是由外而內順序是 k、i、j cppfor int k = 1; k = n; k++ { for int i = 1; i = n; i++ { for int j = 1; j = n; j++ { distij = mindistij, distik + distkj; } }}如果不小心忘記寫成 i j k 的話只要做三次就會對了 2019 年的某篇論文上提到了這點如果任一個 distii 0 若且唯若存在負環 代表有一個點自己繞一圈回到自己距離小於 0 但如果是無向圖的話的負環就很難判斷了對於每個邊嘗試更新連接的兩個點對於起點的距離重複 n-1 次嘗試更新所有的邊cppfor int i = 1; i = n; i++ disti = INF; distx = 0; for int i = 1; i = n-1; i++ { for auto e : edges { int a, b, w; tiea, b, w = e; distb = mindistb, dista + w; } }}如果更新了 n-1 次還能繼續更新 代表這張圖存在負環看完這些之後 想必一定有人會覺得「為什麼要學這麼多種最短路演算法」 原因很簡單,因為這些演算法各自有不同的特性與效率 所以需要適時挑選適合的演算法來使用不過比較值得注意的是 事實上如果要求多源最短路的話 枚舉每個點做 Dijkstra 甚至比 Floyd-Warshall 還快| | Bellman-Ford | Dijkstra | Floyd-Warshall || --- | --- | --- | --- || 類型 | 單點源 | 單點源 | 全點對 || 限制 | 任意圖 | 無負邊 | 任意圖 || 時間複雜度 | OVE | OE log E | OV^3 || 用途 | 檢查負環 | 快速單點源 | 負邊全點對 |

Algorithms