最小路徑覆蓋
- 路徑數(shù)（點(diǎn)不重復(fù)）= 有向圖中的總邊數(shù) - 二分圖最大匹配數(shù)
- 將有向圖變成了一個(gè)二分圖
- 匈牙利算法計(jì)算最大匹配數(shù)
參考: 最小路徑覆蓋問(wèn)題（網(wǎng)絡(luò)流24題）、二分圖的最大匹配、完美匹配和匈牙利算法
最大公約數(shù)
- 輾轉(zhuǎn)相除法求最大公約數(shù)
m對(duì)n求余為a, 若a不等于0,則 m = n, n = a, 繼續(xù)求余,否則 n 為最大公約數(shù)(m > n)。
序列統(tǒng)計(jì)
- m = R - L + 1
- 問(wèn)題等價(jià)于，從 [1, m]中選擇n個(gè)數(shù)(可重復(fù))的方案數(shù)。
- 數(shù)學(xué)推導(dǎo)等于C(m + n, m) - 1
- 使用Lucas定理計(jì)算
參考：「BZOJ 4403」序列統(tǒng)計(jì) - 組合數(shù)
帳篷分配問(wèn)題
- Ai表示第i個(gè)帳篷的人數(shù)，ave表示平均每個(gè)帳篷人數(shù)。Ci=Ai-ave。
- |X1| + |X1-C1| + |X1-C2| + ……+ |X1-Cn-1|要盡量小
- 注意到|X1-Ci|的幾何意義是數(shù)軸上的點(diǎn)X1到Ci的距離，所以問(wèn)題變成了：給定數(shù)軸上的n個(gè)點(diǎn)，找出一個(gè)到他們的距離之和盡量小的點(diǎn)，而這個(gè)點(diǎn)就是這些數(shù)中的中位數(shù)
參考: AcWing 122. 糖果傳遞
