掃一掃
關注中圖網
官方微博
本類五星書更多>
-
>
全國計算機等級考試最新真考題庫模擬考場及詳解·二級MSOffice高級應用
-
>
決戰行測5000題(言語理解與表達)
-
>
軟件性能測試.分析與調優實踐之路
-
>
第一行代碼Android
-
>
JAVA持續交付
-
>
EXCEL最強教科書(完全版)(全彩印刷)
-
>
深度學習
算法競賽入門經典訓練指南 版權信息
- ISBN：9787302571742
- 條形碼：9787302571742 ; 978-7-302-57174-2
- 裝幀：一般膠版紙
- 冊數：暫無
- 重量：暫無
- 所屬分類：>>
算法競賽入門經典訓練指南 本書特色
作者授課視頻資源：https://www.bilibili.com/video/av94769035 《算法競賽入門經典——訓練指南（升級版）》是算法屆大神劉汝佳所著信息學奧賽紅寶書——《算法競賽入門經典》的拓展訓練用書。 訓練指南2021新版增補了大量ACM/ICPC/NOI/NOIP的新知識點和新題型，優化了部分算法模板，擴增了分類專項練習題。 這是一本單書銷售9萬冊，叢書銷售35萬冊，連UVa線上評測系統創始人、ACM/ICPC國際指導委員Miguel A.Revilla都推薦的算法競賽訓練題集。 這是一本在程序員中家喻戶曉、被大量學校廣泛采作教材的算法競賽經典之作。 這不是一本入門圖書。想看懂它，需要你具備一定的算法基礎。 這本書，如果你能獨立完成大部分，你的算法能力完全能達到現今IT公司內程序員的中上水準。 這本書和《算法競賽入門經典（第2版）》珠聯璧合，相輔相成。它會像朋友和知己一樣，同你一起探討和研究問題，直至你打開算法之美的大門！ ACM入門經典，我們相見恨晚！！
算法競賽入門經典訓練指南 內容簡介
《算法競賽入門經典——訓練指南（升級版）》是《算法競賽入門經典（第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.2 RMQ問題 202
3.2.3 線段樹（1）：點修改 204
3.2.4 線段樹（2）：區間修改 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 后綴數組 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 后綴鏈接樹（Suffix Link Tree） 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 動態樹與LCT 289
3.9 離線算法 299
3.10 kd-Tree 312
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 動態樹與LCT 342
3.12.7 離線算法 344
3.12.8 kd-Tree 347
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.4 2-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.2 DFS及其應用 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 簡單的Bash 533
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
展開全部
算法競賽入門經典訓練指南 節選
第 1章 算法設計基礎 算法設計基礎 在《算法競賽入門經典（第2版）》一書中，已經討論過算法分析、漸進時間復雜度等基本概念，以及分治、貪心、動態規劃等常見的算法設計方法。本章是《算法競賽入門經典（第2版）》的延伸，通過例題介紹更多的算法設計方法和技巧。 1.1 思維的體操 例題1 勇者斗惡龍（The Dragon of Loowater, UVa 11292） 假設你是一位國王，你的王國里有一條n個頭的惡龍，你希望雇一些騎士把它殺死（即砍掉惡龍的所有頭）。王國里有m個騎士可以雇用，一個能力值為x的騎士可以砍掉惡龍一個直徑不超過x的頭，且需要支付x個金幣。如何雇用騎士才能砍掉惡龍的所有頭，且需要支付的金幣*少？注意，一個騎士只能砍一個頭（且不能被雇用兩次）。 【輸入格式】 輸入包含多組數據。每組數據：**行為正整數n和m（1≤n,m≤20 000）；接下來n行每行為一個正整數，即惡龍每個頭的直徑；再接下來m行每行為一個正整數，即每個騎士的能力。輸入結束標志為n=m=0。 【輸出格式】 對于每組數據，輸出*少花費。如果無解，輸出“Loowater is doomed!”。 【樣例輸入】 2 3 5 4 7 8 4 2 1 5 5 10 0 【樣例輸出】 11 Loowater is doomed! 【分析】 能力強的騎士開價高是合理的，但如果被你派去砍惡龍的一個很弱的頭，就是浪費人 算法競賽入門經典—訓練指南 ·2· 才了。因此，可以把雇用來的騎士按照能力從小到大排序，把惡龍的所有頭按照直徑從小到大排序，一個一個砍就可以了。當然，不能砍掉“當前需要砍的頭”的騎士就不要雇用了。代碼如下。 #include #include // 因為用到了 sort using namespace std; const int maxn = 20000 + 5; int A[maxn], B[maxn]; int main() { int n, m; while(scanf("%d%d", &n, m) == 2 && n { while(scanf("%d%d", &n, m) == 2 && n { for(int i = 0; = A[cur]) { if(B[i] >= A[cur]) { cost += B[i]; cost += B[i]; // 雇用該騎士 if(++cur == n) break; if(++cur == n) break; // 如果頭已經砍完，及時退出循環 } if(cur x.j; } }; int main() { int n, b, j, kase = 1; int n, b, j, kase = 1; while(scanf("%d", &n) == 1 && { &n) == 1 && { vector v; for(int i = 0; <> 算法的依據。 時間 交代執行 交代執行 交代執行 交待執行 時間 交代執行 交代執行 交代執行 交代執行 先后順序是關鍵 B[Y]+B[X]+J[X] B[X]+B[Y]+J[Y] X Y Y X X Y Y X (a) (b) 圖 1-1 例題3 分金幣（Spreading the Wealth, UVa 11300） 圓桌旁坐著n 個人，每人有一定數量的金幣，金幣總數能被n 整除。每個人可以給他 左右相鄰的人一些金幣，*終使得每個人的金幣數目相等。你的任務是求出被轉手的金幣 數量的*小值。比如，n=4，且4 個人的金幣數量分別為1,2,5,4 時，只需轉移4 枚金幣（第 3 個人給第2 個人2 枚金幣，第2 個人和第4 個人分別給第1 個人1 枚金幣）即可實現每人 手中的金幣數目相等。 【輸入格式】 輸入包含多組數據。每組數據：**行為正整數n（n≤1 000 000），以下n 行每行為 一個正整數，按逆時針順序給出每個人擁有的金幣數。輸入結束標志為文件結束符（EOF）。 【輸出格式】 對于每組數據，輸出被轉手金幣數量的*小值。輸入保證這個值在64 位無符號整數范 圍內。 【樣例輸入】 3 100 100 100 4 1 第1 章 算法設計基礎 ·5· 2 5 4 【樣例輸出】 0 4 【分析】 這道題目看起來很復雜，讓我們慢慢分析。首先，*終每個人的金幣數量可以計算出 來，它等于金幣總數除以人數n。接下來我們用M 來表示每人*終擁有的金幣數。 假設有4 個人，按逆時針順序編號為1, 2, 3, 4。假設1 號給2 號3 枚金幣，然后2 號又 給1 號5 枚金幣，這實際上等價于2 號給1 號2 枚金幣，而1 號什么也沒給2 號。這樣， 可以設x2 表示2 號給了1 號多少個金幣。如果x2<0，說明實際上是1 號給了2 號-x2 枚金幣。 同理，可以設x1，x3，x4，其含義類似。注意，由于是環形，x1 指的是1 號給4 號多少金幣。 現在假設編號為i 的人初始有Ai 枚金幣。對于1 號來說，他給了4 號x1 枚金幣，還剩 Ai-x1 枚；但因為2 號給了他x2 枚金幣，所以*后還剩A1-x1+x2 枚金幣。根據題設，該金幣 數等于M。換句話說，我們得到了一個方程：A1-x1+x2=M。 同理，對于第2 個人，有A2-x2+x3=M。*終，我們可以得到n 個方程，一共有n 個變 量，是不是可以直接解方程組了呢？很顯然，還不行。因為從前n-1 個方程可以推導出* 后一個方程（想一想，為什么）。所以，實際上只有n-1 個方程是有用的。 盡管無法直接解出答案，但我們還是可以嘗試著用x1 表示出其他的xi，則本題就變成 了單變量的極值問題。 對于第1 個人，A1-x1+x2=M ?? x2=M-A1+x1=x1-C1（C1=A1-M） 對于第2 個人，A2-x2+x3=M ?? x3=M-A2+x2=2M-A1-A2+x1=x1-C2（C2=A1+A2-2M） 對于第3 個人，A3-x3+x4=M ?? x4=M-A3+x3=3M-A1-A2-A3+x1=x1-C3（C3=A1+A2+ A3-3M） … 對于第n 個人，An-xn+x1=M。這是一個多余的等式，并不能給我們更多的信息（想一 想，為什么）。 我們希望所有xi 的絕對值之和盡量小，即1 1 1 1 2 1 1 | | | | | | | | n x x C x C x C ?? + ?? + ?? + + ?? 要* 小。注意到 |x1-Ci| 的幾何意義是數軸上點x1 到點Ci 的距離，所以問題變成了：給定數軸上 的n 個點，找出一個到它們的距離之和盡量小的點。 下一步可能有些跳躍。不難猜到，這個*優的x1 就是這些數的“中位數”（即排序以 后位于中間的數），因此只需要排個序就可以了。性急的讀者可能又想跳過證明了，但是 筆者希望您這次能好好讀一讀，因為它實在是太優美、太巧妙了，而且在不少其他題目中 也能用上（我們很快就會再見到一例）。 注意，我們要證明的是：給定數軸上的n 個點，在數軸上的所有點中，中位數離所有 頂點的距離之和*小。凡是能轉化為這個模型的題目都可以用中位數求解，并不只適用于 本題。 算法競賽入門經典—訓練指南 ·6· 讓我們把數軸和上面的點畫出來，如圖1-2 所示。 圖 1-2 任意找一個點，比如圖1-2 中的灰點。它左邊有4 個輸入點，右邊有2 個輸入點。把它 往左移動一點，不要移得太多，以免碰到輸入點。假設移動了d 單位距離，則灰點左邊4 個點到它的距離各減少了d，右邊的兩個點到它的距離各增加了d，但總的來說，距離之和 減少了2d。 如果灰點的左邊有2 個點，右邊有4 個點，道理類似，不過應該向右移動。換句話說， 只要灰點左右的輸入點不一樣多，就不是*優解。什么情況下左右的輸入點一樣多呢？如 果輸入點一共有奇數個，則灰點必須和中間的那個點重合（中位數）；如果有偶數個，則 灰點可以位于*中間的兩個點之間的任意位置（還是中位數）。代碼如下。 #include #include using namespace std; const int maxn = 1000000 + 10; long long A[maxn], C[maxn], tot, M; int main() { int n; while(scanf("%d", &n) == 1) { //輸入數據大，scanf 比cin 快 tot = 0; //用%lld 輸入long long for(int i = 1; i <= n; i++) { scanf("%lld", &A[i]); tot += A[i]; } M = tot / n; C[0] = 0; for(int i = 1; i < n; i++) C[i] = C[i-1] + A[i] - M; //遞推C 數組 sort(C, C+n); long long x1 = C[n/2], ans = 0; //計算x1 //把x1 代入，計算轉手的總金幣數 for(int i = 0; i < n; i++) ans += abs(x1 - C[i]); printf("%lld\n", ans); } return 0; } 程序本身并沒有太多技巧可言，但需要注意的是long long 的輸入輸出。在《算法競賽 入門經典（第2 版）》中我們已經解釋過了，%lld 這個占位符并不是跨平臺的。比如，Windows 下的mingw 需要用%I64d 而不是%lld。雖然cin/cout 沒有這個問題，但是本題輸入量比較大， cin/cout 會很慢。有兩個解決方案：一是自己編寫輸入輸出函數（前面已經給過范例），二 是使用ios::sync_ with_stdio(false)，通過關閉ios 和stdio 之間的同步來加速，有興趣的讀者 可以自行搜索詳細信息。
算法競賽入門經典訓練指南 作者簡介
劉汝佳，2000年3月獲得NOI2000全國青少年信息學奧林匹克競賽一等獎。大一時獲2001年ACM/ICPC國際大學生程序設計競賽亞洲-上海賽區冠軍和2002年世界總決賽銀牌。2004年至今共為 ACM/ICPC亞洲賽區命題二十余道，擔任6次裁判和2次命題總監，并應邀參加IOI和ACM/ICPC相關國際研討會。曾出版《算法競賽入門經典》《算法競賽入門經典——訓練指南》《編程挑戰》等暢銷書。 陳鋒，任職于廈門宇道信隆信息科技有限公司，擔任技術總監職務，專注于人工智能以及算法技術在金融科技領域的應用。同時擔任四川大學ACM/ICPC算法競賽集訓隊特邀指導老師，榕陽編程NOI、NOIP指導教練。所帶學員多次獲得ICPC金/銀牌，進入NOI省隊等。曾出版《算法競賽入門經典——訓練指南》《算法競賽入門經典——習題與解答》《算法競賽入門經典——算法實現》等暢銷書。
書友推薦
- >
自卑與超越
- >
李白與唐代文化
- >
推拿
- >
史學評論
- >
龍榆生：詞曲概論/大家小書
- >
中國歷史的瞬間
- >
大紅狗在馬戲團-大紅狗克里弗-助人
- >
山海經
本類暢銷
