算法競賽入門經典——訓練指南 ( 簡體 字) |
| 作者：劉汝佳 陳鋒 | 類別：1. -> 程式設計 -> 演算法 |
| 譯者： |
| 出版社：清華大學出版社 |  3dWoo書號： 54277
詢問書籍請說出此書號！【缺書】
NT售價： 590 元 |
| 出版日：5/1/2021 |
| 頁數：574 |
| 光碟數：0 |
|
站長推薦：  |
| 印刷：黑白印刷 | 語系： ( 簡體 版 ) |
| |
加入購物車  │加到我的最愛
(請先登入會員) |
| ISBN：9787302571742 |
| 作者序 | 譯者序 | 前言 | 內容簡介 | 目錄 | 序 |
| (簡體書上所述之下載連結耗時費功, 恕不適用在台灣, 若讀者需要請自行嘗試, 恕不保證) |
| 作者序： |
| 譯者序： |
前言：許多計算機相關專業的人，畢業之后除了為應付面試外，基本都很少再去碰算法。而在實際的產品或者項目開發過程中，大多數人也沒有必要親自去實現復雜的算法。因此，算法漸漸淡出程序員的日常生活。同時，在現實生活中有另外一種聲音：程序員的生活太糾結，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章，補充了樹分塊和樹上莫隊等內容。
以上新增部分的內容提綱及題解審閱由劉汝佳老師完成，具體的題解及代碼編寫由陳鋒完成。另外，為了提升讀者的做題體驗感，本書在牛客競賽網上提供了各章節絕大多數題目的題單（掃描封底“文泉云盤”二維碼，獲取題單及其他資源下載方式），讀者可以獲得更好的提交速度以及體驗。當然，讀者也可以挑選自己薄弱的章節，有針對性地進行題目的練習。
|
內容簡介：《算法競賽入門經典——訓練指南（升級版）》是《算法競賽入門經典（第2版）》一書的重要補充，旨在補充原書中沒有涉及或者講解得不夠詳細的內容，從而構建一個更完整的知識體系。本書通過大量有針對性的題目，讓抽象復雜的算法和數學具體化、實用化。
《算法競賽入門經典——訓練指南（升級版）》共包括6章，分別為算法設計基礎、數學基礎、實用數據結構、幾何問題、圖論算法與模型以及更多算法專題。全書通過206道例題深入淺出地介紹了上述領域的各個知識點、經典思維方式以及程序實現的常見方法和技巧，并在章末給出了豐富的分類習題，供讀者查漏補缺和強化學習效果。
《算法競賽入門經典——訓練指南（升級版）》題目多選自近年來ACM/ICPC區域賽和總決賽真題，內容全面，信息量大，覆蓋了常見算法競賽中的大多數細分知識點。書中還給出了所有重要的經典算法的完整程序，以及重要例題的核心代碼，既適合選手自學，也方便院校和培訓機構組織學生學習和訓練。 |
目錄：第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.2RMQ問題202
3.2.3線段樹（1）：點修改204
3.2.4線段樹（2）：區間修改207
3.3字符串（1）219
3.3.1Trie219
3.3.2KMP算法222
3.3.3Aho-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后綴鏈接樹（SuffixLinkTree）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動態樹與LCT289
3.9離線算法299
3.10kd-Tree312
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動態樹與LCT342
3.12.7離線算法344
3.12.8kd-Tree347
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.42-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.2DFS及其應用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簡單的Bash533
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
|
| 序： |
