ACM國際大學生程式設計競賽：算法與實現

《ACM國際大學生程式設計競賽：算法與實現》是2013年清華大學出版社出版的圖書，作者是俞勇。

基本介紹

• 書名：ACM國際大學生程式設計競賽:算法與實現 
• 作者：俞勇
• ISBN：9787302294139
• 頁數：274頁
• 定價：￥36.00
• 出版社：清華大學出版社
• 出版時間：2013-01-01
• 裝幀：平裝
• 開本：16

書籍信息

作者：俞勇 主編　　定價：36元
印次：1-4
ISBN：9787302294139
出版日期：2013.01.01
印刷日期：2015.10.26

ACM國際大學生程式設計競賽

內容簡介

ACM國際大學生程式設計競賽（ACM-ICPC）是國際上公認的水平最高、規模最大、影響最深的計算機專業競賽，目前全球參與人數達20多萬。本書作者將16年的教練經驗與積累撰寫成本系列叢書，全面、深入而系統地將ACM-ICPC展現給讀者。本系列叢書包括《ACM國際大學生程式設計競賽：知識與入門》、《ACM國際大學生程式設計競賽：算法與實現》、《ACM國際大學生程式設計競賽：題目與解讀》、《ACM國際大學生程式設計競賽：比賽與思考》等4冊，其中《ACM國際大學生程式設計競賽：知識與入門》介紹了ACM-ICPC的知識及其分類、進階與角色、線上評測系統；《ACM國際大學生程式設計競賽：算法與實現》介紹了ACM-ICPC算法分類、實現及索引；《ACM國際大學生程式設計競賽：題目與解讀》為各類算法配備經典例題及題庫

目錄

第一部分 算 法

第1章 數學 3

1.1 矩陣 3

1.1.1 矩陣類 3

1.1.2 Gauss消元 4

1.1.3 矩陣的逆 6

1.1.4 常係數線性齊次遞推 7

1.2 整除與剩餘 9

1.2.1 歐幾里得算法 9

1.2.2 擴展歐幾里得 9

1.2.3 單變元模線性方程 10

1.2.4 中國剩餘定理 11

1.2.5 求原根 13

1.2.6 平方剩餘 14

1.2.7 離散對數 15

1.2.8 N次剩餘 16

1.3 素數與函式 18

1.3.1 素數篩法 18

1.3.2 素數判定 19

1.3.3 質因數分解 20

1.3.4 歐拉函式計算 21

1.3.5 Mobius函式計算 23

1.4 數值計算 24

1.4.1 數值積分 24

1.4.2 高階代數方程求根 26

1.5 其他 27

1.5.1 快速冪 27

1.5.2 進制轉換 28

1.5.3 格雷碼 29

1.5.4 高精度整數 30

1.5.5 快速傅立葉變換 35

1.5.6 分數類 37

1.5.7 全排列散列 38

第2章 圖論 40

2.1 圖的遍歷及連通性 40

2.1.1 前向星 40

2.1.2 割點和橋 42

2.1.3 雙連通分量 43

2.1.4 極大強連通分量Tarjan

算法 45

2.1.5 拓撲排序 47

2.1.6 2SAT 49

2.2 路徑 51

2.2.1 Dijkstra 51

2.2.2 SPFA 53

2.2.3 Floyd-Warshall 54

2.2.4 無環圖最短路 55

2.2.5 第k短路 56

2.2.6 歐拉迴路 59

2.2.7 混合圖歐拉迴路 61

2.3 匹配 64

2.3.1 匈牙利算法 64

2.3.2 Hopcroft-Karp算法 66

2.3.3 KM算法 68

2.3.4 一般圖最大匹配 71

2.4 樹 74

2.4.1 LCA 74

2.4.2 最小生成樹Prim算法 77

2.4.3 最小生成樹Kruskal算法 78

2.4.4 單度限制最小生成樹 79

2.4.5 最小樹形圖 83

2.4.6 最優比例生成樹 85

2.4.7 樹的直徑 87

2.5 網路流 89

2.5.1 最大流Dinic算法 89

2.5.2 最小割 92

2.5.3 無向圖最小割 93

2.5.4 有上下界的網路流 95

2.5.5 費用流 97

2.6 其他 100

2.6.1 完美消除序列 100

2.6.2 弦圖判定 101

2.6.3 最大團搜尋算法 103

2.6.4 極大團的計數 105

2.6.5 圖的同構 107

2.6.6 樹的同構 108

第3章 計算幾何 112

3.1 多邊形 112

3.1.1 計算幾何誤差修正 112

3.1.2 計算幾何點類 113

3.1.3 計算幾何線段類 115

3.1.4 多邊形類 117

3.1.5 多邊形的重心 118

3.1.6 多邊形內格點數 119

3.1.7 凸多邊形類 120

3.1.8 凸多邊形的直徑 123

3.1.9 半平面切割多邊形 124

3.1.10 半平面交 126

3.1.11 凸多邊形交 128

3.1.12 多邊形的核 129

3.1.13 凸多邊形與直線集交 130

3.2 圓 133

3.2.1 圓與線求交 133

3.2.2 圓與多邊形交的面積 134

3.2.3 最小圓覆蓋 137

3.2.4 圓與圓求交 138

3.2.5 圓的離散化 140

3.2.6 圓的面積並 144

3.3 三維計算幾何 147

3.3.1 三維點類 147

3.3.2 三維直線類 150

3.3.3 三維平面類 152

3.3.4 三維向量旋轉 154

3.3.5 長方體表面兩點

最短距離 155

3.3.6 四面體體積 156

3.3.7 最小球覆蓋 158

3.3.8 三維凸包 161

3.4 其他 164

3.4.1 三角形的四心 164

3.4.2 最近點對 166

3.4.3 平面最小曼哈頓距離

生成樹 167

3.4.4 最大空凸包 171

3.4.5 平面劃分 174

第4章 數據結構 179

4.1 二叉堆 179

4.2 並查集 183

4.3 樹狀數組 184

4.4 左偏樹 186

4.5 Trie 188

4.6 Treap 190

4.7 伸展樹 193

4.8 RMQ線段樹 199

4.9 ST表 201

4.10 動態樹 202

4.11 塊狀鍊表 207

4.12 樹鏈剖分 210

第5章 論題選編 213

5.1 字元串 213

5.1.1 KMP 213

5.1.2 擴展KMP 214

5.1.3 串的最小表示 216

5.1.4 有限狀態自動機 217

5.1.5 後綴數組 221

5.1.6 最長重複子串 223

5.1.7 最長公共子串 225

5.1.8 最長回文子串manacher

算法 227

5.1.9 字元串散列 228

5.2 轉換 229

5.2.1 星期計算 229

5.2.2 日期相隔天數計算 230

5.2.3 斐波那契進制轉換 232

5.2.4 羅馬進制轉換 233

5.3 構造 235

5.3.1 幻方構造 235

5.3.2 N皇后問題 237

5.3.3 旋轉魔方 239

5.3.4 騎士週遊問題 242

5.4 計算 245

5.4.1 表達式計算 245

5.4.2 最大權子矩形 247

5.4.3 矩形面積並 249

5.4.4 矩形並的周長 252

5.5 序列 255

5.5.1 第k小數 255

5.5.2 逆序對 256

5.5.3 最長公共子序列 257

5.5.4 最長公共上升子序列 259

第二部分 貼 士

第6章 代數 263

6.1 Bertrand猜想 263

6.2 差分序列 263

6.3 威爾遜定理 263

6.4 約數個數 263

6.5 行列式的值 264

6.6 最小二乘法 264

第7章 解析幾何 265

7.1 四邊形 265

7.2 拋物線 265

7.3 雙曲線 265

7.4 橢圓 266

第8章 平面立體幾何 267

8.1 費馬點 267

8.2 皮克定理 267

8.3 三角公式 267

8.4 三維幾何體 268

8.5 托勒密定理 268

第9章 組合數學 269

9.1 Catalan數 269

9.2 組合公式 269

第10章 圖論 271

10.1 樹的計數 271

10.2 有特殊條件的漢米爾頓迴路 271

10.3 普呂弗序列 272

10.4 模2意義下的二分圖匹配數 272

第11章 積分表 273