線段樹分治

將插入和刪除操作轉化成插入和末端刪除，從而使刪除變為撤銷。

最小生成樹

性質：

1.邊權為 \(w\)

2.邊權 \(\le w\)

最短路

\(dij\) 去掉堆優化後時間複雜度為 \(O(n^2+m)\) ，在完全圖下可以少帶一個 \(log\)

博弈

可以先寫一個暴力，然後加一些不是很能證明的剪枝或是特性，如果能過對拍，就是對的了（jly説的）。

並查集

離線區間可並信息查詢

如區間 \(min\) ，掃描線，並查集上記錄每個點到父親的權值，路徑壓縮的時候 \(merge\)

凸性優化

凸性證明往往用歸納法。

哈希表

常見的哈希表可以用鏈表實現，對於某個 \(id\) ，用鏈表記錄所有哈希值等於當前 \(id\)

此外，還可以在同一個列表上跳，本質上就是將鏈表全拉平，代碼會好些一些。

struct hash_map{
	ull key[M];
	int val[M];
	int &operator[](const ull n){
		int id=n%M,cnt=1;
		while(key[id]&&key[id]!=n){
			id=(id+cnt*cnt)%M;
			cnt++;
		}
		key[id]=n;
		return val[id];
	}
};

揹包

完全揹包同餘最短路做法

[國家集訓隊] 墨墨的等式

本質是存在一個 \(a_1\) 可以選任意個，那麼對於某個已經可達的 \(B\) ，有 \(B+a_1k\) 均可達。建立最短路模型， \(dis_i\) 表示對於 \(j=i+a_1k\) 中可達的最小 \(j\)。

刪除元素

對於不存在最優性（取 \(max,min\) ）的揹包，可以用 \(O(V)\)