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

定　價(jià)：￥118.00

作　者：	劉汝佳，陳鋒著
出版社：	清華大學(xué)出版社
叢編項(xiàng)：
標(biāo)　簽：	暫缺

購(gòu)買(mǎi)這本書(shū)可以去

ISBN：	9787302571742	出版時(shí)間：	2021-03-01	包裝：	平裝
開(kāi)本：	16開(kāi)	頁(yè)數(shù)：	600	字?jǐn)?shù)：

內(nèi)容簡(jiǎn)介

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

作者簡(jiǎn)介

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

圖書(shū)目錄

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