算法競賽入門經(jīng)典：訓練指南（算法藝術(shù)與信息學競賽）

定　價：￥118.00

作　者：	劉汝佳，陳鋒著
出版社：	清華大學出版社
叢編項：
標　簽：	暫缺

購買這本書可以去

ISBN：	9787302571742	出版時間：	2021-03-01	包裝：	平裝
開本：	16開	頁數(shù)：	600	字數(shù)：

內(nèi)容簡介

　　《算法競賽入門經(jīng)典——訓練指南（升級版）》是《算法競賽入門經(jīng)典（第2版）》一書的重要補充，旨在補充原書中沒有涉及或者講解得不夠詳細的內(nèi)容，從而構(gòu)建一個更完整的知識體系。本書通過大量有針對性的題目，讓抽象復雜的算法和數(shù)學具體化、實用化。《算法競賽入門經(jīng)典——訓練指南（升級版）》共包括6章，分別為算法設(shè)計基礎(chǔ)、數(shù)學基礎(chǔ)、實用數(shù)據(jù)結(jié)構(gòu)、幾何問題、圖論算法與模型以及更多算法專題。全書通過206道例題深入淺出地介紹了上述領(lǐng)域的各個知識點、經(jīng)典思維方式以及程序?qū)崿F(xiàn)的常見方法和技巧，并在章末給出了豐富的分類習題，供讀者查漏補缺和強化學習效果。《算法競賽入門經(jīng)典——訓練指南（升級版）》題目多選自近年來ACM/ICPC區(qū)域賽和總決賽真題，內(nèi)容全面，信息量大，覆蓋了常見算法競賽中的大多數(shù)細分知識點。書中還給出了所有重要的經(jīng)典算法的完整程序，以及重要例題的核心代碼，既適合選手自學，也方便院校和培訓機構(gòu)組織學生學習和訓練。

作者簡介

　　劉汝佳，2000年3月獲得NOI2000全國青少年信息學奧林匹克競賽一等獎。大一時獲2001年ACM/ICPC國際大學生程序設(shè)計競賽亞洲-上海賽區(qū)冠軍和2002年世界總決賽銀牌。2004年至今共為 ACM/ICPC亞洲賽區(qū)命題二十余道，擔任6次裁判和2次命題總監(jiān)，并應邀參加IOI和ACM/ICPC相關(guān)國際研討會。曾出版《算法競賽入門經(jīng)典》《算法競賽入門經(jīng)典——訓練指南》《編程挑戰(zhàn)》等暢銷書。陳鋒，任職于廈門宇道信隆信息科技有限公司，擔任技術(shù)總監(jiān)職務，專注于人工智能以及算法技術(shù)在金融科技領(lǐng)域的應用。同時擔任四川大學ACM/ICPC算法競賽集訓隊特邀指導老師，榕陽編程NOI、NOIP指導教練。所帶學員多次獲得ICPC金/銀牌，進入NOI省隊等。曾出版《算法競賽入門經(jīng)典——訓練指南》《算法競賽入門經(jīng)典——習題與解答》《算法競賽入門經(jīng)典——算法實現(xiàn)》等暢銷書。

圖書目錄

第1章算法設(shè)計基礎(chǔ) 1
1.1 思維的體操 1
1.2 問題求解常見策略 14
1.3 高效算法設(shè)計舉例 36
1.4 動態(tài)規(guī)劃專題 55
1.5 小結(jié)與習題 71
1.5.1 問題求解策略 72
1.5.2 高效算法設(shè)計 80
1.5.3 動態(tài)規(guī)劃 83
第2章數(shù)學基礎(chǔ) 86
2.1 基本計數(shù)方法 86
2.2 遞推關(guān)系 92
2.3 數(shù)論 101
2.3.1 基本概念 102
2.3.2 模方程 107
2.3.3 線性篩 113
2.3.4 積性函數(shù)與莫比烏斯反演 116
2.3.5 篩法求解積性函數(shù) 118
2.4 組合游戲 124
2.5 概率與數(shù)學期望 130
2.6 置換及其應用 135
2.7 矩陣和線性方程組 142
2.8 快速傅里葉變換（FFT） 154
2.9 數(shù)值方法 165
2.10 小結(jié)與習題 171
2.10.1 組合計數(shù) 173
2.10.2 數(shù)論 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 數(shù)值方法 189
第3章實用數(shù)據(jù)結(jié)構(gòu) 192
3.1 基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)回顧 192
3.1.1 抽象數(shù)據(jù)類型（ADT） 192
3.1.2 優(yōu)先隊列 194
3.1.3 并查集 197
3.2 區(qū)間信息的維護與查詢 199
3.2.1 二叉索引樹（樹狀數(shù)組） 200
3.2.2 RMQ問題 202
3.2.3 線段樹（1）：點修改 204
3.2.4 線段樹（2）：區(qū)間修改 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 后綴數(shù)組 229
3.4.2 最長公共前綴（LCP） 233
3.4.3 基于哈希值的LCP算法 235
3.4.4 回文的Manacher算法 238
3.5 字符串（3） 240
3.5.1 后綴自動機的性質(zhì) 241
3.5.2 后綴鏈接樹（Suffix Link Tree） 241
3.5.3 后綴自動機的構(gòu)造算法 242
3.6 排序二叉樹 255
3.6.1 基本概念 255
3.6.2 用Treap實現(xiàn)名次樹 258
3.6.3 用伸展樹實現(xiàn)可分裂與合并的序列 266
3.7 樹的經(jīng)典問題與方法 270
3.8 動態(tài)樹與LCT 289
3.9 離線算法 299
3.10 kd-Tree 312
3.11 可持久化數(shù)據(jù)結(jié)構(gòu) 319
3.12 小結(jié)與習題 331
3.12.1 基礎(chǔ)數(shù)據(jù)結(jié)構(gòu) 332
3.12.2 區(qū)間信息維護 333
3.12.3 字符串算法 335
3.12.4 排序二叉樹 338
3.12.5 樹的經(jīng)典問題與方法 339
3.12.6 動態(tài)樹與LCT 342
3.12.7 離線算法 344
3.12.8 kd-Tree 347
3.12.9 可持久化數(shù)據(jù)結(jié)構(gòu) 348
第4章幾何問題 351
4.1 二維幾何基礎(chǔ) 351
4.1.1 基本運算 352
4.1.2 點和直線 353
4.1.3 多邊形 355
4.1.4 例題選講 356
4.1.5 二維幾何小結(jié) 359
4.2 與圓和球有關(guān)的計算問題 360
4.2.1 圓的相關(guān)計算 360
4.2.2 球面相關(guān)問題 366
4.3 二維幾何常用算法 366
4.3.1 點在多邊形內(nèi)的判定 366
4.3.2 凸包 368
4.3.3 半平面交 372
4.3.4 平面區(qū)域 378
4.4 三維幾何基礎(chǔ) 382
4.4.1 三維點積 383
4.4.2 三維叉積 384
4.4.3 三維凸包 386
4.4.4 例題選講 388
4.4.5 三維幾何小結(jié) 392
4.5 小結(jié)與習題 393
4.5.1 基礎(chǔ)題目 393
4.5.2 二維幾何計算 395
4.5.3 幾何算法 398
4.5.4 三維幾何 403
第5章圖論算法與模型 408
5.1 基礎(chǔ)題目選講 408
5.2 深度優(yōu)先遍歷 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 生成樹相關(guān)問題 443
5.5 二分圖匹配 447
5.5.1 二分圖最大匹配 447
5.5.2 二分圖最佳完美匹配 448
5.5.3 穩(wěn)定婚姻問題 452
5.5.4 常見模型 455
5.6 網(wǎng)絡(luò)流問題 457
5.6.1 最短增廣路算法 457
5.6.2 最小費用最大流算法 462
5.6.3 建模與模型變換 464
5.6.4 例題選講 467
5.7 小結(jié)與習題 472
5.7.1 基礎(chǔ)知識和算法 472
5.7.2 DFS及其應用 472
5.7.3 最短路及其應用 476
5.7.4 最小生成樹 477
5.7.5 二分圖匹配 479
5.7.6 網(wǎng)絡(luò)流 480
第6章更多算法專題 484
6.1 輪廓線動態(tài)規(guī)劃 484
6.2 嵌套和分塊數(shù)據(jù)結(jié)構(gòu) 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 運動規(guī)劃 527
6.5 數(shù)學專題 529
6.5.1 小專題集錦 530
6.5.2 線性規(guī)劃 532
6.6 淺談代碼設(shè)計與靜態(tài)查錯 533
6.6.1 簡單的Bash 533
6.6.2 《仙劍奇?zhèn)b傳四》之最后的戰(zhàn)役 542
6.7 小結(jié)與習題 548
6.7.1 輪廓線上的動態(tài)規(guī)劃 548
6.7.2 數(shù)據(jù)結(jié)構(gòu)綜合應用 550
6.7.3 暴力法 557
6.7.4 幾何專題 562
6.7.5 數(shù)學專題 567
6.7.6 代碼組織與調(diào)試 569
附錄 Java、C#和Python語言簡介 575
主要參考書目 582