大概寫完了。

如果覺得這篇博客寫得好的話不妨點一個推薦（我怎么淪落到求贊的地步了

0.更新日志

我盡量在本篇博客總結我遇到的所有思維技巧，希望深入理解之后能形成思維網絡。

本篇博客的選題很多都是 \(\tt CF\ 3000+\) 的題，具有很高的思維難度而非代碼難度。

\(2021/8/10\)，把 \(dp\) 開了個頭。

\(2021/9/30\)，繼續更新 \(dp\) 部分。

\(2021/10/8\)，繼續更新 \(dp\) 部分。

\(2021/10/14\)，繼續更新 \(dp\) 部分。

\(2021/10/29\)，感覺復習慢一點也沒關系，一定要盡量自己推出來，懂得完整的邏輯鏈條然后從中提取我所缺失的精華，這才是復習的目的，繼續更新 \(dp\) 部分。

\(2021/11/8\)，終于開始復習圖論啦，現在看來退役之前肯定更不完了，把這個技巧性強的復習完就滿足了吧 \(qwq\)

\(2021/11/15\)，每次找判定性條件，一定要找必要條件，我已經因為沒有往這方面想受到重創了。

\(2021/11/19\)，真他嗎退役之前更不完了，\(zxy\) 啊 \(zxy\) 之前暑假定下的不斷更目標你忘了嗎？

\(2021/12/21\)，退役一個月之后回歸，以后養成好習慣，新寫一道題的題解之后就放上來。

\(2022/2/9\)，怎么馬上就要省選了啊，省選之前爭取基本完工吧，這東西真的就是我的遺產了。

\(2022/3/30\)，開始涉足一些以前沒有整理過的板塊。

\(2022/4/10\)，字數上萬了，這篇博客稱為 \(\rm 3A\) 大作不過分吧？

\(2022/7/19\)，正式開始 \(\tt NOI\) 之前為期一個月的復習計劃。

\(2022/7/27\)，穩步進行復習中，大概在 \(8/6\) 結束第一階段的復習，在 \(8/10\) 結束第二階段的復習（整理貪心\(\&\)數據結構）。然后重讀這篇博客，找出遺忘的地方再次復習，多推一推思路總是好的。

1 dp

1.1 常規dp的思維過程

1.1.1 問題轉化

• 比如你要讓所有點被覆蓋，那么狀態可以設計成覆蓋一段前綴，并且中間不允許出現斷點：CF1476F
• 序列上的路徑問題，可以轉化成起點和終點的匹配問題，\(dp\) 匹配的權值，記錄匹配的標記就可做：The Karting
• 多過程的題，不妨考慮末狀態具有什么性質，直接對末狀態進行計算。比如一類期望題中，某一種方案的定義方式最后導出等概率出現，就可以直接對此方案計數了：綠寶石之島
• 高維的問題，可以通過技巧拆分成不相關的低維問題，比如 \(45\) 度旋轉：Jumping sequence
• 盡可能的簡化問題也是問題轉化的一部分，比如把具有平行關系的點縮在一起：Black, White and Grey Tree
• 計數問題中任何性限制原則上優于存在性限制，可以通過切換限制主體來完成轉化：Reunion
• 子序列問題可以通過證明不交轉化成區間問題，要向簡單的 \(dp\) 模型靠攏：AmShZ Wins a Bet

1.1.2 發掘性質

理清思路真的很重要，拿到題你可以先想想什么東西在什么情況下合法。

• 什么時候需要你去發掘性質？當你發現直接 \(dp\) 需要考慮的情況太多了，你可以手玩找一些最優解需要滿足的必要條件，才能讓你的 \(dp\) 有的放矢，例題：CF1368H1、Division into Two
• 性質是針對限制而來的，在限制較少的題目中可以去往考慮更少情況的方向猜性質：CF573D
• 在具有強烈過程性的題目可以往結果的方向猜性質：To Make 1、模擬賽2-A、Eternal Average
• 很多時候討論特殊情況可以得到很好的性質：泳池（討論 \(0\) 的情況可以得到調和級數的性質）
• 如果限制的主體數量級巨大（比如集合、子序列），那么可以考慮歸納、遞歸的方法描述限制。并且使用這種方法還有一種好處，就是遞歸子問題很容易拓展到 \(dp\) 的形式：Density of subarrays

1.1.3 思考決策狀態

• 可以先使用枚舉法幫助思考我們需要決策的狀態，然后用 \(dp\) 加速枚舉的過程：Sorting Books；Insertion Sort
• 計數題可以想一想需要知道什么量可以用計數原理快速算方案，然后我們用 \(dp\) 決策這些量即可：一拳超人
• 可以選取一種基狀態，其他狀態可以由基狀態修改而來，這時候盡量把問題改成多個量選\(/\)不選的問題，也盡量把他們的影響獨立開來，然后用 \(dp\) 決策這個過程：New Year and Binary Tree Paths
• 如果是決策的最終狀態，且有多種方式可以到達同一種最終狀態，那么強制只用其中一種方式：Mr. Kitayuta's Gift

1.1.4 選定dp主體

我們知道，\(dp\) 的本質是枚舉所有狀態，但是這些狀態必然有一個載體，所以我對 \(dp\) 主體的理解是他只是一種狀態的表示方法，我們用它來描述狀態，但是狀態是最重要的。

很多時候你會遇到很多奇怪的 \(dp\) 主體，但判斷它們的唯一原則就是是否能考慮所有狀態，選 \(dp\) 主體的時候容易被思維定式局限，所以思考可以從哪些方面來描述狀態是重要的，這里有一些關于選定 \(dp\) 主體的例子：

• CF1474F：選 \(x\) 軸為 \(dp\) 主體是不容易的，但是因為我們通常是按順序考慮子序列所以很容易陷入這個誤區，選 \(y\) 軸為 \(dp\) 主體問題就迎刃而解了，所以對偏序關系更高級的理解是若干個限制，不同的題需要從不同的限制入手。
• 卡農：并不一定以小處為主體，比如這題主體為數不好做，但是主體為集合就可以直接轉移了。
• CF1463F：遇到集合最優化問題時，可以考慮在值域上規劃，選值域為 \(dp\) 主體。

1.1.5 設計dp狀態

• 只保留和代價計算有關的量，比如如果代價只和數量有關，并且如果可以通過數量還原出集合，我們可以把狀壓的一維改成線性的：CF1188D
• 當狀態很大的時候可以考慮通過枚舉來把某些量拿出狀態里面：Game with Cards
• 當問題前后相互影響時，可以考慮把全局變量定義到局部狀態里面：密室逃脫；如果操作是全局的，上面的方法也很好用：Red and Black Tree
• 把和限制緊密貼合的量設計到狀態里面，陰間出題人可能會用題目描述來引導你設計非常慢的 \(dp\) 狀態，做一些基本的題意轉化即可：皮配
• 可以設計相反的狀態，比如最小花費步數轉化為最大減少步數，可能轉化后更貼合題設：Paint

1.1.6 確定dp順序

聽著，所謂 \(dp\)，最重要的是順序。無論是考慮限制的順序，還是計算貢獻的順序，一定要著重思考，我覺得它和結論題中的必要條件有著相同的地位。

• 治療計劃：如果操作是有時間順序的話，我們很容易被局限于時間中，另一種思路是考慮操作的主體，考慮主體的關系時把時間的影響考慮進去，所以 \(dp\) 不一定按時間。
• 一拳超人：如果一個東西對另一個東西有單向的影響，那么先處理前面那個有助于考慮影響。
• Kyoya and Train：圖問題中，要注意轉移順序，通常這一維時單調的就可以作為順序維，比如時間。
• 集合選數：\(dp\) 順序盡量讓限制緊湊一些，我們也許可以在獨立的前提下篡改順序。
• Singer House、環：注意 \(dp\) 的順序和方案的順序是有區別的。比如對于路徑計數問題，如果我們按照序列從左到右 \(/\) 樹形自底向上的 \(dp\) 順序計數，那么達到的效果就是若干條有向鏈合并的過程。
• MEX counting、遺跡：可能需要根據限制的特性，提前\(/\)延遲確定一些元素的過程。
• The Hanged Man：選取合適的 \(dp\) 順序，可以減少 \(dp\) 狀態。

1.1.7 尋找子問題

• 這部分我覺得可以總結一些核心的思想：尋找子問題最重要的是找狀態之間的相似性，所謂相似性的含義就是信息記錄在子問題中的一部分的占比，相似性越大你寫轉移就越容易，這需要你強大的觀察能力：stars；要去構造問題之間的相似性，比如染色問題中可以通過欽定不變色來獲得相似性：Shrinking Tree
• 尋找子問題要考慮消除后面操作的影響，這樣才能保證沒有后效性：如果某個元素對于前面的影響是長遠的，但又只能考慮一小步轉移，那么尋找當前問題的等效子問題，就可以把這個影響傳遞下去，完成轉移：stars；或者可以通過枚舉法來消除所謂影響：Lanterns
• 當考慮一小步不能很好的歸納到子問題時，可以定義一個輔助數組來解決這個中介狀態：矩陣、統計問題中若當前不能計算代價，可以設計輔助數組把代價存下來：消失的運算符
• 枚舉法制造限制來劃分子問題，比如順序匹配問題中可以枚舉空位：CF1439D

1.1.8 考慮如何轉移

• 轉移的大步小步。小步適于考慮轉移，但是可能會消耗更多時間；大步常常會很復雜，但是可能起到加速的效果。在大步小步之間切換，才能寫出合適的轉移：Appleman and a Game

• 轉移中存在的限制很煩，在一些計數問題中，對于多個元素的限制可以考慮某些元素任意選，另一些元素為了滿足限制而具有確定的選法，計數 \(dp\) 中選擇的順序是十分重要的：卡農

• 如果確定轉移順序之后前后會相互影響，那么在后影響前的時候可以通過枚舉來解決這個影響，再歸納到子問題：CF1476F

• 多個對象的決策問題中，通常只考慮最后一個對象的決策：CF1439D

• 正難則反是很重要的技巧，比如在計算第一次到達的方案數的題目中，容斥掉的項就是子問題：逃跑

• 轉移的時候適當的算錯，可能會讓轉移簡潔很多：常見的模型是算錯但是一定不會作為轉移點 link；還有是算少但是最優解可以被統計到：Gerald and Path

• 復合 \(dp\)，設計多個 \(dp\) 狀態，互相轉移的方法是很值得思考的。其實我感覺它的原理還是分步思想，把一個較為復雜的問題拆分成若干個部分解決，這些部分中可能又蘊含子問題：模擬賽6-A；或者是多個 \(dp\)，一個 \(dp\) 用于拆分，一個 \(dp\) 用于解決被弱化過的問題，通常可以得到很好的性質：CF1439D、泳池

• 可以把限制的判斷拆分到轉移中進行：泳池、遺跡

1.2 常見dp優化方式

1.2.1 斜率優化

• 有些題很難看出需要用斜率優化，把和狀態有關的量當成常數，把只和轉移點有關的量當成縱坐標，把交叉項系數當成橫坐標，把轉移點的某個量當成直線去切即可：CF1067D
• 另一類不常見的斜率優化是，變形出斜率的形式，維護凸包：國王飲水記

1.2.2 決策單調性

定義：對于 \(a<b<c<d\)，若 \(f(c)\) 從 \(b\) 轉移比 \(a\) 優，那么 \(f(d)\) 從 \(b\) 轉移也比 \(a\) 優。

判斷式：\(w(j,i+1)+w(j+1,i)\geq w(j,i)+w(j+1,i+1)\)

通用實現：把決策點拿去分治，每次更新中間位置的狀態，然后把決策點劃分到兩邊。

• 一些最值問題可以套用決策單調性模型：課桌、Evacuation

1.2.3 考慮有效轉移/狀態

• 只去計算和答案有關的狀態（也就是減少狀態的數量），當前前提是轉移不出問題：Rescue Niwen!；如果答案是和式，那么可以把狀態也定義成和式：Student's Camp
• 在某一種特殊情況下一種轉移的方式會變少，可能達到復雜度級別的優化。序列上可以考慮區間交\(/\)不交情況下的有效轉移：Communism
• 兩種轉移的時候選一種為主體，另一種在它的基礎上對答案有影響的時候就是有效轉移；并且如果一種狀態明顯超過了需要考慮的范圍（就算在價值上它是更優的），你也不需要去考慮它：CF771E
• 從某個點轉移一定比另一個點轉移要優，看起來很樸素的結論卻能在很多時候有奇效。它可以讓轉移點的數量大大減少：Bank Security Unification；也可以忽略到一些惡心的限制（不合法的點一定不優）：模擬賽4-A；也可以利用貪心大致篩選一些有效轉移：Professional layer

1.2.4 討論法

• 整個問題重要的量可能很多，都需要用狀態表示出來，但某些情況下有用的量可能會減少，這時候可以分類討論，互相轉移：Favorite Game
• 當 \(dp\) 的取值很少且是分層轉移的，可以討論并用數據結構維護狀態：Split
• 圖論問題可以討論掉一些較小的環來降低復雜度：Abandoning Roads
• 討論法很適合處理環形 \(dp\) 問題。環形 \(dp\) 的關鍵是：斷開哪一條環邊（我們想要環邊具有怎樣的特殊性質）；斷開環邊局部的狀態是怎樣的（簡單討論可以解決）：Sonya Partymaker

1.2.5 等價類

• 在很多圖論問題中狀壓環的時候，如果轉移只和環的大小有關，那么可以把相同大小的環看成一個等價類：CF1466H
• 只和數量有關而和順序無關可以按照數量劃分等價類：Mr. Kitayuta's Gift
• 乘積不超過某個數的題目可以考慮通過逆向整除分塊來劃分等價類：Ridiculous Netizens
• 轉移方式相同而且易于計算總方案數，可以把它們劃分為等價類：逃跑

1.2.6 數據結構優化

• 對于數列覆蓋問題，常有的結論是兩個點的覆蓋范圍要么包含、要么相離，這時候可以選擇用單調數據結構維護（因為覆蓋范圍單調），而不是帶 \(\tt log\) 的數據結構：CF1131G
• 發現題目有不可解決的維度時，要敢于使用數據結構。但是此時空間消耗特別重要，注意處理 \(dp\) 的順序，才能時數據結構的使用簡單化，并且減少常數的消耗：購票

1.2.7 解決巨大數據范圍

• 離散化是解決較大數據范圍的一種方式，如果某一段內轉移相同，可以離散化出段然后矩陣加速：CF1474F；或者記錄離散化段內的信息轉移：劃艇；離散化還可以把連續型問題轉化為離散型問題：Random Ranking
• 可以找循環節，只要不同的循環節之間沒有多的限制就行，然后每個循環內部都取最優解。證明的關鍵在于沒有構成完整循環的那部分，可以考慮調整法證明（具體思路見例題）：CF1463F
• 對于最優化的 \(dp\) 問題，可以去找轉移點的結論，知道每個轉移點轉移多少次就可以矩陣加速了：CF1067D

1.2.8 考慮轉移路徑

• 轉移路徑可以形象化地表示出來，那么可以把簡單的 \(dp\) 轉化成計數問題，比如這里二維簡單 \(dp\) 轉網格圖計數：[JLOI2015]騙我呢
• 考慮 \(dp\) 的組合意義可以建出圖論模型，快速計算時直接枚舉其中的某個量：匹配字符串

1.2.9 費用計算優化

• 如果當前狀態不好知道，但你清楚代價的變化規則時，可以費用提前計算：Candles
• 如果代價是全局的，那么可以費用延后計算（但一定要注意有無后效性啊??）：Red and Black Tree

1.2.10 分治優化

• 背包問題中如果只有一種元素會特殊，那么可以用分治優化，每次保留本層最優解傳遞上去即可，復雜度會優化的原因是分治會通過在部分中競爭保留最優解：籃球；
• 只要是對于一段區間只有加入就可以嘗試線段樹分治，不一定要是序列上的區間，可以是先建立樹形結構之后，對于一段 \(\tt dfn\) 區間的修改：序列
• 如果只有一個位置不加入，也可以直接分治優化：Random Ranking

1.2.11 神奇優化

• 當轉移代價無法優化時，可以考慮轉移點數量的限制，然后快速找到轉移點：緋色IOI
• 不支持取 \(\max\) 操作時，可以通過考慮轉移點的性質來轉貪心，通常是權值單向影響的題目：CF878E
• 如果 \(dp\) 值單調，并且需要支持合并和取最值，那么可以用 \(\tt set\) 維護差分標記：魔法樹
• 如果 \(dp\) 代價為正并且只存在于單點上，那么可以考慮成類最短路，每次拿到最小的那個能擴展就擴展，用數據結構維護最容易被擴展的點即可（通常是線段樹維護最值）：治療計劃
• 整體 \(dp\)，如果多個 \(dp\) 轉移方式完全相同，那么可以考慮一次 \(dp\) 求出答案，比如序列上可以通過端點初始化和端點統計完成：Extreme Extension、Foreigner、星圖；更加靈活的形式是找問題之間的關系：Palindromic Hamiltonian Path；其他例子：Mr. Kitayuta's Gift、山河重整、線段樹

1.3 常見dp模型

1.3.1 樹形dp

• 樹背包真正的復雜度是第一維大小乘上第二維大小，特別是第二維很小的情況：CF1097G
• 建立一些使用于特殊性質的樹形結構，并在結構上規劃：淺談笛卡爾樹結構的應用
• 樹重排規劃問題可以考慮轉區間 \(dp\)，本質上就是枚舉根的過程：Tree Tweaking
• 路徑規劃問題，可以枚舉起點，然后使用換根 \(dp\) 來獲取最優的起點：Svjetlo
• 合并問題可以從葉子開始考慮：Logical Operations on Tree
• 樹上路徑的限制問題，可以只保留最深的\(/\)最淺的記為狀態轉移：命運
• 不支持合并的樹形 \(dp\) 問題可以考慮轉成 \(\tt dfn\) 序上 \(dp\)（樹上依賴背包）：Ridiculous Netizens

1.3.2 狀壓dp

• 圖計數問題，通常是考慮導出子圖，常用的技巧是正難則反：淺談狀壓dp在圖計數問題上的應用
• 如果只需要知道大小關系，狀壓 \(dp\) 也可用于確定序列問題上，需要多消耗 \(O(\)值域\()\) 的復雜度：Random Robots
• 狀壓套折半搜索具有神奇的復雜度 \(O((1+\sqrt 2)^n)\)：Harry The Potter

1.3.3 連續段dp

• 連續段 \(dp\) 可以計算端點產生的貢獻，這是和連續段數正相關的：摩天大樓
• 寫轉移的時候可以用兩段之間任意長這個條件，方案數就便于計算了：Phoenix and Computers

1.3.4 背包

• 如果裝入的總物品不是很多（\(\sqrt n\) 級別）并且連續，可以考慮柱狀圖 \(dp\)，轉移分為增加一個柱子和把所有柱子整體升高：逆序對、山河重整；而且這種 \(dp\) 天然帶有順序，如果你想求前 \(k\) 大的話是特別方便的：綠寶石之島
• 多重背包如果只需要判定存在性，可以維護還剩下的物品數量，轉完全背包：AB tree
• 如果背包支持快速合并（有凸性），那么可以直接用分治優化：妹妹卡組
• 要有一個總體是時間觀，很多巧妙的背包優化只能把 \(n\) 變成 \(\sqrt n\)，如果需要本質復雜度的下降，那么可以嘗試改變維護的東西，降維是常用的技巧：Tree Degree Subset Sum、Jumping sequence，降維的關鍵就是找獨立性之后拆分：皮配
• 有一個物品是特殊的，它的選取方式和其他物品不一樣，特殊考慮它就能讓問題變簡單：Lucky Numbers；少量特殊物品時可以考慮分別計算然后合并背包：皮配
• 很多時候背包會存在（隱藏的）拓撲關系，這時候的結論可能是選了小價值物品就必須選大價值物品：Turtle
• 總容量大，但是物品重量很小的背包，可以按二進制位考慮壓縮有效狀態數：物品
• 前后綴背包，把這個思想搬到樹上就是求出 \(\tt dfn\) 正序背包和 \(\tt dfn\) 倒序背包，然后再合并：蘋果樹

1.3.5 計數dp

計數 \(dp\) 的原則是：初始有一些基礎方案，然后我們逐步添加可以區分出方案的東西（這東西是根據方案不同的定義來的），轉移到不同的地方就代表這一步產生了不同的方案：高維游走

• 組合意義的嵌套的重要的方法，也就是我們給我們的代價函數確定一個組合意義，那么 \(dp\) 就需要同時完成確定局面和組合計數的功能，常用技巧是拆分：Pass to Next、Stranger Trees、Crash 的文明世界
• 巧妙的枚舉可以達到合并兩個子問題方案的目的，比如本題枚舉可以合并組合數：CF1097G
• 如果判斷合法需要使用 \(dp\)，而原問題又是一個計數問題時，可以使用 \(dp\) 套 \(dp\)，其關鍵還是建出 \(\tt DFA\)：模擬賽7-A、游園會

1.3.6 雜項

• \(dp\) 維護直線函數：CF889E
• \(\tt slope\ trick\) 優化 \(dp\)，主要處理代價帶絕對值的規劃題目：折線算法；可以維護很多跟斜率有關的操作，比如含有 \(\tt max\) 的函數：Increment Decrement
• \(dp\) 維護容斥系數，在大小關系中的計數題中十分常見：小D與隨機、不等關系；一些需要考慮集合的毒瘤題中，暴力指數級容斥出奇跡，再轉 \(dp\) 維護即可：獵人殺、百鴿籠

2 圖論

2.1 圖論問題的思維過程

2.1.1 圖論模型的建立

首先考慮對于原問題的什么對象建立模型（主體的選取），然后嘗試用圖論的各種意義去表示原問題中的元素（比如點權、邊權、路徑、連通塊\(...\)），這兩步都不要被定式思維所限制。

以題目中的一個限制為基礎建立模型，這一步不要被思維定式所局限。

• 遇到難以處理的全局限制時可以考慮圖論：Maximum Adjacent Pairs
• 矩形中類似推箱子的問題，可以把箱子的移動轉化成空格的移動，建立關于空格移動路徑的圖：Shifting Dominoes
• 區間元素和的判定問題可以把前綴和建成點，原圖中的元素建成連接前綴和的邊：Flip and Reverse

2.1.2 圖結構的分析

• 樹形結構具有很多優美的性質，可以通過分析度數與環來證明樹形結構：Shifting Dominoes
• \(dfs\) 樹是很重要的思維方式，通常我們分析樹邊和非樹邊能得到很多有意思的性質。如果是有向圖還要考慮哪個點為根更好分析：James and the Chase；或者可以通過 \(\tt dfs\) 樹直接給出構造：Nezzar and Hidden Permutations；Weighting a Tree
• \(\tt DAG\) 具有很好的性質，所以就算是遇到一般圖時，也可以先思考在 \(\tt DAG\) 的環境下如何處理：Sergey's problem

2.1.3 問題轉化

• 度數和連通性常常可以互化，但度數描述單點限制，連通性描述整體限制：電報
• 圖論中拆分思維也很重要，把總貢獻拆分到點上\(/\)邊上：Keys
• 如果不同的限制具有拓撲關系，根據題目特性可能可以忽略一些限制：Falling sand
• 一類東西只貢獻一次的問題可以考慮轉化成匹配問題：Maximum Adjacent Pairs
• 可達性問題可以考慮轉化成連通性問題，此時注意考察連通的雙向性和等價性：Cow and Vacation

2.1.4 尋找結論

• 如果點權集中可以獲得更多貢獻，那么可以思考答案會不會是原圖的最大團：七負我
• 從小處入手思考結論（比如葉子），那么你可能發現原來復雜的問題變簡單了：緋色 IOI（抵達）
• 拓撲覆蓋問題可以考慮在原序列上的區間性質：Falling sand；連通性問題也可能有區間性質：Number of Components
• 通過雙圖策略尋找性質：String Transformation 2、Next or Nextnext
• 生成樹的應用是廣泛的，關注性質 答案一定在滿足某種性質的生成樹上：模擬賽6-B

2.2 常見算法應用

2.2.1 最短路

• \(\tt dijk\) 的遍歷思想在很多題中有大用處，如果每個點只需要遍歷一次那么維護最有可能遍歷的點：Mike and code of a permutation；治療計劃
• 動態加邊可以解決到達時間最小的限制，它的本質是如果具有連通性就可以說明最早到達：Dirty Arkady's Kitchen；動態加邊還可以直接維護強連通性，對正反圖動態 \(\tt bfs\) 即可：圖函數；動態加邊還可以完成版本之間的轉化，結合 \(\tt spfa\) 可以做到某些情況下的動態最短路：道路堵塞
• 用 \(\tt dijk\) 可以保證一些特殊的轉移順序：Intergalaxy Trips
• 環上的最短路，如果數據范圍極大，先考慮重構環之后再掃環：Drazil and His Happy Friends
• 刪點后求最短路的問題有固定套路，就是考慮有一條邊一定會跨過這個點，可以拼湊出路徑來：風之軌跡；道路堵塞

2.2.2 連通性

• 互達問題可以思考連通性，連通性重要的一點是傳遞性，有些問題可能只有特殊點具有連通性：Cow and Vacation
• \(\tt lct\) 可以維護動態邊雙連通分量，考慮把非樹邊的影響轉化成賦值標記即可：Bear and Chemistry
• 無向圖路徑的最值問題，可以將邊權排序之后轉化為維護連通性（最小生成樹只是特例）：路徑查詢
• 對于帶修改的問題來說，可以有一個統一的固定結構來處理兩點連通的時刻（邊起作用的時刻）：Gates to Another World；維護強連通性，可以用整體二分求出每條邊強連通的時間，然后轉化成維護無向圖的連通性：WD與地圖

2.2.3 拓撲排序

• 拓撲排序可以提供一種解構圖的順序，注意拓撲排序中天然帶有的可達性：Pink Floyd；如果需要一些出現順序的關系，可以先建立圖之后考慮其拓撲序：Insider's Information
• 拓撲排序的性質，同在隊列里的點沒有任何到達關系，可以通過它來篩選合法點：Upgrading Cities
• 拓撲排序的另類形式：按 \(1\sim n\) 的順序在反圖上 \(\tt dfs\)，最后回溯的順序就是拓撲序：Mike and code of a permutation

2.2.4 將問題轉化到圖論算法

• 調整法可以幫助建出差分約束限制，矩陣問題可以以行和列為待定變量：矩陣游戲
• 拓撲排序可以解決帶平局的博弈問題，首先全部設置為平局，按照定義對反圖跑拓撲即可：Shiritori
• 差分約束的反向應用，如果要求是不出現負環，那么等價于有差分約束的合法解，那么可以把圖上的邊都寫成不等式：Negative Cycle
• 二分圖染色問題，如果需要優化連邊，得到同色的性質可以縮成一個點，然后套用并查集路徑壓縮的時間復雜度：港口設施

2.3 樹問題

知識點：樹的直徑（鄰域理論）、樹的中心、鏈剖分、虛樹、樹分治、樹合并、樹哈希。

2.3.1 問題轉化

• 無根樹問題定根（比如路徑、刪葉子）是一種重要的思維方法：Squid Game、D、Matches Are Not a Child's Play；考慮重心可以去掉一些關于子樹大小的 \(\min\) 式子：Distance Matching
• 樹上最遠點問題可以轉直徑端點：CF516D、廣義的直徑問題是帶權匹配，是支持點權的：情報中心；最長鏈問題也可能和直徑有聯系：模擬賽7-B；以直徑中點為根建樹可能是不錯的選擇：Drazil and Morning Exercise；以直徑端點建樹也可能有很好的性質：Spiders Evil Plan

2.3.2 樹上算法

• \(\tt lct\) 有著特別重要的染色模型，也就是用實邊代表同色，虛邊代表異色，修改就是把一個點到根的路徑染色，然后用數據結構維護顏色的方法：Matches Are Not a Child's Play、樹點涂色
• 延遲貪心，即能不放置關鍵點則不放置，這樣能把關鍵點放置在最淺的位置：Squid Game
• 要快速計算虛樹的大小時，可以考慮下標為 \(\tt dfn\) 序的線段樹來維護：語言；這種用線段樹去重的方法還可以應用于字符串中（若干后綴的本質不同前綴，\(\tt sam\) 上啟發式合并）：Asterisk Substrings；這類線段樹合并的本質是用線段樹的結構提供了一個合并順序：三角形
• 最大\(/\)最小邊權問題考慮 \(\tt kruskal\) 重構樹。比如想要求虛樹的最大邊權，可以轉化成重構樹上最淺的祖先，即 \(\tt dfn\) 序最大點和最小點的 \(\tt lca\)：Groceries in Meteor Town
• 路徑問題考慮點分治，不要被復雜的形式給詐騙了：Network

2.3.3 常見模型

• 連通塊問題的常用解決方法：可以在連通塊的最淺點統計這個連通塊的貢獻，那么用樹形 \(dp\) 來規劃這個最淺點即可：切樹游戲、Ridiculous Netizens；還可以用 點數-邊數=1 的經典容斥：完美的集合；選取連通塊的代表點時，可以套用點分樹這種分治結構：成都七中、Ridiculous Netizens
• 還原樹的問題中，可以分步還原，也就是先還原特殊點的結構，再還原整體的結構：Restoring Map；New Year and Forgotten Tree
• 邊權和貢獻最大問題可以往長鏈剖分這個角度考慮，如果是路徑問題可以通過 \(2k\) 個葉子的構造性結論轉化成最長鏈問題（前提是需要定根）：Spiders Evil Plan
• 巧妙利用樹上結構，如可以用重鏈剖分的結構來快速定位：Nauuo and Binary Tree；若是多個數通過操作合并為一個數，可以思考操作的樹形結構：Eternal Average；括號序列的樹形結構是重要的：[省選聯考 2022] 序列變換（差點因為這題沒進隊）

2.4 網絡流

有一些入門的內容，不想整理了：網絡流簡單題選做；網絡流二十四題

把下面這些整理完之后，我才發現好像網絡流確實已經很難有新意了，很多 \(\tt trick\) 都是反復出現的。

2.4.1 量的意義

• 用流量的流入和流出代表加減，可以表示一些加減的不等式關系：Red-Blue Graph
• 流量可以在基于要求的情況下，表示解決要求的途徑，而費用可以看成途徑的代價：Chips Challenge
• 可以用路徑來表達不合法的關系，再用最小割來獲取最優解：Starry Night Camping；老C的方塊
• 對于覆蓋類型的限制，把需要覆蓋的點串聯起來，用路徑表示覆蓋的關系：奇怪的線段樹

2.4.2 觀察性質

• 如果用網絡流解決平面圖問題，可以考慮黑白染色轉二分圖的性質：過山車
• 網絡流解決矩陣問題，可以用行列來建二分圖：；但這有時候是個思維定式，如果行和列獨立并且有其他限制，那么建單層圖能更好地表達限制：Asa's Chess Problem
• 完美匹配的等價條件是 \(\tt Hall\) 定理，所以如果原問題和 \(\tt Hall\) 有某種關聯可以通過這層關系轉化到網絡流上：Construction of a tree
• 拆分法，網絡流一般只能解決單點對單點的限制，如果是多點對單點，那么大膽找結論，我們可以從答案的形式入手：Rainbow Triples；還有對代價的拆分，比如絕對值的微元貢獻法：One Billion Shades of Grey
• 如果某個問題可以建出其費用流模型，那么是有凸性的，就引申到了 \(\tt wqs\) 之類的算法：April Fools' Problem

2.4.3 小技巧

• 單點的多重意義，可以考慮拆點，通常可以讓限制表達得更明晰：過山車，Making It Bipartite
• 動態網絡流，如果有多個圖但是差別不大，可以把多出來的邊退流：模擬賽7-C；One Billion Shades of Grey
• 手算最小割，常常需要枚舉法和數據結構維護：Rainbow Triples；也可以對于點所屬的顏色來 \(dp\)：Breadboard Capacity；手算最大流也常用，使用結論然后數據結構維護：k-Maximum Subsequence Sum
• 保留有用的邊，減少邊數：Bridge Club；劃分等價類，減少點數：小埋與游樂場
• 優化建圖，本質和圖論的優化建圖是同一類方法，\(cdq\) 優化建圖：通信；主席樹優化建圖：a+b Problem

2.4.4 圖匹配問題

• 一般圖匹配也許可以通過結論轉化成二分圖匹配（左部右部的匹配次數相同）：模擬賽5-A
• 一些情況下貪心地匹配：Add to Square（達到構造的界）；模擬賽2-C（特殊的偏序關系）
• 二分圖的獨立性（只需要考慮某一部的具體情況）：Bipartite Blanket
• 不能走回頭路的博弈問題可以考察二分圖匹配相關的結論，這是因為交錯路具有特殊的數量關系：游戲
• 經典問題：有向圖求環劃分，可以拆成入點和出點跑二分圖匹配：邊

2.4.5 常見模型

• 混合圖的歐拉回路，思考清楚度數在原問題中對應著什么即可套用此模型：wait
• 最大權閉合子圖，可以解決帶強制選取關系的選\(/\)不選問題，或者也可以解決類似的二選一問題：魔法商店
• 最長反鏈，轉最小鏈覆蓋之后，用 \(\tt dfs\) 的方法構造即可：Birthday；也有構造新的偏序集再跑最長反鏈的題目：Making It Bipartite
• 上下界網絡流，可以表示一些強制限制：Showing Off；帶上下界的網絡流

3.unknown

3.1 計數

3.1.1 問題轉化

• 映射法，遇到多對一的問題時（多種方案生成同構的結果），可以通過添加限制把多化一，構成雙射：Two Histograms；可以根據數感，和常見的結構建立映射關系：神必的集合、Slime and Sequences；遇到信息題時（確定未知變量），考慮我們都知道什么信息，和信息建立映射關系：Bears and Juice
• 組合意義法，如果方案數是加權的，那么思考權值的組合意義，最好化為存粹的方案數：Min Product Sum；教數學的校長；組合意義盡量合并多步計數（即把原來復雜的結果化為一個過程）：盒；對于外層的枚舉可以建立虛點來等效替換：數葉子；逆向應用一些定理也是組合意義的一個方向：無損加密
• 把限制轉化成單側的，這樣計數順序會更明顯：Centroid Probabilities
• 切換計數對象，簡化計數的主體：stairs；去除不易處理的限制：count；添加限制轉化為容易計數的對象：Two Pieces

3.1.2 容斥/反演

• 最常見的容斥方法是枚舉不合法的個數：Two Histograms、神經網絡
• 如果存在選取個數 \(\leq a_i\) 的限制，可以強制選取 \(a_i+1\) 個，然后記上 \(-1\) 的容斥系數：鑰匙
• \(\tt LGV\) 引理，原本求的是偶數逆序對的不交路徑減去奇數逆序對的不交路徑。在特殊的圖中（比如網格圖，數軸）可以直接求不交路徑數量：無損加密，如果終點未知還可以考慮 \(dp\) 計算行列式：Random Robots
• 容斥的另一種思考方向，先給出一種會算重的計數方法，然后找出這種計數方法算重的原因，然后對這個算重的原因容斥：樹；比如經典模型 \(\tt DAG\) 計數，就是容斥入度為 \(0\) 的點：Finding satisfactory solutions；類似的基環樹計數，可以容斥葉子：人類補完計劃
• 集合劃分容斥，用于解決相等關系的限制，直接對邊數容斥即可：Distinct Multiples

3.1.3 統計方法

• 思考答案的形式，然后思考在哪里統計，如果答案是區間則可以在端點處統計：Chords；如果答案是樹上的點集，那么可以在其 \(\tt lca\) 處統計（寫成代碼就是在合并子樹的時候統計）：Vladislav and a Great Legend
• 思考統計的順序，確定合理的順序可以讓式子變得更簡單，通常有偏序關系就意味著可能需要思考順序：Inversions；分步統計，逐步確定的方法也是重要的：鑰匙；為保證順序，還可以在一次計數中結合不同的計數方法：模擬賽3-A；可以先確定一個大致的順序，然后在轉移時修正它：Square Constraints
• 關于去重方法，可以考慮給同構的方案增加限制：Piling Up；比較無腦的去重方法，考慮一種方案會被計算多少次，然后用除法去重：Fox And Travelling；如果要考慮無序的子結構，可以考慮隔板法去重：Shake It!

3.1.4 常見模型

• 卡塔蘭數模型，可以解決在網格圖中行走但是不越過某條直線的方案數：Ball Eat Chameleons
• 斯特林數模型，可以在 \(n\) 大 \(k\) 小的情況下優化計算 \(n^k\)：Vladislav and a Great Legend
• 本質不同字符串計數的問題，直接考慮建立 \(\tt DFA\)：Strange Operation

3.1.5 概率期望

• 注意利用等概率的性質，比如轉等概率環，可以把總體的方案放到單點上去：Wine Thief、也可以方便地計算總方案數：AmShZ Farm
• 如果題目保證了出現的概率，那么這題可能就是基于概率來尋找關鍵點：James and the Chase
• 拆分。獨立變量的概率常常可以拆分，這樣可以分步解決問題：Strongly Connected Tournament；概率對期望的拆分十分重要，可以完成期望對概率的轉化：Shuffles Cards、Gachapon
• 概率期望類型的題目中，一些前綴 \(/\) 差分類型的轉化往往能夠簡化問題：地震后的幻想鄉

3.2 基礎方法

3.2.1 勢能法/均攤法

• 適合勢能法的題目有一些特征，比如覆蓋問題：小Z與函數；染色問題：Intervals of Intervals、億塊田（位運算可以看成數位的顏色段均攤）；區間合并與分裂問題（通常是維護的東西具有單調性，可以把值相同的一段看成區間的題目）：貨幣、Holy Diver
• 使用勢能法時，可以從一些感性的角度，通過定義勢能函數來入手：Souvenirs
• 盡管有時候操作比較復雜，但是若是具有 某變量一定減少 的性質，就可以通過加速一些簡單的過程來優化：Addition and Andition；可以通過一些簡單的操作變換，使得減少量和花費的時間之間對應起來：五彩斑斕的世界
• 勢能線段樹，可以維護區間取 \(\min\)、區間除法等操作：淺談勢能線段樹在特殊區間問題上的應用、Cartesian Tree、Stations
• 均攤法最重要的是分析總體復雜度，所以一些暴力的操作可能看起來很慢但是總體復雜度優秀：Berland Miners

3.2.2 拆分法

使用拆分法時，最重要的是保證獨立性。

• 如果題目中存在時間順序，可以把這個順序破除來保證獨立性（即換一個順序計算）：Addition and Andition
• 可以對左右端點拆分來優化，比如應用到區間 \(dp\) 問題：Student's Camp；可以拆分之后分別計算：Cartesian Tree
• 高維問題可以考慮拆分成獨立的低維問題：Berserk Robot、Jumping sequence
• 拆分法可以用來集中限制，比如把兩個主體間的限制拆開，等效到一個主體上：Drazil and His Happy Friends；拆分法還可以分解限制，可以把區間限制拆開，分解到單點上：模擬賽2-B
• 線段樹可以理解成對二進制數位的拆分，有些題目可能利用線段樹來拆分：Xor-Set

3.2.3 調整法

調整法的使用過程是：選取初始狀態（Sergey's problem）、確定調整方式。

• 有很多匹配問題具有神奇結論，證明可以考慮調整法：Modulo Pairing、Bear and Cavalry
• 如果某問題連判定合法性都困難，還要求你最優化的話，那么大膽使用調整法。從最優狀態開始調整，使用最小代價來達成合法性（這樣可以兩個愿望一次滿足）：Two Faced Cards、Chips Challenge
• 鄧老師調整法，從一個合法狀態開始，然后對它進行微調使得權值變大 \(/\) 變小：鄧老師調整法、Pastoral Oddities
• 可以用調整法來研究最優解滿足的性質，這時候使用一些簡單的不等關系是重要的：遇到困難睡大覺、轉盤、Max Correct Set
• 兩種決策的問題可以考慮主一副二的方法，先固定一個，然后用另一個調整以獲得最優解：Squares
• 連續型問題向離散型問題的轉化，可以通過調整法證明只會取到端點值：Parametric MST、Levko and Game

3.2.4 分治法/倍增法

• 矩形問題可以考慮交替分治，加上點雙指針單調性什么的可以做到優秀復雜度：Empty Rectangles
• 類似后綴數組的倍增技巧，優化的重點是充分利用上一層的信息：Minimal String Xoration、月球列車
• 使用倍增法的重要步驟是結合單次詢問分析，找到關鍵的固定的可加速過程，然后倍增：麻煩的雜貨店、Hopping Around the Array
• 倍增是基于二進制的，所以某些異或問題用倍增有奇效：溫故而知新
• 確定唯一的后繼就可以倍增，可以認為地讓這個后繼滿足一些優良性質：唱詩

3.2.5 神奇復雜度

• 只保留有用的點 \(/\) 點對再暴力計算，可以從一些基本的不等關系入手：Weighted Increasing Subsequences、法陣
• 動態的擴展狀態，只考慮用得到的狀態，在總狀態數特別少的情況下特別有用：A Serious Referee
• bitset，一個開掛般的存在，沒有減少任何計算量，但是卻常常是有效的優化。字符串匹配問題常常可以套用 bitset：Substrings in a String、strings；利用 bitset 來遞推：New Year and the Tricolore Recreation；利用 bitset 加速對應位置異或：區間距離
• 找到某個能讓值域翻倍\(/\)折半的關鍵元素，可以優化暴力的復雜度：大套子、Phoenix and Diamonds
• 四毛子思想。直接對原序列分塊，對于每一塊內處理出所有子集的信息，可以平衡復雜度：strings

3.2.6 根號相關

• 總和一定時，注意種類 \(\sqrt n\) 的結論：Snowy Mountain、Tree Degree Subset Sum
• 值域分治。在位運算和四則運算混合時，預處理時先最大化前一半的數位，再最大化后一半的數位，預處理和詢問平衡做到 \(O(n\sqrt n)\) 之類的復雜度：In a Trap；暴力前一半，狀壓后一半，可以做到 \(O(\sqrt n)\)：進制轉換；值域分塊帶有天然的偏序關系，在偏序關系限制比較嚴格的時候可以嘗試使用：Set Merging
• 根號分治。把種類按照出現次數分類已經是老生常談了，但是注意分治后的情況下具有的性質：眾數、Huffman Coding on Segment；序列跳躍問題可以直接對后繼的距離根號分治：Summer Oenothera Exhibition
• 操作分塊。結構變化且復雜的題目可以考慮每 \(O(\sqrt n)\) 個操作分成一塊，分別處理。注意這樣轉化之后結構會變簡單，可以把一些復雜的操作用暴力來實現：Jumping Through the Array

3.2.7 貢獻法

貢獻法最基礎的用法就是改變和式的計算方式，使用貢獻法時，首先確定貢獻對象，然后思考這個對象在什么情況下會產生多大的貢獻：Move by Prime

• 多種情況下要統一貢獻形式，可能需要欽定合適的貢獻方式：鑰匙（可以貪心匹配上的就貢獻）
• 基于大小關系比較的題目中，可以考慮使用 01-principle，即先考慮 \(01\) 序列的情況，再用貢獻法推廣：線段樹

3.2.8 隨機化

• 擴大值域以減小出錯概率。如果想通過行列式表示積和式的一些性質（比如是否為 \(0\)），那么可以擴大值域，直接計算行列式，出錯的概率是極小的：億些整理
• 在出現頻率差距較大時，隨機抽樣調查若干次可以獲得想要的結果：Olha and Igor

3.2.9 枚舉法

• 適當的枚舉有助于考慮限制，比如點不交的問題中，可以枚舉不交的那個點：Path
• 用枚舉法向簡單問題化歸：Prefix Suffix Addition、制作菜品
• 切換枚舉對象，前提是分析清楚枚舉過程：鴿子固定器

3.2.10 貪心法

• 我們使用貪心時，盡可能要單一化貪心的對象，獨立化貪心的代價。這需要我們觀察代價的特點，使用拆分法對代價進行一些處理：[省選聯考 2022] 序列變換；貪心對象多化一的處理：新年的腮雷

• 統一代價的形式，這樣更便于貪心的使用：Parametric MST；統一操作的形式，也便于貪心：Game Relics、Escape

• 樹上依賴貪心。如果存在先選父親才能選兒子的限制時，弄出合并規則然后用堆維護：三角形、牛半仙的魔塔

• 如果代價具有凸性，那么可以會指向堆貪心之類的做法：WYR-Leveling Ground

3.3 數據結構

這里并不是對數據結構的系統總結，而是總結了一些有意思的思維點，可能對你做數據結構有幫助，但是前提還是有扎實的數據結構基礎，能對任何結構信手拈來。

3.3.1 問題轉化

• 寫出操作的線性變換形式，就可以直接套用矩陣：密碼箱
• 刪除操作，可以看成回退到上一時刻，可以用保留所有歷史版本的主席樹來支持回退：火車管理
• 對一段區間內的分段函數求和，可以對把自變量當成版本，以位置來建立主席樹：Tower Defense
• 對于強制在線的問題，可以先思考離線怎么處理，然后套上可持久化數據結構：區間第k小

3.3.2 考慮限制

• 切換限制的主體。很多時候從題目的方向直接翻譯是行不通的，這時候弄清限制涉及到了哪些對象，然后通過選取其他對象的形式來重新表述限制，就達到了切換限制主體的效果：鈴原露露
• 保留有效限制。限制之間也存在偏序關系，如果通過一些技巧可以達到排除無效限制的效果，那么就可能把限制的總量規約到一個較小的數量集。比如樹上啟發式合并來考慮和 \(\tt lca\) 有關的限制：鈴原露露、事情的相似度
• 放寬限制。并不一定要在滿足限制時檢查，可以找維護一個合適的必要條件，把總檢查次數限制在一定范圍內：被創與地震
• 收緊限制。對于限制較弱的問題，可以通過討論特殊情況，使得要考慮的范圍縮小：Path

3.3.3 確定維護對象

• 盡量不要去維護有關特定值的信息，可以通過放寬條件的方式轉化為維護最值：Bear and Bad Powers of 42、Into Blocks
• 可以通過切換主體的方式來確定維護對象。譬如有 \(A\rightarrow B\) 的影響，從 \(A\) 的角度看是一種效果，從 \(B\) 的角度看又是另一種效果。根據修改與詢問的特性變換角度，可以確定最為合適的維護對象：The Tree；先弄清維護的信息是什么，然后切換主體，保持維護信息的不變即可：前進四、詭異操作
• 切換承載信息的主體，前提是原來的主體和新選取的主體之間可以建立對應關系：Nauuo and ODT；尋找決定性的對象，比如這個對象決定了答案，那么我們就盡力去描述它：區間和

3.3.4 思考如何維護

• 如果難以對維護對象選取主元，那么考慮對稱的維護兩個對象：圖論

• 等效操作的思想是很重要的，當你切換維護對象之后，可以通過等效操作來適應現在所維護的東西：The Tree、數軸變換

• 整體標記法。思考清楚整體標記對于單點的影響即可：Latin Square

• 注意維護信息的順序，比如有的問題只適合以一種順序加入：Julia the snail

3.3.5 常見模型

• 遞歸半邊模型。其本質是離線與在線的結合，利用維護好的信息每次可以將考慮的區間折半。維護括號匹配：Nastya and CBS；維護極長上升子序列類的信息：轉盤
• 染色模型。一些類區間賦值類操作可以向染色模型轉化：輕重邊；區間求并的問題，可以掃描線加染色模型，也就是維護最晚被染的顏色：rrusq、區間本質不同子串個數
• 貓樹分治。主要作用是提供一個分治中點，比如可以把分治中點當成歷史最大值的起點：rprmq1
• 二進制分組。可以支持末尾的在線加入，搬到線段樹上可以支持末尾刪除和區間查詢：Unknown