算法競賽入門經典：算法實現（簡體書）

最近三年，筆者在工作及創作之餘，一直在參與大學生ACM/ICPC以及中學生NOI系列競賽的培訓工作，在此期間認識了很多朋友，大家一起交流算法學習及比賽趣事，互相促進，甚是開心。

很多算法初學者，甚至一些算法高手，都跟我反饋，弄明白算法的基本原理之後，迫切地希望能有一本介紹相關算法代碼實現的圖書，以方便大家在練習環節和比賽時作為參考。對於大學生來說，因為ICPC競賽允許自帶資料，因此他們對這樣的算法代碼實現書有著更迫切的期望，通過調用這些簡潔、規範的代碼實現，可以大大減輕他們比賽時因來回琢磨代碼實現細節而導致調試時間大幅增加的壓力。

而在省選以及NOI賽場上也出現過因為沒有掌握較好的模板代碼，導致考場上實現時間大幅度增加，最終與獎牌失之交臂的憾事。許多中學生在學習計算幾何時並不知道劉汝佳老師在《算法競賽入門經典（第2版）》《算法競賽入門經典——訓練指南》中提供了簡潔、完整的模板代碼，這也是本書創作的一個動機。

本書內容

本書不介紹具體的算法理論知識，而是精選《算法競賽入門經典（第2版）》和《算法競賽入門經典——訓練指南》中的典型題目，按算法要點和競賽考點重新進行分拆和歸類，並提供240餘套簡潔、高效、規範、完整的實現代碼模板。此外，也加入了一些雖然未在兩本書中出現，但實際上對初學者入門非常重要的題目代碼。

全書共分為7章，各章的具體內容如下。

第1章介紹C++編程基礎與STL中的常用算法實現，共計15道真題的算法實現。

第2章介紹算法設計與優化，包含算法優化策略、貪心算法、搜索算法、動態規劃算法等內容，共計56道真題的算法實現。

第3章介紹數學相關算法，包含數論、組合計數、概率與期望、組合遊戲、置換、矩陣和線性方程組、快速傅裡葉變換（FFT）、數值方法、數學專題等內容，共計46道真題的算法實現。

第4章介紹數據結構相關算法，包含基礎數據結構、區間信息維護、排序二叉樹、樹的經典問題與方法、動態樹與LCT、離線算法、kd-tree、可持久化數據結構、嵌套和分塊數據結構等內容，共計52道真題的算法實現。

第5章介紹字符串相關算法，包含Trie與KMP以及AC自動機、後綴數組、後綴自動機等內容，共計13道真題的算法實現。

第6章介紹計算幾何相關算法，包含二維幾何基礎、圓有關的計算問題、二維幾何常用算法、三維幾何基礎、幾何專題算法等內容，共計21道真題的算法實現。

第7章介紹圖論相關算法，共包含深度優先遍歷、最短路問題、生成樹相關問題、二分圖匹配、網絡流問題，共計36道真題的算法實現。

本書只關注近些年在正式比賽（包括ACM/ICPC區域賽、NOIP以及NOI這樣的全國性比賽）中常見的算法實現。書中所有真題都極具典型性，每道題在求解過程中都經過了嚴密、仔細的剖析和反復的優化，最終擇選較優的算法代碼進行實現。

系列書學習說明

至此，“算法藝術與信息學競賽”系列已包含如下4本書。

《算法競賽入門經典（第2版）》（以下簡稱《入門經典》），是系列中的核心算法理論書。如果你是個新手，剛剛步入信息學奧賽大陣營，歡迎你學習此書，它將系統地講解C/C++語言基礎知識，數據結構知識，以及信息學奧賽和ACM/ICPC中的常考必考算法知識點、技巧和剖析。

《算法競賽入門經典——訓練指南》是《入門經典》的姊妹篇，主要針對更多的算法競賽題型進行橫向拓展，以及更廣範圍內的講解和訓練，“覆蓋面廣，點到為止，注重代碼”是本書的最大特點。

《算法競賽入門經典——習題與解答》是《入門經典》的配套習題詳解，將其中的多數練習題，尤其是限於篇幅無法展開的練習題，進行了細致的解析，使其更簡單、易學，快速提升讀者的算法思維能力。更適合初學者配合著《入門經典》一起學習。

《算法競賽入門經典——算法實現》是一本高效備考工具書，擇選近些年來信息學奧賽中最新、最經典的比賽真題，給出優化過的各類代碼實現模板，通過它可快速備考各類競賽。

讀者可以根據自己的學習情況和備戰目標，分時分段選擇不同的圖書，以最大效果地發揮“1+1>2”的事半功倍的效果。

感謝廣大讀者朋友們，你們的信任和支持是我在算法道路上能持續前行的最大動力。

祝大家讀書快樂！

目錄

第1章 C++編程基礎與STL 1

第2章 算法設計與優化 20

2.1 算法優化策略 20

2.2 貪心算法 28

2.3 搜索算法 34

2.4 動態規劃算法 60

第3章 數學 91

3.1 數論 91

3.2 組合計數 113

3.3 概率與期望 127

3.4 組合遊戲 134

3.5 置換 136

3.6 矩陣和線性方程組 139

3.7 快速傅裡葉變換（FFT） 146

3.8 數值方法 156

3.9 數學專題 159

第4章 數據結構 165

4.1 基礎數據結構 165

4.2 區間信息維護 188

4.3 排序二叉樹 202

4.4 樹的經典問題與方法 212

4.5 動態樹與LCT 229

4.6 離線算法 237

4.7 kd-Tree 249

4.8 可持久化數據結構 254

4.9 嵌套和分塊數據結構 263

第5章 字符串 275

5.1 Trie、KMP以及AC自動機 275

5.2 後綴數組、Hash和Manacher 282

5.3 後綴自動機 287

第6章 計算幾何 298

6.1 二維幾何基礎 298

6.2 與圓有關的計算問題 302

6.3 二維幾何常用算法 311

6.4 三維幾何基礎 328

6.5 幾何專題算法 342

第7章 圖論 362

7.1 深度優先遍歷 362

7.2 最短路問題 374

7.3 生成樹相關問題 395

7.4 二分圖匹配 404

7.5 網絡流問題 420

STL是C++標準模板庫（Standard Template Library）的簡稱，使用得當能夠省去不少代碼篇幅。

例1-1 【輸入輸出函數】TeX中的引號（Tex Quotes, UVa 272）

在TeX中，左雙引號是“``”，右雙引號是“''”。輸入一篇包含雙引號的文章，你的任務是把它轉換成TeX的格式。

【樣例輸入】

"To be or not to be," quoth the Bard, "that

is the question".

【樣例輸出】

``To be or not to be, '' quoth the Bard, ``that

is the question''.

【代碼實現】

// 陳鋒

#include

int main() {

int c, first = 1;

char s[2][4] = {"''", "``"};

while ((c = getchar()) != EOF) {

if (c == '"')

printf("%s", s[first]), first ^= 1;

else

printf("%c", c);

}

return 0;

}

/*

算法分析請參考:《算法競賽入門經典（第2版）》例題3-1

注意：本題是如何使用first變量及其xor運算來控制是否為首次輸出的

*/

例1-2 【計數排序與IO優化】年齡排序（Age Sort, UVa 11462）

給定n（0＜n≤2 000 000）個居民的年齡（都是1～100的整數），把它們按照從小到大的順序輸出。

【代碼實現】

// 陳鋒

#include

using namespace std;

#define _for(i, a, b) for (int i = (a); i < (b); ++i)

typedef long long LL;

const int MAXN = 100;

int main() {

int n, a, cnt[MAXN + 4];

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

fill_n(cnt, MAXN + 4, 0);

_for(i, 0, n) scanf("%d", &a), ++cnt[a];

_for(i, 0, MAXN) _for(j, 0, cnt[i])

printf("%d%s", i, (i == MAXN - 1 && j == cnt[i] - 1) ? "" : " ");

puts("");

}

}

/*

算法分析請參考:《算法競賽入門經典—訓練指南》升級版1.3節例題17

注意：本題中的fill_n函數比memset更方便，性能更好

*/

如果還要精益求精，可以優化輸入輸出，進一步降低運行時間，程序如下。

// 劉汝佳

#include

#include

#include // 為了使用isdigit宏

inline int readint() {

char c = getchar();

while(!isdigit(c)) c = getchar();

int x = 0;

while(isdigit(c)) {

x = x * 10 + c - '0';

c = getchar();

}

return x;

}

int buf[10]; // 聲明為全局變量可以減小開銷

inline void writeint(int i) {

int p = 0;if(i < 0) putchar('-'), i = -i;

if(i == 0) p++; // 特殊情況：i等於0時需要輸出0，而不是什麼也不輸出

else while(i) {

buf[p++] = i % 10,i /= 10;

}

for(int j = p - 1; j >= 0; j--) putchar('0' + buf[j]); // 逆序輸出

}

int main() {

int n, x, c[101];

while(n = readint()) {

memset(c, 0, sizeof(c));

for(int i = 0; i < n; i++) c[readint()]++;

int first = 1;

for(int i = 1; i <= 100; i++)

for(int j = 0; j < c[i]; j++) {

if(!first) putchar(' ');

first = 0;

writeint(i);

}

putchar('\n');

}

return 0;

}

例1-3 【字符函數；常量數組】回文詞（Palindromes, UVa 401）

輸入一個字符串，判斷它是否為回文串以及鏡像串。輸入字符串保證不含數字0。所謂回文串，就是反轉以後和原串相同，如abba和madam。所謂鏡像串，就是左右鏡像之後和原串相同，如2S和3AIAE。注意，並不是每個字符在鏡像之後都能得到一個合法字符。在本題中，每個字符的鏡像如圖1-1所示（空白項表示該字符鏡像後不能得到一個合法字符）。

圖1-1 鏡像字符

輸入的每行包含一個字符串（保證只有上述字符，不含空白字符），判斷它是否為回文串和鏡像串（共4種組合）。每組數據之後輸出一個空行。

【樣例輸入】

NOTAPALINDROME

ISAPALINILAPASI

2A3MEAS

ATOYOTA

【樣例輸出】

NOTAPALINDROME -- is not a palindrome.

ISAPALINILAPASI -- is a regular palindrome.

2A3MEAS -- is a mirrored string.

ATOYOTA -- is a mirrored palindrome.

【代碼實現】

// 劉汝佳

#include

using namespace std;

string rev = "A 3 HIL JM O 2TUVWXY51SE Z 8 ",

msg[] = {

"not a palindrome",

"a regular palindrome",

"a mirrored string",

"a mirrored palindrome"

};

char r(char c) {

if (isalpha(c)) return rev[c - 'A'];

return rev[c - '0' + 25];

}

int main() {

char s[32];

while (scanf("%s", s) == 1) {

int len = strlen(s), p = 1, m = 1;

for (int i = 0; i < (len + 1) / 2; i++) {

if (s[i] != s[len - 1 - i]) p = 0; // 不是回文串

if (r(s[i]) != s[len - 1 - i]) m = 0; // 不是鏡像串

}

printf("%s -- is %s.\n\n", s, msg[m * 2 + p]);

}

return 0;

}

/*

算法分析請參考:《算法競賽入門經典（第2版）》例題3-3

注意：本題中輸入字符串應該使用scanf而不是gets，以避免出現讀入空行的問題

*/

例1-4 【字典序】環狀序列（Circular Sequence, ACM/ICPC Seoul 2004, UVa 1584）

長度為n的環狀串有n種表示方法，分別為從某個位置開始順時針得到的字母序列。例如，圖1-2所示的環狀串有10種表示方法：CGAGTCAGCT、GAGTCAGCTC、AGTCAGCTCG等。在這些表示法中，字典序最小的稱為“最小表示”。

輸入一個長度為n（n≤100）的環狀DNA串（只包含A、C、G、T這4種字符）。輸入樣式對應該串所有表示方法中的一種表示法，你的任務是輸出該環狀串的最小表示。例如， CTCC的最小表示是CCCT，CGAGTCAGCT的最小表示為AGCTCGAGTC。

【代碼實現】

// 劉汝佳

#include

using namespace std;

// 環狀串s的表示法p是否比表示法q的字典序小

int less_than(const string& s, int p, int q) {

int n = s.length();

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

char cp = s[(p + i) % n], cq = s[(q + i) % n];

if (cp != cq) return cp < cq;

}

return 0; // 相等

}

int main() {

ios::sync_with_stdio(false), cin.tie(0);

int T;

string s;

cin >> T;

while (T--) {

cin >> s;

int ans = 0, n = s.length();

for (int i = 1; i < n; i++)

if (less_than(s, i, ans)) ans = i;

for (int i = 0; i < n; i++) cout << (s[(ans + i) % n]);

cout << endl;

}

return 0;

}

/*

算法分析請參考:《算法競賽入門經典（第2版）》例題3-6

注意：main()函數的第一行可以加速STL的IO操作，但不能再和stdio中的printf混用

同類問題：Periodic Strings, UVa 455

*/