跳到正文

CSCI2740

競賽編程

區間查詢與線段樹、圖搜索、連通性與最短路徑、字串匹配、數論、計算幾何、動態規劃、貪心算法及無偏遊戲。

19 章 · 33 節EN · 繁 · 简
我的課程筆記

你的進度

0/ 33 節已標記完成

下一節: 二元索引樹:區間、更新與前綴和

完成記錄儲存在此瀏覽器中。

這門課在網上

CSCI2740 筆記裏的內容

定理卡
97
定義
54
反例
50
概念視角
17
思想史
0
證明透視
47

這門課的概念視角還沒有記錄到網上。

在知識圖譜中打開這門課

數字只算這門課 33 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。

在網上定理卡 97 · 定義 54 · 反例 50 · 概念視角 17 · 證明透視 47

這門課的概念視角還沒有記錄到網上。

在知識圖譜中打開這門課

數字只算這門課 33 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。

第 1 章 · 5 節

區間查詢

從儲存區間的不變量推導 Fenwick 樹的查詢與更新,證明對數時間界,並區分增量、賦值及最小值查詢。

定理 12 · 定義 5反例 7視角 4證明透視 5

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 1.1

    二元索引樹:區間、更新與前綴和

    從儲存區間的不變量推導 Fenwick 樹的查詢與更新,證明對數時間界,並區分增量、賦值及最小值查詢。

  2. 1.2

    用線段樹處理賦值與區間最小值

    證明線段樹的不變量,以及單點賦值下對數時間區間最小值查詢。

  3. 1.3

    線段樹:結合式摘要與有序區間查詢

    推導結合式摘要的有序線段查詢,並區分單點更新及延遲傳播。

  4. 1.4

    二維前綴和與矩形差分

    推導四角總和查詢與離線矩形加法,明確處理半開邊界、空矩形及預處理成本。

  5. 1.5

    平方根分塊:延後加法與區間總和

    分清儲存值、延後區塊加量與真實區塊總和,證明可交錯執行的區間加法及總和查詢。

第 2 章 · 1 節

2. 靜態區間查詢

預處理二的冪長度區間以查詢靜態最小值。

定理 3 · 定義 2反例 3證明透視 2

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 2.1

    靜態區間最小值的稀疏表

    證明二的冪長度區間不變量,解釋重疊最小值查詢。

第 3 章 · 1 節

圖的連通性

無向多重圖的 DFS low-link 與橋邊。

定理 2 · 定義 2反例 1視角 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 3.1

    無向多重圖中的 DFS 橋邊

    保留平行邊身分,證明 low-link 橋邊判準。

第 4 章 · 1 節

區間更新

以端點差分處理區間加法與單點值。

定理 1 · 定義 1反例 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 4.1

    差分陣列與區間加法端點

    證明離線區間加法的端點不變量,並連繫 Fenwick 單點查詢。

第 5 章 · 1 節

無偏遊戲

有限正常玩法、mex 與異或。

定理 3 · 定義 2反例 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 5.1

    無偏遊戲的 mex 值與異或

    證明有限無偏正常玩法遊戲的異或法則,並跟蹤取子遊戲。

第 6 章 · 1 節

因數篩法

Möbius 因數和及互質配對計數。

定理 3 · 定義 1反例 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 6.1

    Möbius 因數和與互質配對

    證明因數指示式,並以倍數篩計算互質索引對。

第 7 章 · 1 節

加權區間排程

由相容前綴建立動態規劃。

定理 1 · 定義 1反例 1視角 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 7.1

    加權區間排程

    推導加權區間的前驅遞推、重建及複雜度。

第 8 章 · 3 節

計算幾何

利用定向與有向面積判斷點相對於凸多邊形的位置。

定理 9 · 定義 5反例 4視角 2證明透視 4

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 8.1

    有向面積與凸多邊形內的點

    運用叉積、邊界測試與鞋帶和,明確說明凸性及整數範圍假設。

  2. 8.2

    方向與閉線段相交

    精確分類線段相交,包括共線和退化情形。

  3. 8.3

    單調鏈凸包與共線點

    構造凸包極點並證明按列分組的單調鏈算法。

第 9 章 · 2 節

字串算法

利用前後綴及回退搜尋重疊字串。

定理 9 · 定義 4反例 3視角 1證明透視 4

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 9.1

    KMP 字串匹配:前後綴、回退與重疊匹配

    從巢狀前後綴推導前綴函數,證明線性搜尋,保留重疊出現,並由最長真前後綴求最小週期。

  2. 9.2

    Z 陣列、區間重用與精確字串匹配

    證明前綴匹配重用的線性複雜度,並用 Z 值求精確匹配、前後綴與週期。

第 10 章 · 3 節

圖搜索與連通性

低鏈值、橋邊、有向分量與刪點。

定理 7 · 定義 5反例 6視角 1證明透視 7

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 10.1

    迭代低鏈值搜索與橋森林

    追蹤以邊編號實作的迭代低鏈值計算,並構造由橋連結的森林。

  2. 10.2

    強連通分量、完成次序與凝聚圖

    推導兩遍有向 DFS 算法及其無環凝聚圖。

  3. 10.3

    割點、DFS 根與刪點後的連通分量數

    推導 low-link 刪點判準並計算餘下連通分量。

第 11 章 · 1 節

二進冪

迴圈不變量、模冪及矩陣應用。

定理 2 · 定義 1反例 2證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 11.1

    二進冪:迴圈不變量、矩陣遞推與遊走計數

    不靠交換律證明二進冪並應用矩陣冪。

第 12 章 · 1 節

單調佇列

視窗極值、支配關係與攤銷成本。

定理 3 · 定義 1反例 2證明透視 3

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 12.1

    滑動視窗最小值:支配、到期與單調雙端佇列

    證明支配關係、處理重複值並界定雙端佇列總工作量。

第 13 章 · 2 節

輕重鏈剖分

樹路徑、子樹大小與區間查詢邊界。

定理 8 · 定義 4反例 4證明透視 4

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 13.1

    輕重鏈路徑與查詢邊界

    證明輕邊數量界,並把頂點及邊路徑劃分為區間查詢。

  2. 13.2

    祖先倍增、第 k 祖先與最近共同祖先

    組合父映射的冪,證明最近共同祖先的同步跳躍不變量,並在靜態樹查詢中避免虛構根以上的祖先。

第 14 章 · 2 節

子集動態規劃

精確已訪集合狀態、路線代價與最優路線。

定理 8 · 定義 3反例 3視角 1證明透視 2

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 14.1

    子集狀態、哈密頓巡迴與最優路線

    推導精確已訪集合動態規劃並還原最優有向巡迴。

  2. 14.2

    遞增子序列:最小尾值與有效見證

    證明最小尾值不變量,處理相等值,並重建真正的子序列而不是把尾值陣列當作見證。

第 17 章 · 2 節

數論

同餘式、中國剩餘定理與線性篩法。

定理 5 · 定義 3反例 3視角 2證明透視 2

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 17.1

    精確算法:同餘與幾何定向

    以擴展歐幾里得算法解線性同餘式,在模數不必互質時合併同餘式,並為定向測試與模冪保持精確的邊界檢查。

  2. 17.2

    線性篩法:最小質因數與多次分解查詢

    證明合成數的唯一生成規則,建立最小質因數表,並說清楚質因數提取的預處理、輸出及算術成本。

第 16 章 · 3 節

最短路徑

含負圈的 Bellman-Ford,以及使用雙端佇列的 0-1 BFS。

定理 13 · 定義 7反例 4視角 3證明透視 3

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 16.1

    同步 Bellman–Ford:最短途徑、負圈,以及額外一輪所證明的事

    證明 Bellman-Ford 背後的限長遞推式,把距離分為有限、無窮及負無窮,並說明額外一輪所能證明的事。

  2. 16.2

    0–1 BFS:為甚麼雙端佇列可以取代優先佇列

    當每條邊的成本為 0 或 1 時,用雙端佇列計算最短距離,並證明雙鍵不變量、處理過時項目及分析複雜度。

  3. 16.3

    Dijkstra 與 Floyd–Warshall:單源與全點對最短路徑

    證明非負權重下的 Dijkstra 算法,指出負權邊究竟在哪一步令它失效,並推導計算全點對距離的 Floyd–Warshall 遞推式。

第 15 章 · 1 節

搜尋與答案二分

對單調可行性判斷進行二分搜尋。

定理 2 · 定義 1反例 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 15.1

    對容量進行二分搜尋:先證明可行性測試

    把最小化問題化為單調的是非判斷,證明貪心可行性測試,並以安全的上下界與運算對答案進行二分搜尋。

第 18 章 · 1 節

最小生成樹

不相交集合、Kruskal 與 Prim,以及割性質。

定理 3 · 定義 3反例 1視角 1證明透視 2

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 18.1

    不相交集合、Kruskal 算法與 Prim 算法

    證明最小生成樹的割性質,在不相交集合並查集上實作 Kruskal 算法,並與 Prim 算法比較。

第 19 章 · 1 節

貪心算法

區間調度與工作次序的交換論證。

定理 3 · 定義 3反例 2證明透視 2

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 19.1

    貪心算法與交換論證:區間調度與最優工作次序

    闡明貪心選擇的證明模式,並以交換論證證明區間調度及按加權完成時間排序的貪心規則,同時說明為何看似合理的貪心規則會失敗。

Vercel 瀏覽統計與公開頁面效能量度均須分別取得同意,兩者均非使用網站的必要條件。

網站功能儲存(按需使用)

安全、登入及你選擇的偏好會按需使用儲存,與可選統計分開處理。

撤回會停止後續統計;需要卸載已載入的統計程式時,頁面會重新載入。已傳送的資料不會因此刪除。

查看 Cookie 與儲存詳情