《算法競賽入門經(jīng)典（第2版）》是一本算法競賽的入門與提高教材，把C/C++語言、算法和解題有機地結合在一起，淡化理論，注重學習方法和實踐技巧。全書內(nèi)容分為12 章，包括程序設計入門、循環(huán)結構程序設計、數(shù)組和字符串、函數(shù)和遞歸、C++與STL入門、數(shù)據(jù)結構基礎、暴力求解法、高效算法設計、動態(tài)規(guī)劃初步、數(shù)學概念與方法、圖論模型與算法、高級專題等內(nèi)容，覆蓋了算法競賽入門和提高所需的主要知識點，并含有大量例題和習題。書中的代碼規(guī)范、簡潔、易懂，不僅能幫助讀者理解算法原理，還能教會讀者很多實用的編程技巧；書中包含的各種開發(fā)、測試和調試技巧也是傳統(tǒng)的語言、算法類書籍中難以見到的。
《算法競賽入門經(jīng)典（第2版）》可作為全國青少年信息學奧林匹克聯(lián)賽（NOIP）復賽教材、全國青少年信息學奧林匹克競賽（NOI）和ACM國際大學生程序設計競賽（ACM/ICPC）的訓練資料，也可作為IT工程師與科研人員的參考用書。
如果你是一名程序員，如果你參加NOIP、NOI、ACM/ICPC競賽，只要你對算法感興趣，那就來吧！就是這本被最多程序員所喜愛、被大量學校廣泛作為教材的算法競賽經(jīng)典之作！
算法競賽入門經(jīng)典一書全新改版，頁碼翻倍，奇葩？非也，這是因為：
◆第一版內(nèi)容太少，讓人感覺意猶未盡。
◆有些內(nèi)容有點過時，需要與時俱進。
◆C++的介紹太少，例題太少，學有余力的同學在入門完之后有些迷茫。
此次改版就是針對這些不足，所以很讓人期待！
第2版前言
《算法競賽入門經(jīng)典》第1版出版至今已有四個年頭。這四年間發(fā)生了很多變化，如NOI系列比賽終于對STL“解禁”，如C11和C++11標準出臺，g++編譯器升級（直接導致本書第1版中官方使用的?運算符無法編譯通過），如《算法競賽入門經(jīng)典——訓練指南》的出版彌補了本書第1版的很多缺憾，再如ACM/ICPC的蓬勃發(fā)展，使更多的大學生了解并參與到了算法競賽中來……
看來，是時候給本書“升級”了。
主要的變化
我原本打算只是增加一章專門介紹C++和STL，用符合新語言規(guī)范的方式重寫部分代碼，順便增加一些例題和習題，沒想到一寫就是100頁——幾乎讓書的篇幅翻了一倍。寫作第1版時，220頁的篇幅是和諸位一線中學教師商量后定下來的，因為書太厚會讓初學者望而生畏。不過這幾年的讀者反饋讓我意識到：由于篇幅限制，太多的東西讓讀者意猶未盡，還不如多寫點。雖然之后出版了《算法競賽入門經(jīng)典——訓練指南》，但那本書的主要目標是補充知識點，即拓展知識寬度，而我更希望在知識寬度幾乎不變的情況下增加深度——我眼中的競賽應該主要比思維和實踐能力，而不是主要比見識。
索性，我繼續(xù)加大篇幅，用大量的例子（包括題目和代碼）來表現(xiàn)我想向讀者傳達的信息。一位試讀的朋友在收到第一份書稿片段時驚呼：“題目的質量比第1版提高太多了！”這正是我這次改版的主要目的。
具體來說，這次改版有以下變化：
在前4章中逐步介紹一些更實用的語言技巧，直接使用競賽題目作為例子。
全新的第5章，講解競賽中最常用的C++語法，包括STL算法和容器。
第6~7章作為基礎篇，加大代碼和技巧的比例，并適當增加例題。
第8~11章作為中級篇，增加了各種例題，著重鍛煉思維能力。
全新的第12章作為高級篇，在《算法競賽入門經(jīng)典——訓練指南》的基礎上補充少量知識點與大量精彩例題。
需要特別說明的是第12章出現(xiàn)的原因。這一章的內(nèi)容很難，而且要求讀者熟練掌握《算法競賽入門經(jīng)典——訓練指南》的主要內(nèi)容，看起來和“入門”二字是矛盾的。其實本書雖然名為“入門經(jīng)典”，實際上卻不僅只適合入門讀者。根據(jù)這幾年讀者反饋的情況來看，有相當數(shù)量的有經(jīng)驗的選手也購買了本書。原因在于：很多有經(jīng)驗的選手屬于“自學成才”，總覺得自己可能會漏掉點什么基礎知識。事實也是如此：本書中提到的很多代碼和分析技巧是傳統(tǒng)教科書中見不到的，對于很多有經(jīng)驗的選手來說也是“新鮮事物”，并且他們能比初學者更快、更好地把這些知識運用到比賽中去。本書第12章就是為這些讀者準備的。如果這樣解釋還不夠直觀，就把第12章作為一個游戲里通關后多出來的Hard模式吧！
閱讀說明
既然內(nèi)容有了較大變化，閱讀方式也需要再次說明一下。首先，和本書第1版一樣，本書最好是有人帶著學習，如老師、教練或者學長。隨著網(wǎng)絡的發(fā)展，這個條件越來越容易滿足了——就算是沒人指導，也可以在別人的博客中留言，或者在貼吧中尋求幫助。
一定要重視書中的“提示”。書中有很多“提示”部分都是非常重要的知識點或者技巧，有些提示看似平凡無奇，但如果沒有引起重視而導致賽場上丟分，可是會追悔莫及的。
接下來是關于新增第5章的。首先聲明一點，這一章并不是C++語言速成——C++語言是不可能速成的。這一章不是說你從頭讀到尾然后就掌握C++了，而是提供一個綱要，告訴你哪些東西是算法競賽中最常用的，以及這些東西應當如何使用。你可以先另外找一本書（或者閱讀網(wǎng)上的文章）學習C++，然后再看本書第5章（目的是把那些又容易暈又不那么有用的知識從腦子里刪除），也可以直接看本書第5章，每次遇到看不懂或者覺得不夠詳細的地方，再找其他參考書來學。順便說一句，就算你已經(jīng)非常熟悉C++了，也最好瀏覽一下第5章（特別是代碼�。�。這不會花費太多時間，但很可能學到有用的東西。
忍不住再說點題外話。有時學習算法的最好方法并不是編寫程序，而是手算。“手算”這個詞聽上去有點枯燥，改成“玩游戲”如何？如《雷頓教授與不可思議的小鎮(zhèn)》就是一個不錯的選擇——它包含了過河問題（謎題7、93）、找砝碼（謎題6、131）、一筆畫（謎題30、39）、n皇后（謎題80~83，130）、倒水問題（謎題23、24、78）、幻方（謎題95）、華容道（謎題97、132、135）等諸多經(jīng)典問題。
致謝
雖然多出來了200多頁，其實本書的改版工作并沒有花費太長時間（不到半年），在此期間也沒有麻煩太多朋友讀稿和討論。參與本書第2版讀稿和校對工作的幾位朋友分別是：陳鋒（第8~11章）、王玉斌（第8~9章，第12章）、郭云鏑（第12章）、曹海宇（第5章、第9章）、陳立杰（第12章）、葉子卿（第12章）、周以凡（第12章）。
感謝給我發(fā)郵件以及在googlecode的wiki中留言指出本書第1版勘誤的網(wǎng)友們：imxivid、zr95.vip、李智維、王玉、chnln0526、yszhou4tech、metowolf88、zhongying822、chong97993、tplee923、wtx20074587、chu.pang等，你們的支持和鼓勵是我寫作的重要動力。
另外，書中部分難題的題解離不開以下朋友的賜教和討論：Md.Mahbubul Hasan、Shahriar Manzoor、Derek Kisman、Per Austrin、Luis Garcia、顧昱洲、陳立杰、張培超等。
第2版的習題全部（這次不僅僅是“主要”了）來自UVa在線評測系統(tǒng)，感謝Miguel Revilla教授、他的兒子Miguel Jr.和Carlos M. Casas Cuadrado對本書的大力支持。
最后，再次感謝清華大學出版社的朱英彪編輯在這個恰當?shù)臅r機提出改版事宜，并容忍我把交稿時間一拖再拖。希望這次改版不會讓你失望。
劉汝佳
劉汝佳，1982年12月生，高中畢業(yè)于重慶市外國語學校。2000年3月獲得NOI2000全國青少年信息學奧林匹克競賽一等獎第四名，進入國家集訓隊，并因此保送到清華大學計算機科學與技術系。大一時獲2001年ACM/ICPC國際大學生程序設計競賽亞洲-上海賽區(qū)冠軍和2002年世界總決賽銀牌（世界第四），2005年獲學士學位，2008年獲碩士學位。
學生時代曾為中國計算機學會NOI科學委員會學生委員，擔任IOI2002-2008中國國家隊教練，并為NOI系列比賽命題十余道。現(xiàn)為NOI競賽委員會委員，并在NOI 25周年時獲得中國計算機學會頒發(fā)的“特別貢獻獎”。
2004年至今共為ACM/ICPC亞洲賽區(qū)命題二十余道，擔任6次裁判和2次命題總監(jiān)，并應邀參加IOI和ACM/ICPC相關國際研討會，發(fā)表論文兩篇。
2004年初作為第一作者出版專著《算法藝術與信息學競賽》，2009年出版譯著《編程挑戰(zhàn)》，2009年出版《算法競賽入門經(jīng)典》，2012年出版《算法競賽入門經(jīng)典——訓練指南》。
多年來在全國二十余個城市進行中學生競賽培訓工作，為北京、上海、吉隆坡等地的著名高校授課與宣講，并多次與TopCoder、百度和網(wǎng)易有道等知名企業(yè)合作舉辦比賽，讓更多的IT人才獲得展示自我的平臺。
第1部分 語言篇
第1章 程序設計入門 1
1.1 算術表達式 1
1.2 變量及其輸入 3
1.3 順序結構程序設計 6
1.4 分支結構程序設計 9
1.5 注解與習題 13
1.5.1 C語言、C99、C11及其他 13
1.5.2 數(shù)據(jù)類型與輸入格式 14
1.5.3 習題 15
1.5.4 小結 16
第2章 循環(huán)結構程序設計 18
2.1 for循環(huán) 18
2.2 while循環(huán)和do-while循環(huán) 22
2.3 循環(huán)的代價 25
2.4 算法競賽中的輸入輸出框架 27
2.5 注解與習題 34
2.5.1 習題 34
2.5.2 小結 36
第3章 數(shù)組和字符串 37
3.1 數(shù)組 37
3.2 字符數(shù)組 41
3.3 競賽題目選講 45
3.4 注解與習題 53
3.4.1 進位制與整數(shù)表示 54
3.4.2 思考題 55
3.4.3 黑盒測試和在線評測系統(tǒng) 55
3.4.4 例題一覽與習題 56
3.4.5 小結 59
第4章 函數(shù)和遞歸 61
4.1 自定義函數(shù)和結構體 61
4.2 函數(shù)調用與參數(shù)傳遞 65
4.2.1 形參與實參 65
4.2.2 調用棧 66
4.2.3 用指針作參數(shù) 69
4.2.4 初學者易犯的錯誤 71
4.2.5 數(shù)組作為參數(shù)和返回值 71
4.2.6 把函數(shù)作為函數(shù)的參數(shù) 73
4.3 遞歸 74
4.3.1 遞歸定義 74
4.3.2 遞歸函數(shù) 75
4.3.3 C語言對遞歸的支持 75
4.3.4 段錯誤與棧溢出 77
4.4 競賽題目選講 79
4.5 注解與習題 92
4.5.1 頭文件、副作用及其他 93
4.5.2 例題一覽和習題 95
4.5.3 小結 99
第5章 C++與STL入門 100
5.1 從C到C++ 100
5.1.1 C++版框架 101
5.1.2 引用 102
5.1.3 字符串 103
5.1.4 再談結構體 105
5.1.5 模板 106
5.2 STL初步 108
5.2.1 排序與檢索 108
5.2.2 不定長數(shù)組：vector 109
5.2.3 集合：set 112
5.2.4 映射：map 113
5.2.5 棧、隊列與優(yōu)先隊列 115
5.2.6 測試STL 120
5.3 應用：大整數(shù)類 123
5.3.1 大整數(shù)類BigInteger 124
5.3.2 四則運算 125
5.3.3 比較運算符 126
5.4 競賽題目舉例 127
5.5 習題 134
第2部分 基礎篇
第6章 數(shù)據(jù)結構基礎 139
6.1 再談棧和隊列 139
6.2 鏈表 143
6.3 樹和二叉樹 148
6.3.1 二叉樹的編號 148
6.3.2 二叉樹的層次遍歷 150
6.3.3 二叉樹的遞歸遍歷 155
6.3.4 非二叉樹 160
6.4 圖 162
6.4.1 用DFS求連通塊 162
6.4.2 用BFS求最短路 164
6.4.3 拓撲排序 167
6.4.4 歐拉回路 168
6.5 競賽題目選講 170
6.6 訓練參考 175
第7章 暴力求解法 182
7.1 簡單枚舉 182
7.2 枚舉排列 184
7.2.1 生成1~n的排列 184
7.2.2 生成可重集的排列 185
7.2.3 解答樹 186
7.2.4 下一個排列 187
7.3 子集生成 188
7.3.1 增量構造法 188
7.3.2 位向量法 188
7.3.3 二進制法 189
7.4 回溯法 191
7.4.1 八皇后問題 191
7.4.2 其他應用舉例 194
7.5 路徑尋找問題 198
7.6 迭代加深搜索 206
7.7 競賽題目選講 209
7.8 訓練參考 213
第3部分 競賽篇
第8章 高效算法設計 220
8.1 算法分析初步 220
8.1.1 漸進時間復雜度 220
8.1.2 上界分析 222
8.1.3 分治法 223
8.1.4 正確對待算法分析結果 224
8.2 再談排序與檢索 225
8.2.1 歸并排序 225
8.2.2 快速排序 227
8.2.3 二分查找 227
8.3 遞歸與分治 229
8.4 貪心法 231
8.4.1 背包相關問題 231
8.4.2 區(qū)間相關問題 232
8.4.3 Huffman編碼 234
8.5 算法設計與優(yōu)化策略 235
8.6 競賽題目選講 244
8.7 訓練參考 252
第9章 動態(tài)規(guī)劃初步 259
9.1 數(shù)字三角形 259
9.1.1 問題描述與狀態(tài)定義 259
9.1.2 記憶化搜索與遞推 260
9.2 DAG上的動態(tài)規(guī)劃 262
9.2.1 DAG模型 262
9.2.2 最長路及其字典序 262
9.2.3 固定終點的最長路和最短路 264
9.2.4 小結與應用舉例 267
9.3 多階段決策問題 270
9.3.1 多段圖的最短路 270
9.3.2 0-1背包問題 271
9.4 更多經(jīng)典模型 274
9.4.1 線性結構上的動態(tài)規(guī)劃 274
9.4.2 樹上的動態(tài)規(guī)劃 280
9.4.3 復雜狀態(tài)的動態(tài)規(guī)劃 284
9.5 競賽題目選講 290
9.6 訓練參考 303
第10章 數(shù)學概念與方法 310
10.1 數(shù)論初步 310
10.1.1 歐幾里德算法和唯一分解定理 310
10.1.2 Eratosthenes篩法 312
10.1.3 擴展歐幾里德算法 313
10.1.4 同余與模算術 314
10.1.5 應用舉例 316
10.2 計數(shù)與概率基礎 318
10.2.1 楊輝三角與二項式定理 319
10.2.2 數(shù)論中的計數(shù)問題 321
10.2.3 編碼與解碼 323
10.2.4 離散概率初步 324
10.3 其他數(shù)學專題 327
10.3.1 遞推 327
10.3.2 數(shù)學期望 332
10.3.3 連續(xù)概率 334
10.4 競賽題目選講 336
10.5 訓練參考 341
第11章 圖論模型與算法 352
11.1 再談樹 352
11.1.1 無根樹轉有根樹 352
11.1.2 表達式樹 353
11.2 最小生成樹 355
11.2.1 Kruskal算法 356
11.2.2 競賽題目選解 358
11.3 最短路問題 359
11.3.1 Dijkstra算法 359
11.3.2 Bellman-Ford算法 363
11.3.3 Floyd算法 364
11.3.4 競賽題目選講 365
11.4 網(wǎng)絡流初步 366
11.4.1 最大流問題 366
11.4.2 增廣路算法 367
11.4.3 最小割最大流定理 369
11.4.4 最小費用最大流問題 370
11.4.5 應用舉例 372
11.5 競賽題目選講 375
11.6 訓練參考 379
11.7 總結與展望 384
第12章 高級專題 386
12.1 知識點選講 386
12.1.1 自動機 386
12.1.2 樹的經(jīng)典問題和方法 392
12.1.3 可持久化數(shù)據(jù)結構 397
12.1.4 多邊形的布爾運算 399
12.2 難題選解 404
12.2.1 數(shù)據(jù)結構 404
12.2.2 網(wǎng)絡流 409
12.2.3 數(shù)學 411
12.2.4 幾何 415
12.2.5 非完美算法 419
12.2.6 雜題選講 423
12.3 小結與習題 446
附錄A 開發(fā)環(huán)境與方法 455
A.1 命令行 455
A.1.1 文件系統(tǒng) 455
A.1.2 進程 456
A.1.3 程序的執(zhí)行 456
A.1.4 重定向和管道 457
A.1.5 常見命令 457
A.2 操作系統(tǒng)腳本編程入門 458
A.2.1 Windows下的批處理 458
A.2.2 Linux下的Bash腳本 459
A.2.3 再談隨機數(shù) 460
A.3 編譯器和調試器 460
A.3.1 gcc的安裝和測試 460
A.3.2 常見編譯選項 461
A.3.3 gdb簡介 462
A.3.4 gdb的高級功能 463
A.4 淺談IDE 464
主要參考書目 465
書單推薦
