NOIP算法學習筆記

第一板塊——基本算法

搜索

雙向廣搜

常見用法

OI-Wiki 雙向搜索

補充

雙向廣搜判無解的效率一般比不上普通廣搜

題目

P1379 八數碼難題
簡要思路：把 \(string\) 的狀態存到 \(map\) 中，再把每個位置的可拓展的狀態代表出來，跑雙向 \(bfs\) 即可

第二板塊——數學

位運算

常見用法

OI-Wiki 位運算

組合數學

排列組合

常見用法

OI-Wiki 排列組合

補充

\[\begin{pmatrix}n \\m \\ \end{pmatrix} = \begin{pmatrix}n-1 \\m \\ \end{pmatrix} + \begin{pmatrix}n-1 \\m-1 \\ \end{pmatrix} \]
\[\sum^n_{i=1} \normalsize\begin{pmatrix}n \\i \\ \end{pmatrix} = 2^n \]

題目

P7481 夢現時刻
 題解
簡要思路：推 \(F_{a,b}\) 遞推式，用組合數遞推式化簡

第三板塊——圖論

拓撲排序

常見用法

OI-Wiki 拓撲排序

題目

P1347 排序
簡要思路：按照小于關系拓撲建邊，有以下幾種情況：

出現環，則不合法
圖不連通但沒出現環，則有無窮多解
否則，有唯一解

差分約束

常見用法

OI-Wiki 差分約束

補充

差分約束中，跑最短路還是最長路看不等式的符號，一般而言，\(dis_u \le dis_v+w\) 跑最短路，\(dis_u \ge dis_v+w\) 跑最長路
差分約束中，一般情況下（建超級源點 \(0\)，初始 \(dis_0 = 0\)），
如果跑最短路，那么對于 \(i\in[1,n],dis_i \le 0\)。
如果跑最長路，那么對于 \(i\in[1,n],dis_i \ge 0\)。
所以，當題目中要求 \(i\in[1,n],A_i \le 0\)，可以直接跑最短路，反之跑最長路
形如 \(A_u =(\le或\ge) x\) 的等式，可以建超級點 \(n+1\)，轉化為 \(dis_u =(\le或\ge) dis_{n+1}+x\)，這里只討論跑最短路的情況，最長路同理：
跑最短路后，可以發現，超級點的值也會更新，此時，超級點的值其實為 \(\min_{i\in[1,n] \land A_i確定} A_i\)，但我們想要的是 \(dis_0 = 0\)，所以 \(dis_i\) 的真實值為 \(dis_i-dis_0\)

題目

P4926 [1007] 倍殺測量者
簡要思路：給式子兩邊都取 \(log\)，套差分約束板子即可
P5590 賽車游戲
簡要思路：轉換為 \(dis_a - dis_b \in [1,9]\)，跑差分約束。有幾點要注意：
1.注意判斷 \(1\) 能否到 \(n\)
2.如果有邊不在 \(1\) 到 \(n\) 的路徑上，就把這些邊去掉，不然會影響差分約束的判斷

最短路

易錯點

假如有負權邊，當 \(w\) 為負數時，如果 \(dis_u\) 和 \(dis_v\) 為 \(inf\) 時，\(dis_v\) 就會被更新，所以要么最后判斷時不寫 "\(==inf\)"，要么在松弛時判斷 \(dis_u\) 不為 \(inf\)（\(Floyd\) 松弛同理）

Bellman-Ford

常見用法

OI-Wiki Bellman-Ford

補充

有邊數限制的題可以考慮 \(Bellman-Ford\)
比如：求從 \(1\) 號點到 \(n\) 號點的最多經過 \(k\) 條邊的最短距離
細節：\(Bellman-Ford\) 有每輪更新有串聯效應，比如在一輪中，\(1\) 更新 \(2\) ，更新了的 \(2\) 又更新 \(3\) ，這樣就不保證最多經過 \(k\) 條邊，所以應再加一維，可用滾動數組優化。

Dijkstra

常見用法

OI-Wiki Dijkstra

題目

P1144 最短路計數
簡要思路：松弛時，\(dis_u+w<dis_v\) 就 \(cnt[v]=cnt[u]\)，\(dis_u+w=dis_v\) 就 \(cnt[v]+=cnt[u]\)，原因顯然
P1462 通往奧格瑞瑪的道路
簡要思路：直接做不容易，考慮二分答案，于是 \(check(x)\) 就要判斷能否從 \(1\) 到 \(n\) 經過一些邊，邊權 \(\le x\)，且邊權和小于血量。重新建圖，跑最短路判斷即可
P5304 [GXOI/GZOI2019] 旅行者
簡要思路：考慮把點分成兩個集合，建兩個超級源點分別與這兩個集合的點連邊，則它們的最短路就是兩集合之間最短路的最小值。但任意兩點的最小值可能在集合內，此時我們考慮重新劃分集合，容易發現，可以枚舉二進制中的第 \(i\) 位，為 \(0\) 的放進一個集合，為 \(1\) 的放進另一個集合，這樣就一定能找到最小值，原因顯然

Floyd

常見用法

OI-Wiki Floyd

補充

注意重邊（ \(dp_{x,y}=min(dp_{x,y},z)\) ）

題目

P6175 無向圖的最小環問題
簡要思路：見 OI-Wiki 最小環
P1730 最小密度路徑
簡要思路：因為是有向無環圖，所以任意兩點之間的最小密度路徑長度不會超過 \(n\)，所以 \(O(n^5)\) 暴力 \(DP\) 即可，再想優化可以參考題解
P1613 跑路
簡要思路：數據范圍小，考慮 \(Floyd\)，由于一次可以跑 \(2^k\)，所以我們可以預處理出 \(x\) 到 \(y\) 是否有長度為 \(2^k\) 的邊（倍增思想），再跑 \(Floyd\)，時間復雜度 \(O(n^4)\)

Johnson

常見用法

OI-Wiki Johnson

分層圖

常見用法

OI-Wiki 分層圖

題目

P4568 [JLOI2011] 飛行路線
簡要思路：板子題
P1266 速度限制
簡要思路：對于速度可以建分層圖，實現時可以定義 \(dp_{i,j}\) 表示到 \(i\) 時速度為 \(j\) 的最短路，時間復雜度 \(O(V_{max} \times m \times \log m)\)

連通性

常見用法

OI-Wiki 強連通分量
 OI-Wiki 雙連通分量
 OI-Wiki 割點和橋

補充

有向圖用 \(scc\)，無向圖用 \(edcc\) 或 \(vdcc\)，有時也可以兩種圖互相轉換
縮點后會形成一顆樹或 \(DAG\)，可以從上面找性質，求答案
注意 \(scc\) 或 \(vdcc\) 或 \(edcc\) 里面的性質
一些題目可以圖論建模

題目

P5058 [ZJOI2004] 嗅探器
簡要思路：題解
P3225 [HNOI2012] 礦場搭建
簡要思路：題解
P1407 [國家集訓隊] 穩定婚姻
簡要思路：題解

基環樹

補充

基環樹找環：
\((1)\) 無向圖通過一個動態數組，只有 \(v\) 為該動態數組的最后一位的值時才把 \(u\) 加進去（還需特判 \(u\) 為入環點的情況）
\((2)\) 有向圖中，內向圖用 \(topo\)，外向圖轉為內向圖
基環樹的處理方法：
\((1)\)在環上找性質
\((2)\)斷開環
\((3)\)縮點

題目

P2607 [ZJOI2008] 騎士
簡要思路：基環樹上 \(dp\), 容易發現，我們可以找到環上的一個點，分兩種情況：\(u\) 不選和 \(fa_u\) 不選，分別 \(dp\) 即可
P4381 [IOI 2008] Island
簡要思路：求基環樹直徑，詳見題解
P1399 [NOI2013] 快餐店
簡要思路：答案應當為刪掉環上一條邊后的最小直徑除以二，詳見題解

生成樹

最小生成樹 (MST)

常見用法

OI-Wiki 最小生成樹

補充

寫代碼時注意區分 \(n,m\)

題目

P1991 無線通訊網
簡要思路：二分答案，\(MST\) 判斷即可
P4047 [JSOI2010] 部落劃分
簡要思路：二分答案，用長度 \(\le x\) 的邊建新圖，跑 \(MST\)，最后判斷連通塊數量即可。更為優秀做法看題解
P1967 [NOIP 2013 提高組] 貨車運輸
簡要思路：容易發現可以建瓶頸生成樹，將圖化為樹，樹上倍增或樹剖都可以
P4951 [USACO01OPEN] Earthquake
簡要思路：\(0/1\) 分數規劃 \(+ MST\)

dfs 生成樹

補充

\(dfs\) 生成樹性質：
1.如果是無向圖，只有樹邊，返祖邊
2.如果是有向圖，有樹邊，返祖邊，橫叉邊，前向邊

題目

P11954 「ZHQOI R1」刪邊
簡要思路：構造題，在圖上比較難做，可以考慮 \(dfs\) 生成樹，則可以刪去所有返祖邊，形成一棵樹，再刪去樹上的一條邊即可，注意細節（菊花圖要特殊考慮），具體看題解

第四板塊——數據結構

線段樹

線段樹基礎

常見用法

OI-Wiki 線段樹基礎

題目

P4588 [TJOI2018] 數學計算
簡要思路：由于不保證模數是質數，所以用逆元做不行，此時我們可以發現兩個操作都可以轉換為單點修改，記錄第 \(i\) 次詢問乘的樹，按題意單點修改，查詢就輸出 \(tr[1]\)，即可
ABC397 F - Variety Split Hard
思路：
考慮先把數列分成兩份，枚舉分的位置，對于后半部分直接計算貢獻，對于前半部分需要再切分一次，嘗試在 \(O(log \times n)\) 的時間內計算貢獻。
容易發現可以預處理出 \(fcnt_i\) 表示 \(1\) 到 \(i\) 中切分一次的貢獻，注意到，從 \(i-1\) 轉移到 \(i\) 的過程中，相當于增加一個斷點，所以可以維護一個數列 \(B_i\) 表示斷在第 \(i\) 個位置的貢獻，需要區間修改和查詢最值。
具體地說，記 \(lst_x\) 表示 \(x\) 這個數上一次出現的位置，則從 \(i-1\) 轉移到 \(i\) 的過程中，從 \(lst_{A_i}\) 到 \(i-1\) 的位置要加上 \(1\)，同時還要新增一個斷點，記錄它的貢獻，具體實現見代碼
ABC407 F - Sums of Sliding Window Maximum
思路：見我的題解
P4513 小白逛公園
簡要思路：具體看題解

線段樹合并

常見用法

OI-Wiki 線段樹合并

補充

注意線段樹合并遞歸到某個節點時，如果 \(A\) 樹或者 \(B\) 樹上的對應節點為空，便直接返回另一個樹上對應節點。如果下一次再次合并的話，就有可能修改這個節點的值，而這個節點可能本來是另一棵已經更新完的線段樹。
則線段樹合并時可能會修改別的已更新完線段樹的值，所以我們需要在更新完第 \(i\) 線段樹時及時記錄 \(i\) 的答案

題目

P4556 [Vani有約會] 雨天的尾巴 /【模板】線段樹合并
簡要思路：樹上差分轉化為單點修改，直接更新線段樹，最后 \(dfs\) 合并即可

P3605 [USACO17JAN] Promotion Counting P
簡要思路：本題有非常多做法：

樹狀數組。我們可以 \(dfs\) 記錄答案，這里有個比較套路的方法：我們可以用全局權值樹狀數組維護，觀察到，\(dfs\) 到 \(u\) 時，前面可能有一些點的貢獻會被計算，記為 \(s\)，則我們可以先 \(dfs\) 完子樹，再查詢，貢獻就為 \(s+ans_u\)，所以我們便可這樣計算出答案
主席樹。查詢子樹可以通過 \(dfs\) 序轉化為區間查詢，然后就變成主席樹板子
線段樹合并。由于只有 \(n\) 個點，所以可以動態開點線段樹，每次向上合并再查詢

掃描線

常見用法

OI-Wiki 掃描線

題目

P5490 【模板】掃描線 & 矩形面積并
簡要思路：板子題
P1856 [IOI 1998 ] [USACO5.5] 矩形周長Picture
簡要思路：跟矩陣面積并有些像，按 \(x\) 和 \(y\) 分別掃描一次，掃描時橫線的貢獻等于 \(abs\) (當前總區間覆蓋長度 - 上一次總區間覆蓋長度)，因為每添加一條邊，如果沒有使總區間覆蓋長度發生變化，說明這條邊在矩形內部，被包含了，不用計算；如果引起總區間長度發生變化，說明這條邊不被包含，應該計算。此外，如果兩條掃描線的 \(y\) 相等，那么需要先計算入邊，原因顯然

第六板塊——動態規劃

動態規劃基礎

常見用法

OI-Wiki 動態規劃基礎

線性DP

題目

P12406 「CZOI-R3」消除序列
思路：
首先發現，交換次數可以歸納為奇數和偶數兩種情況，于是定義 \(f_{i,0/1}\) 表示消到 \(B\) 的第 \(i\) 個數時，\(x,y\) 的交換次數為偶數或奇數的答案
第 \(i\) 次循環時，記 \(w_0\) 表示交換次數為偶數的最小代價，\(w_1\) 表示交換次數為奇數的最小代價，則有轉移方程：

\[f_{i,0} = \min(f_{i-1,0}+w_0,f_{i-1,1}+w_1+z) \]

\[f_{i,1} = \min(f_{i-1,1}+w_1,f_{i-1,0}+w_0+z) \]

現在瓶頸在于計算 \(w_0\) 和 \(w_1\)

首先，我們可以計算 \(A_i\) 在第 \(i-1\) 次操作的位置，記為 \(lpos\)，然后我們就需要把 \(A_i\) 從 \(lpos\) 移到 \(1\)，但這中間可能有數為 \(0\) 導致有部分貢獻無需計算，容易發現可以樹狀數組維護，這里可以用化環為鏈的方法，但還是需要注意一些邊界情況

樹形DP

常見用法

OI-Wiki 樹形 DP

補充

樹形 DP 的狀態多樣，先考慮經典狀態，實在做不了再考慮其他狀態，轉移方程需仔細推敲

題目

P12734 理解
思路：本題我們可以先定義一個直接出答案的狀態：\(f_{u,i}\) 表示以 \(u\) 為根的子樹內記憶容量為 \(i\) 的最少時間，特別地，\(f_{u,0}\) 表是以 \(u\) 為根的子樹內，不選 \(u\) 的最少時間。則答案應為 \(f_{0,0}\)，所以 \(f_u\) 應該不記錄 \(u\) 的貢獻。
對于狀態轉移，首先有：

\[f_{u,1} = \sum_{v \in son(u)} \min(f_{v,0},f_{v,k}+r_v) \]

\[f_{u,0} = \begin{cases} \infty & u \in x \\ f_{u,1} & u \notin x \\ \end{cases}\]

考慮 \(i \in [2,k]\)，有三種轉移情形：

\(v\) 不選，此時用于轉移的是 \(f_{v,0}\)
\(v\) 作為根，此時用于轉移的是 \(f_{v,k}+r_v\)
\(v\) 作為 \(u\) 的兒子，此時用于轉移的是 \(f_{v,i-1}+t_u\)

但是，我們發現，對于 \(u\) 子樹和 \(i\) 的記憶容量，\(u\) 的兒子中可以有最多一個記憶容量為 \(k\)，其余都為 \(k-1\)。
這時，我們可以按以下方式處理，就是先算出和再減去 \(v\) 的原貢獻加上新貢獻

F(i,2,k){
		ll s = 0;
		for (auto v:go[u]){
			s += min(dp[v][0],min(dp[v][k]+ar[v],dp[v][i-1]+br[v]));
		}
		dp[u][i] = s;
		for (auto v:go[u]){
			dp[u][i] = min(dp[u][i],s-min(dp[v][0],min(dp[v][k]+ar[v],dp[v][i-1]+br[v]))+min(dp[v][0],min(dp[v][k]+ar[v],dp[v][i]+br[v])));
		}
	}

最后注意一下多測清空

第十板塊——常見技巧

離線處理

簡述：把詢問離線排序，按一定順序處理

題目

P10814 【模板】離線二維數點
簡要思路：對詢問按 \(k\) 值排序，然后遍歷詢問，可以直接 \(1～n\) 加 \(\le que[i].k\) 的點，現在就是要維護 \([l,r]\) 中存在多少個元素 \(\le x\)，權值樹狀數組可以做到，故時間復雜度 \(O(n\times \log n)\)。

posted @ 2025-07-19 09:18 huangyuze 閱讀(36) 評論(0) 收藏舉報

刷新頁面返回頂部