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