算法競賽入門經典訓練指南(升級版)（簡體書）

許多計算機相關專業的人，畢業之後除了為應付面試外，基本都很少再去碰算法。而在實際的產品或者項目開發過程中，大多數人也沒有必要親自去實現復雜的算法。因此，算法漸漸淡出程序員的日常生活。同時，在現實生活中有另外一種聲音：程序員的生活太糾結，coding的速度永遠跟不上需求變化的速度，提需求的客戶似乎成了程序員的“天敵”，成了他們“苦逼”生活的罪魁禍首。

那麼，一本講算法比賽的書跟這又有多少關係呢？就從我自身的經歷說起吧。我不是計算機科班出身，但因種種原因進入了這個行業，而且是從一個很低的起點進入的。於是我像所有人一樣，平時很難靜下心來學習算法，有了面試就去臨時抱本書突擊一下。終於有一天我受不了了這種循環，我捫心自問：難道只有為了某個急功近利的目的我才願意去付出自己的時間嗎？佛家有句話叫“凡夫求果，菩薩求因”，我就想，既然成不了聖人，就學一回聖人吧。

因緣際會，我接觸到了“入門經典”及其作者劉汝佳，於是一發不可收，寫這本書的過程也變成了修行與學習的過程。慢慢地，我發現算法對於實際工作的人而言，有著比應付面試更大的價值。所謂的算法、組件、模式，就像是一些基礎的原材料，對於優秀的建筑師來說，需要透徹地理解（不一定寫得很熟練）它們的關鍵性。因為一個錯誤的設計，對於系統來說，所要付出的代價遠比一般的程序bug要高得多。更進一步說，現在做軟件的為什麼苦，為什麼抱怨需求變化快？因為解決問題的思維方式出現了偏差。需求分析絕對不是簡單地拿著需求，直接翻譯成代碼—這是最低層次的實現。算法分析的意義，更多地不在於性能，不在於那些腦筋急轉彎，而在於發現紛繁復雜的問題背後的“不變式”，而這正是本書要著力與大家分享的地方。

2012年，《算法競賽入門經典——訓練指南》第一版出版面市。時光荏苒，轉眼間已過去8年時間。這些年間，競賽界出現了很多新的知識點和題目類型；另外，在人工智能大潮的感召下，更多的學子參與到了算法競賽中。為了能夠為這些新增的知識點提供一些例題講解以及習題練習，大概從兩年前開始，筆者和劉汝佳老師開始考慮對本書進行增補。

我們對近些年來ACM/ICPC等信息學競賽中新增的知識和點題型進行了仔細的斟酌和比對，通過多次篩選，挑選出了一些極具代表性的習題，增補到了原書中。這些習題基本都是ACM/ICPC各個區域比賽以及世界總決賽的真題以及各國信息學競賽中的真題，部分章節中幾乎有一半習題被更新為最新題目。

具體來說，《算法競賽入門經典——訓練指南》升級版新增的內容主要有：

第2章，補充了數學部分線性篩、莫比烏斯反演以及積性函數。將FFT放到第2章並且進行了擴寫，並且增加了NTT以及FWT相關例題。

第3章，補充了字符串部分，主要是後綴自動機、Manacher字符串相關算法；倍增LCA、點分治、樹鏈剖分等樹上經典問題與方法；LCT的相關例題以及習題；離線算法，包括基於時間分治、整體二分、莫隊；kd-Tree；可持久化數據結構，包括權值線段樹、Trie、樹狀數組、Treap的可持久化版本。

第4章，補充了一道平面切割立方體的3D幾何例題（LA 5808）。

第5章，完善了一些例題題解的描述。

第6章，補充了樹分塊和樹上莫隊等內容。

以上新增部分的內容提綱及題解審閱由劉汝佳老師完成，具體的題解及代碼編寫由陳鋒完成。另外，為了提升讀者的做題體驗感，本書在牛客競賽網上提供了各章節絕大多數題目的題單（掃描封底“文泉云盤”二維碼，獲取題單及其他資源下載方式），讀者可以獲得更好的提交速度以及體驗。當然，讀者也可以挑選自己薄弱的章節，有針對性地進行題目的練習。

第1章 算法設計基礎 1

1.1 思維的體操 1

1.2 問題求解常見策略 14

1.3 高效算法設計舉例 36

1.4 動態規劃專題 55

1.5 小結與習題 71

1.5.1 問題求解策略 72

1.5.2 高效算法設計 80

1.5.3 動態規劃 83

第2章 數學基礎 86

2.1 基本計數方法 86

2.2 遞推關係 92

2.3 數論 101

2.3.1 基本概念 102

2.3.2 模方程 107

2.3.3 線性篩 113

2.3.4 積性函數與莫比烏斯反演 116

2.3.5 篩法求解積性函數 118

2.4 組合遊戲 124

2.5 概率與數學期望 130

2.6 置換及其應用 135

2.7 矩陣和線性方程組 142

2.8 快速傅裡葉變換（FFT） 154

2.9 數值方法 165

2.10 小結與習題 171

2.10.1 組合計數 173

2.10.2 數論 177

2.10.3 組合遊戲 181

2.10.4 概率 183

2.10.5 置換 184

2.10.6 矩陣與線性方程組 186

2.10.7 快速傅裡葉變換（FFT） 188

2.10.8 數值方法 189

第3章 實用數據結構 192

3.1 基礎數據結構回顧 192

3.1.1 抽象數據類型（ADT） 192

3.1.2 優先隊列 194

3.1.3 並查集 197

3.2 區間信息的維護與查詢 199

3.2.1 二叉索引樹（樹狀數組） 200

3.2.2 RMQ問題 202

3.2.3 線段樹（1）：點修改 204

3.2.4 線段樹（2）：區間修改 207

3.3 字符串（1） 219

3.3.1 Trie 219

3.3.2 KMP算法 222

3.3.3 Aho-Corasick自動機 225

3.4 字符串（2） 229

3.4.1 後綴數組 229

3.4.2 最長公共前綴（LCP） 233

3.4.3 基於哈希值的LCP算法 235

3.4.4 回文的Manacher算法 238

3.5 字符串（3） 240

3.5.1 後綴自動機的性質 241

3.5.2 後綴鏈接樹（Suffix Link Tree） 241

3.5.3 後綴自動機的構造算法 242

3.6 排序二叉樹 255

3.6.1 基本概念 255

3.6.2 用Treap實現名次樹 258

3.6.3 用伸展樹實現可分裂與合並的序列 266

3.7 樹的經典問題與方法 270

3.8 動態樹與LCT 289

3.9 離線算法 299

3.10 kd-Tree 312

3.11 可持久化數據結構 319

3.12 小結與習題 331

3.12.1 基礎數據結構 332

3.12.2 區間信息維護 333

3.12.3 字符串算法 335

3.12.4 排序二叉樹 338

3.12.5 樹的經典問題與方法 339

3.12.6 動態樹與LCT 342

3.12.7 離線算法 344

3.12.8 kd-Tree 347

3.12.9 可持久化數據結構 348

第4章 幾何問題 351

4.1 二維幾何基礎 351

4.1.1 基本運算 352

4.1.2 點和直線 353

4.1.3 多邊形 355

4.1.4 例題選講 356

4.1.5 二維幾何小結 359

4.2 與圓和球有關的計算問題 360

4.2.1 圓的相關計算 360

4.2.2 球面相關問題 366

4.3 二維幾何常用算法 366

4.3.1 點在多邊形內的判定 366

4.3.2 凸包 368

4.3.3 半平面交 372

4.3.4 平面區域 378

4.4 三維幾何基礎 382

4.4.1 三維點積 383

4.4.2 三維叉積 384

4.4.3 三維凸包 386

4.4.4 例題選講 388

4.4.5 三維幾何小結 392

4.5 小結與習題 393

4.5.1 基礎題目 393

4.5.2 二維幾何計算 395

4.5.3 幾何算法 398

4.5.4 三維幾何 403

第5章 圖論算法與模型 408

5.1 基礎題目選講 408

5.2 深度優先遍歷 411

5.2.1 無向圖的割頂和橋 413

5.2.2 無向圖的雙連通分量 416

5.2.3 有向圖的強連通分量 420

5.2.4 2-SAT問題 424

5.3 最短路問題 428

5.3.1 再談Dijkstra算法 428

5.3.2 再談Bellman-Ford算法 432

5.3.3 例題選講 436

5.4 生成樹相關問題 443

5.5 二分圖匹配 447

5.5.1 二分圖最大匹配 447

5.5.2 二分圖最佳完美匹配 448

5.5.3 穩定婚姻問題 452

5.5.4 常見模型 455

5.6 網絡流問題 457

5.6.1 最短增廣路算法 457

5.6.2 最小費用最大流算法 462

5.6.3 建模與模型變換 464

5.6.4 例題選講 467

5.7 小結與習題 472

5.7.1 基礎知識和算法 472

5.7.2 DFS及其應用 472

5.7.3 最短路及其應用 476

5.7.4 最小生成樹 477

5.7.5 二分圖匹配 479

5.7.6 網絡流 480

第6章 更多算法專題 484

6.1 輪廓線動態規劃 484

6.2 嵌套和分塊數據結構 490

6.3 暴力法專題 500

6.3.1 路徑尋找問題 500

6.3.2 對抗搜索 505

6.3.3 精確覆蓋問題和DLX算法 510

6.4 幾何專題 516

6.4.1 仿射變換與矩陣 516

6.4.2 離散化和掃描法 518

6.4.3 運動規劃 527

6.5 數學專題 529

6.5.1 小專題集錦 530

6.5.2 線性規劃 532

6.6 淺談代碼設計與靜態查錯 533

6.6.1 簡單的Bash 533

6.6.2 《仙劍奇俠傳四》之最後的戰役 542

6.7 小結與習題 548

6.7.1 輪廓在線的動態規劃 548

6.7.2 數據結構綜合應用 550

6.7.3 暴力法 557

6.7.4 幾何專題 562

6.7.5 數學專題 567

6.7.6 代碼組織與調試 569

附錄 Java、C#和Python語言簡介 575

主要參考書目 582

第 1章 算法設計基礎 算法設計基礎

在《算法競賽入門經典（第2版）》一書中，已經討論過算法分析、漸進時間復雜度等基本概念，以及分治、貪心、動態規劃等常見的算法設計方法。本章是《算法競賽入門經典（第2版）》的延伸，通過例題介紹更多的算法設計方法和技巧。

1.1 思維的體操 例題1 勇者斗惡龍（The Dragon of Loowater, UVa 11292）

假設你是一位國王，你的王國裡有一條n個頭的惡龍，你希望雇一些騎士把它殺死（即砍掉惡龍的所有頭）。王國裡有m個騎士可以雇用，一個能力值為x的騎士可以砍掉惡龍一個直徑不超過x的頭，且需要支付x個金幣。如何雇用騎士才能砍掉惡龍的所有頭，且需要支付的金幣最少？注意，一個騎士只能砍一個頭（且不能被雇用兩次）。

【輸入格式】

輸入包含多組數據。每組數據：第一行為正整數n和m（1≤n,m≤20 000）；接下來n行每行為一個正整數，即惡龍每個頭的直徑；再接下來m行每行為一個正整數，即每個騎士的能力。輸入結束標志為n=m=0。

【輸出格式】

對於每組數據，輸出最少花費。如果無解，輸出“Loowater is doomed!”。

【樣例輸入】

2 3

5

4

7

8

4

2 1

5

5

10

0

【樣例輸出】

11

Loowater is doomed!

【分析】

能力強的騎士開價高是合理的，但如果被你派去砍惡龍的一個很弱的頭，就是浪費人

算法競賽入門經典—訓練指南

·2·

才了。因此，可以把雇用來的騎士按照能力從小到大排序，把惡龍的所有頭按照直徑從小到大排序，一個一個砍就可以了。當然，不能砍掉“當前需要砍的頭”的騎士就不要雇用了。代碼如下。

#include

#include // 因為用到了 sort

using namespace std;

const int maxn = 20000 + 5;

int A[maxn], B[maxn];

int main() {

int n, m;

while(scanf("%d%d", &n, m) == 2 && n { while(scanf("%d%d", &n, m) == 2 && n {

for(int i = 0; < n; i++) scanf("%d", &A[i]); for(int i = 0; < n; i++) scanf("%d", &A[i]);

for(int i = 0; < m; i++) scanf("%d", &B[i]); for(int i = 0; < m; i++) scanf("%d", &B[i]);

sort(A, A+n);

sort(B, B+m);

int cur = 0; int cur = 0; // 當前需要砍掉的頭編號

int cost = 0; int cost = 0; // 當前總費用

for(int i = 0; < m; i++) for(int i = 0; < m; i++)

if(B[i] >= A[cur]) { if(B[i] >= A[cur]) {

cost += B[i]; cost += B[i]; // 雇用該騎士

if(++cur == n) break; if(++cur == n) break; // 如果頭已經砍完，及時退出循環

}

if(cur < n) printf("Loowater is doomed! if(cur < n) printf("Loowater is doomed! \n");

else p rintf("%d \n", cost); n", cost);

}

return 0;

}

例題2 突擊戰（Commando War, UVa 11729）

假設你帶領團隊去執行一組突擊任務，你有n個部下，每個部下需要完成一項任務。第i個部下需要你花Bi分鐘交代任務，然後他會立刻獨立地、無間斷地執行Ji分鐘後完成任務。你需要選擇交代任務的順序，使得所有任務盡早執行完畢（即最後一個執行完的任務應盡早結束）。注意，不能同時給兩個部下交代任務，但部下們可以同時執行他們各自的任務。

【輸入格式】

輸入包含多組數據。每組數據：第一行為部下的個數n（1≤n≤1000）；接下來n行每行為兩個正整數B和J（1≤B≤10 000，1≤J≤10 000），即交代任務的時間和執行任務的時間。輸入結束標志為n=0。

【輸出格式】

對於每組數據，輸出所有任務完成的最短時間。

【樣例輸入】

3

2 5

第 1 章 算法設計基礎

·3·

3 2

2 1

3

3

4

5

0

【樣例輸出】

Case 1: 8

Case 2: 15

【分析】

直覺告訴我們，執行時間較長的任務應該先交代。於是我們想到這樣一個貪心算法：按照J從大到小的順序給各個任務排序，然後依次交代。代碼如下。

#include

#include

#include

using namespace std;

struct Job {

int j, b;

bool operator < (const Job& x) { bool operator < (const Job& x) { // 運算符重載，不要忘記 const 修飾符

return j > x.j;

}

};

int main() {

int n, b, j, kase = 1; int n, b, j, kase = 1;

while(scanf("%d", &n) == 1 && { &n) == 1 && {

vector v;

for(int i = 0; < n; i++) { for(int i = 0; < n; i++) {

scanf("%d%d", &b, j); v.push_back((Job){j,b}); scanf("%d%d", &b, j); v.push_back((Job){j,b});

}

sort(v.begin(), end()); sort(v.begin(), end()); // 使用 Job 類自己的 < 運算符排序 運算符排序

int s = 0;

int ans = 0;

for(int i = 0; < n; i++) { for(int i = 0; < n; i++) {

s += v[i].b; += v[i].b; // 當前任務的開始執行時間

ans = max(ans, s+v[i].j); ans = max(ans, s+v[i].j); // 更新任務執行完畢時的最晚間

}

printf("Case %d: d \n", kase++, ans);

}

return 0;

}

上述代碼直接交上去就可以通過測試了。

可是為什麼這樣做是對的呢？假設我們交換兩個相鄰的任務X和Y（交換前X在Y之

算法競賽入門經典—訓練指南

·4·

前，交換後Y 在X 之前），不難發現這對其他任務的完成時間沒有影響，那麼這兩個任務呢？

❑ 情況一：交換之前，任務Y 比X 先結束，如圖1-1（a）所示。不難發現，交換之後X

的結束時間延後，Y 的結束時間提前，最終結果不會變好。

❑ 情況二：交換之前，X 比Y 先結束，則交換後結果變好的充要條件是：交換後X 的結

束時間比交換前Y 的結束時間早（交換後Y 的結束時間肯定變早了）。反之，如果出現

如圖1-1（b）所示的情況，則交換後的結果不會變好，交換後結果變好的充要條件可

以寫成B[Y]+B[X]+J[X]

算法的依據。

時間

交代執行

交代執行

交代執行

交待執行

時間

交代執行

交代執行

交代執行

交代執行

先後順序是關鍵

B[Y]+B[X]+J[X]

B[X]+B[Y]+J[Y]

X

Y

Y

X

X

Y

Y

X

(a) (b)

圖 1-1

例題3 分金幣（Spreading the Wealth, UVa 11300）

圓桌旁坐著n 個人，每人有一定數量的金幣，金幣總數能被n 整除。每個人可以給他

左右相鄰的人一些金幣，最終使得每個人的金幣數目相等。你的任務是求出被轉手的金幣

數量的最小值。比如，n=4，且4 個人的金幣數量分別為1,2,5,4 時，只需轉移4 枚金幣（第

3 個人給第2 個人2 枚金幣，第2 個人和第4 個人分別給第1 個人1 枚金幣）即可實現每人

手中的金幣數目相等。

【輸入格式】

輸入包含多組數據。每組數據：第一行為正整數n（n≤1 000 000），以下n 行每行為

一個正整數，按逆時針順序給出每個人擁有的金幣數。輸入結束標志為文件結束符（EOF）。

【輸出格式】

對於每組數據，輸出被轉手金幣數量的最小值。輸入保證這個值在64 位無符號整數範

圍內。

【樣例輸入】

3

100

100

100

4

1

第1 章 算法設計基礎

·5·

2

5

4

【樣例輸出】

0

4

【分析】

這道題目看起來很復雜，讓我們慢慢分析。首先，最終每個人的金幣數量可以計算出

來，它等於金幣總數除以人數n。接下來我們用M 來表示每人最終擁有的金幣數。

假設有4 個人，按逆時針順序編號為1, 2, 3, 4。假設1 號給2 號3 枚金幣，然後2 號又

給1 號5 枚金幣，這實際上等價於2 號給1 號2 枚金幣，而1 號什麼也沒給2 號。這樣，

可以設x2 表示2 號給了1 號多少個金幣。如果x2<0，說明實際上是1 號給了2 號-x2 枚金幣。

同理，可以設x1，x3，x4，其含義類似。注意，由於是環形，x1 指的是1 號給4 號多少金幣。

現在假設編號為i 的人初始有Ai 枚金幣。對於1 號來說，他給了4 號x1 枚金幣，還剩

Ai-x1 枚；但因為2 號給了他x2 枚金幣，所以最後還剩A1-x1+x2 枚金幣。根據題設，該金幣

數等於M。換句話說，我們得到了一個方程：A1-x1+x2=M。

同理，對於第2 個人，有A2-x2+x3=M。最終，我們可以得到n 個方程，一共有n 個變

量，是不是可以直接解方程組了呢？很顯然，還不行。因為從前n-1 個方程可以推導出最

後一個方程（想一想，為什麼）。所以，實際上只有n-1 個方程是有用的。

盡管無法直接解出答案，但我們還是可以嘗試著用x1 表示出其他的xi，則本題就變成

了單變量的極值問題。

對於第1 個人，A1-x1+x2=M Þ x2=M-A1+x1=x1-C1（C1=A1-M）

對於第2 個人，A2-x2+x3=M Þ x3=M-A2+x2=2M-A1-A2+x1=x1-C2（C2=A1+A2-2M）

對於第3 個人，A3-x3+x4=M Þ x4=M-A3+x3=3M-A1-A2-A3+x1=x1-C3（C3=A1+A2+ A3-3M）

…

對於第n 個人，An-xn+x1=M。這是一個多餘的等式，並不能給我們更多的信息（想一

想，為什麼）。

我們希望所有xi 的絕對值之和盡量小，即1 1 1 1 2 1 1 | | | | | | | | n x x C x C x C − + − + − + + − 要最

小。注意到 |x1-Ci| 的幾何意義是數軸上點x1 到點Ci 的距離，所以問題變成了：給定數軸上

的n 個點，找出一個到它們的距離之和盡量小的點。

下一步可能有些跳躍。不難猜到，這個最優的x1 就是這些數的“中位數”（即排序以

後位於中間的數），因此只需要排個序就可以了。性急的讀者可能又想跳過證明了，但是

筆者希望您這次能好好讀一讀，因為它實在是太優美、太巧妙了，而且在不少其他題目中

也能用上（我們很快就會再見到一例）。

注意，我們要證明的是：給定數軸上的n 個點，在數軸上的所有點中，中位數離所有

頂點的距離之和最小。凡是能轉化為這個模型的題目都可以用中位數求解，並不只適用於

本題。

算法競賽入門經典—訓練指南

·6·

讓我們把數軸和上面的點畫出來，如圖1-2 所示。

圖 1-2

任意找一個點，比如圖1-2 中的灰點。它左邊有4 個輸入點，右邊有2 個輸入點。把它

往左移動一點，不要移得太多，以免碰到輸入點。假設移動了d 單位距離，則灰點左邊4

個點到它的距離各減少了d，右邊的兩個點到它的距離各增加了d，但總的來說，距離之和

減少了2d。

如果灰點的左邊有2 個點，右邊有4 個點，道理類似，不過應該向右移動。換句話說，

只要灰點左右的輸入點不一樣多，就不是最優解。什麼情況下左右的輸入點一樣多呢？如

果輸入點一共有奇數個，則灰點必須和中間的那個點重合（中位數）；如果有偶數個，則

灰點可以位於最中間的兩個點之間的任意位置（還是中位數）。代碼如下。

#include

#include

using namespace std;

const int maxn = 1000000 + 10;

long long A[maxn], C[maxn], tot, M;

int main() {

int n;

while(scanf("%d", &n) == 1) { //輸入數據大，scanf 比cin 快

tot = 0;

//用%lld 輸入long long

for(int i = 1; i <= n; i++) { scanf("%lld", &A[i]); tot += A[i]; }

M = tot / n;

C[0] = 0;

for(int i = 1; i < n; i++) C[i] = C[i-1] + A[i] - M; //遞推C 數組

sort(C, C+n);

long long x1 = C[n/2], ans = 0; //計算x1

//把x1 代入，計算轉手的總金幣數

for(int i = 0; i < n; i++) ans += abs(x1 - C[i]);

printf("%lld\n", ans);

}

return 0;

}

程序本身並沒有太多技巧可言，但需要注意的是long long 的輸入輸出。在《算法競賽

入門經典（第2 版）》中我們已經解釋過了，%lld 這個占位符並不是跨平臺的。比如，Windows

下的mingw 需要用%I64d 而不是%lld。雖然cin/cout 沒有這個問題，但是本題輸入量比較大，

cin/cout 會很慢。有兩個解決方案：一是自己編寫輸入輸出函數（前面已經給過範例），二

是使用ios::sync_ with_stdio(false)，通過關閉ios 和stdio 之間的同步來加速，有興趣的讀者

可以自行搜索詳細信息。