《ACM國際大學生程式設計競賽：知識與入門》是2012年清華大學出版社出版的圖書，作者是俞勇。
基本介紹
- 書名：ACM國際大學生程式設計競賽：知識與入門
- ISBN：9787302294900
書籍信息,內容簡介,圖書目錄,
書籍信息
作者：俞勇 主編
定價：29元
印次：1-3
ISBN：9787302294900
出版日期：2012.12.01
印刷日期：2015.06.09
內容簡介
ACM國際大學生程式設計競賽（ACM-ICPC）是國際上公認的水平最高、規模最大、影響最深的計算機專業競賽，目前全球參與人數達20多萬。本書作者將16年的教練經驗與積累撰寫成本系列叢書，全面、深入而系統地將ACM-ICPC展現給讀者。本系列叢書包括《ACM國際大學生程式設計競賽：知識與入門》、《ACM國際大學生程式設計競賽：算法與實現》、《ACM國際大學生程式設計競賽：題目與解讀》、《ACM國際大學生程式設計競賽：比賽與思考》等4冊，其中《ACM國際大學生程式設計競賽：知識與入門》介紹了ACM-ICPC的知識及其分類、進階與角色、線上評測系統；《ACM國際大學生程式設計競賽：算法與實現》介紹了ACM-ICPC算法分類、實現及索引；
圖書目錄
第一部分 入門與進階
第1章 入門 3
1.1 ACM-ICPC競賽介紹 3
1.2 新手入門 5
1.3 團隊的分工與配合 7
1.4 訓練 9
1.5 備戰分區賽 12
1.6 備戰總決賽 13
第2章 進階 16
2.1 如何提高讀題能力 16
2.2 如何提高代碼能力 17
2.3 Bug與Debug 19
2.4 從做題者到命題者 20
第二部分 知識點與求解策略
第3章 數學基礎 25
3.1 函式增長與複雜性分類 25
3.1.1 漸進符號 25
3.1.2 階的計算 26
3.1.3 複雜性分類 27
3.2 機率論 28
3.2.1 事件與機率 28
3.2.2 期望與方差 30
3.3 代數學 31
3.3.1 矩陣 31
3.3.2 行列式 33
3.3.3 解線性方程組 34
3.3.4 多項式 37
3.3.5 複數 38
3.3.6 群 39
3.4 組合學 42
3.4.1 排列與組合 42
3.4.2 鴿巢原理 43
3.4.3 容斥原理 44
3.4.4 特殊計數序列 45
3.4.5 Pólya計數定理 47
3.5 博弈論 50
3.5.1 博弈樹 50
3.5.2 SG函式 51
3.5.3 Nim遊戲與Nim和 53
3.6 數論 54
3.6.1 整除 54
3.6.2 不定方程 57
3.6.3 同餘方程與歐拉定理 58
3.6.4 原根、離散對數和二項同餘
?方程 60
3.6.5 連分數 61
第4章 數據結構 64
4.1 線性表 64
4.1.1 鍊表 64
4.1.2 棧 65
4.1.3 佇列 65
4.1.4 塊狀鍊表 66
4.2 集合 67
4.2.1 散列表 67
4.2.2 並查集 69
4.3 排序 71
4.3.1 樸素排序算法 71
4.3.1.1 插入排序 71
4.3.1.2 冒泡排序 72
4.3.2 高效排序算法 73
4.3.2.1 歸併排序算法 73
4.3.2.2 快速排序算法 74
4.3.2.3 線性排序算法 76
4.4 樹 78
4.4.1 堆 78
4.4.1.1 二叉堆 78
4.4.1.2 左偏樹 80
4.4.2 二叉樹 82
4.4.2.1 二叉搜尋樹 82
4.4.2.2 Treap 84
4.4.2.3 伸展樹 85
4.4.3 線段樹 89
第5章 圖論 91
5.1 圖 91
5.1.1 基本概念 91
5.1.1.1 圖的定義與基本
?術語 91
5.1.1.2 匹配與覆蓋 92
5.1.1.3 獨立集、團與支
????????????配集 94
5.1.1.4 圖的染色 95
5.1.2 特殊圖的分類 96
5.1.3 圖的遍歷 99
5.1.3.1 深度優先遍歷 99
5.1.3.2 廣度優先遍歷 100
5.1.4 連通性 103
5.1.4.1 連通性的基本
????????????定義 103
5.1.4.2 割點與橋 104
5.1.4.3 強連通分量 105
5.1.4.4 套用：2-SAT 107
5.1.5 哈密頓路與歐拉路 108
5.1.5.1 哈密頓路 108
5.1.5.2 歐拉路 109
5.1.6 最短路 111
5.1.6.1 Bellman-ford算法 111
5.1.6.2 Dijkstra算法 113
5.1.6.3 Floyd算法 114
5.2 樹 115
5.2.1 基本概念與遍歷 115
5.2.1.1 樹的基本定義與
?術語 115
5.2.1.2 樹的遍歷 117
5.2.2 生成樹 117
5.2.2.1 生成樹的基本概念 117
5.2.2.2 Prim算法 118
5.2.2.3 Kruskal算法 120
5.2.2.4 最小生成樹的
????????????變種 121
5.2.2.5 生成樹計數 123
5.3 二分圖 124
5.3.1 最大匹配 124
5.3.2 最大權匹配 126
5.3.3 穩定婚姻 128
5.4 網路流 129
5.4.1 基本概念 129
5.4.1.1 流網路 129
5.4.1.2 殘量網路 130
5.4.1.3 增廣路徑 130
5.4.1.4 最大流最小割
????????????定理 131
5.4.2 最大流算法 131
5.4.2.1 Ford-Fulkerson
?算法 131
5.4.2.2 Dinic算法 133
5.4.3 費用流 135
5.4.4 流與割模型 137
5.4.4.1 上下界網路流 137
5.4.4.2 混合圖歐拉迴路 139
5.4.4.3 最大權閉合子圖 140
第6章 計算幾何 142
6.1 向量 142
6.2 點的有序化 143
6.3 多邊形與圓 144
6.3.1 簡單多邊形 144
6.3.2 凸包問題 146
6.3.3 圓的面積並 147
6.4 半平面交 148
6.5 經典問題 151
6.5.1 線段求交 151
6.5.2 最近點對 152
6.5.3 最遠點對 154
第7章 論題選編 156
7.1 背包問題 156
7.2 LCA與RMQ 157
7.3 快速傅立葉變換 159
7.4 字元串 161
7.4.1 字元串匹配 161
7.4.2 Trie 164
7.4.3 AC自動機 165
7.4.4 後綴數組 167
7.4.5 擴展KMP 169
第8章 求解策略 171
8.1 搜尋 171
8.2 分治 175
8.3 貪心 176
8.4 動態規劃 179
8.5 隨機化 183
第三部分 在 線 資 源
第9章 線上評測系統 187
9.1 基本使用方法 187
9.2 USACO介紹 190
9.3 CII介紹 191
9.4 PKU介紹 192
9.5 SGU介紹 193
9.6 SPOJ介紹 195
第10章 網上比賽 197
10.1 GCJ介紹 197
10.2 TopCoder介紹 199
10.3 Codeforces介紹 200
參考文獻 203
