時空

時間復雜度的計算一定要注意有沒有什么 \(\sum\) 的限制，有沒有隱含的條件（如自然根號）。

空間不夠用的情況下可以考慮分批處理獨立的部分。常見于各種奇怪 ds 題。

DP

狀態值域互換是很常見的技巧。

某些題目中轉移可能是比較奇怪的偏序集，扯清轉移順序很重要。JOI2012 kangaroo，UR#13 Ernd。

費 用 提 前 計 算。

背包 dp

大多數背包 dp 是 \((\min/\max,+)\) 狀物，統計方案的是 \((\times,+)\) 狀物。

插入一個元素相當于和二項式做卷積 \(O(m)\)，合并相當于卷積。\((\times,+)\) 存在逆運算，可以支持刪除。注意查兩個背包合并后的單點是 \(O(m)\) 的。

\((\min/\max,+)\) 背包實際上是維護半群運算，所以會有雙棧維護隊列（JZOJ6358 小ω的仙人掌）、DSU on tree（即流傳的 dfs 序優化）優化樹上背包、點分治做路徑背包（旅行）、掛到貓樹上等技巧。

概率期望 dp

如果帶環轉移不取模，在時限足夠的情況下可以多次迭代，期望如果存在一定是收斂的。

期望線性性質，獨立的可以拆開算，(BZOJ4318 OSU!，ARC165E Random Isolation，CF1864H Asterism Stream)。

帶環轉移的若干處理方法。

dp 優化

斜率優化具體情況具體分析，抓住 \(x,y,k\) 的單調性。

wqs 不只是求單點。如果求一個凸包上多點最值，可以先找到整個凸包最值，向左向右找到第一個在給定集合內的橫坐標求兩次單點即可（CF2125F Timofey and Docker）。

決策單調性分治可以在外面套 CDQ 實現半在線。另外看到了個單 log 做法。

不好優化（如沒有決策單調、沒有凸性等常見性質）的半在線可以先 CDQ 變成離線。

通過重定義矩陣乘法可以用矩陣快速冪優化每輪轉移一樣的 dp（CF461E Appleman and a Game）。

連續段 dp

轉移順序很重要。常見于排列計數、類似排列的偏序集計數。

在欽定轉移順序后，可以將狀態簡化為若干形態類似的段，能快速求出新建一段、合并兩段、接在一段開頭或末尾的貢獻。在插入難做時可以考慮。

例題引用。

數據結構

信息維護

注意到 \(\gcd\) 做差分，異或做異或差分等不會對答案有整體影響。

并查集

可撤銷并查集最好寫按秩合并，啟發式合并可能會有奇妙問題（[PA 2017] 商旅 / Osady i warownie）。

可撤銷帶權并查集由于不能路徑壓縮，每次查詢一個點的權值要老老實實算一遍（ CF2104G Modulo 3）。

計數

常用方法：通過構造單射，欽定一個好做的計數結構。

兩個方向的類似限制可以容斥成一個方向。

圖計數

劃分階段是底層邏輯。

有標號 DAG 計數考慮容斥，欽定入/出度為 \(0\) 的部分。[省選聯考 2024] 重塑時光，[清華集訓 2014] 主旋律。

集合冪級數 \(\exp\) 的組合意義：劃分為若干個非空集合的帶權方案數。逆運算 \(\ln\)，如連通性生成子圖計數。

最小生成樹：省選聯考 2025 歲月，JSOI2008 最小生成樹計數。

形式冪級數

OGF 組合意義：\(\sum\limits_{i=0}^{\infty}F^i=\dfrac{1}{1-F}\)。

EGF 組合意義：\(\sum\limits_{i=0}^{\infty}\dfrac{F^i}{i!}=e^F\)。

排列計數

一些問題中，某些變量在對當前狀態無影響但是對后面狀態有影響時可以延遲欽定。

對排列的劃分計數，常用單射欽定技巧確定計數結構。

字符串

SA 生來注重刻畫字典序關系。

能用 Trie 不要用 ACAM，能用 SA/KMP/EXKMP 不要用 SAM。

貪心、構造、Ad-hoc

不知道怎么形容這個東西，某些可行性問題可以拆成判斷所有子問題的可行性。PKUSC2022 擼貓，某模擬賽 T4。Hall 定理。

雜項

偏序集內部最小鏈劃分數等于最長反鏈大小，最長鏈大小等于最小反鏈劃分數。

區間圖是弦圖，弦圖的最小染色數等于最大團。

求 \(\dfrac{a}{b}\) 對 \(p\) 取模時，如果 \(b\) 不存在逆元但是比較小，可以求 \(a\) 對 \(p\times b\) 取模的結果，最后再除以 \(b\) 規避模數域下的除法。

隨機賦值+和哈希/異或哈希有奇效（[PA 2017] 商旅 / Osady i warownie，[CSP-S 2022] 星戰）。

某些 \(\max/\min\) 還有絕對值該拆就拆。\(\max\{|x-y|\}\) 狀物是假的，絕對值可以直接扔掉，但是 \(\min\{|x-y|\}\) 不行。

注意可能的自然根號 / log。