基本介紹
- 書名：算法競賽入門經典:訓練指南
- 類型：考試
- 出版日期：2012年10月1日
- 語種：簡體中文
- ISBN：9787302291077
- 作者：劉汝佳 陳鋒
- 出版社：清華大學出版社
- 頁數：511頁
- 開本：16
- 品牌：清華大學出版社
基本介紹,內容簡介,作者簡介,圖書目錄,
基本介紹
內容簡介
《算法競賽入門經典:訓練指南》題目多選自近年來ACM/ICPC區域賽和總決賽真題，內容全面，信息量大，覆蓋了常見算法競賽中的大多數細分知識點。書中還給出了所有重要的經典算法的完整程式，以及重要例題的核心代碼，既適合選手自學，也方便教練組織學習和訓練。
作者簡介
劉汝佳，1982年12月生，高中畢業於重慶市外國語學校。2000年3月獲得NOI2000全國青少年信息學奧林匹克競賽一等獎第四名，進入國家集訓隊，並因此保送到清華大學計算機科學與技術系。大一時獲2001年ACM/ICPC國際大學生程式設計競賽亞洲—上海賽區冠軍和2002年世界總決賽銀牌（世界第四），2005年獲學士學位，2008年獲碩士學位。學生時代曾為中國計算機學會NOI科學委員會學生委員，擔任IOI2002—2008@國國家隊教練，並為NOI系列比賽命題十餘道。現為NOI競賽委員會委員。並在NOI 25周年時獲得中國計算機學會頒發的“特別貢獻獎”。2004年至今共為ACM/ICPC亞洲賽區命題二十餘道，擔任6次裁判和2次命題總監。並應邀參加IOI和ACM/ICPC相關國際研討會，發表論文兩篇。2004年初作為第一作者出版專著《算法藝術與信息學競賽》，2009年出版譯著《編程挑戰》。多年來在全國二十餘個城市進行中學生競賽培訓工作，為北京、上海、吉隆坡等地的著名高校授課與宣講，並多次與TopCoder、百度和網易有道等知名企業合作舉辦比賽，讓更多的IT人才獲得展示自我的平台。
陳鋒，1982年9月生。畢業於華北水利水電學院機械設計專業。曾就職於微軟全球技術支持中心，負責net虛擬機以及Visual Studio開發技術支持。後進入金融IT行業，專注於銀行網點平台的產品研發，曾分別負責基於.net和Eclipse的兩代網點平台產品的開發以及架構設計。現就職於北京宇信易誠科技，任前端產品技術經理及架構師。
陳鋒，1982年9月生。畢業於華北水利水電學院機械設計專業。曾就職於微軟全球技術支持中心，負責net虛擬機以及Visual Studio開發技術支持。後進入金融IT行業，專注於銀行網點平台的產品研發，曾分別負責基於.net和Eclipse的兩代網點平台產品的開發以及架構設計。現就職於北京宇信易誠科技，任前端產品技術經理及架構師。
圖書目錄
第1章 算法設計基礎
1.1思維的體操
1.2問題求解常見策略
1.3高效算法設計舉例
1.4動態規劃專題
1.5小結與習題
第2章 數學基礎
2.1基本計數方法
2.2遞推關係
2.3 數論
2.3.1基本概念
2.3.2模方程
2.4組合遊戲
2.5機率與數學期望
2.6置換及其套用
2.7矩陣和線性方程組
2.8數值方法簡介
2.9小結與習題
第3章 實用數據結構
3.1基礎數據結構回顧
3.1.1抽象數據類型（ADT）
3.1.2優先佇列
3.1.3並查集
3.2區間信息的維護與查詢
3.2.1二叉索引樹（樹狀數組）
3.2.2 RMQ問題
3.2.3線段樹（1）：點修改
3.2.4線段樹（2）：區間修改
3.3字元串（1）
3.3.1 Trie
3.3.2 KMP算法
3.3.3 Aho—Corasick自動機
3.4字元串（2）
3.4.1 後綴數組
3.4.2最長公共前綴（LCP）
3.4.3基於哈希值的LCP算法
3.5排序二叉樹
3.5.1基本概念
3.5.2用Treap實現名次樹
3.5.3用伸展樹實現可分裂與合併的序列
3.6小結與習題
第4章 幾何問題
4.1二維幾何基礎
4.1.1基本運算
4.1.2點和直線
4.1.3多邊形
4.1.4例題選講
4.1.5二維幾何小結
4.2與圓和球有關的計算問題
4.2.1 圓的相關計算
4.2.2球面相關問題
4.3二維幾何常用算法
4.3.1點在多邊形內判定
4.3.2凸包
4.3.3半平面交
4.3.4平面區域
4.4三維幾何基礎
4.4.1三維點積
4.4.2三維叉積
4.4.3三維凸包
4.4.4例題選講
4.4.5三維幾何小結
4.5小結與習題
第5章 圖論算法與模型
5.1基礎題目選講
5.2深度優先遍歷
5.2.1 無向圖的割頂和橋
5.2.2無向圖的雙連通分量
5.2.3有向圖的強連通分量
5.2.4 2—SAT問題
5.3最短路問題
5.3.1再談Dijkstra算法
5.3.2再談Bellman—Ford算法
5.3.3例題選講
5.4生成樹相關問題
5.5二分圖匹配
5.5.1二分圖最大匹配
5.5.2二分圖最佳完美匹配
5.5.3穩定婚姻問題
5.5.4常見模型
5.6網路流問題
5.6.1最短增廣路算法
5.6.2最小費用最大流算法
5.6.3建模與模型變換
5.6.4例題選講
5.7小結與習題
第6章 更多算法專題
6.1輪廓線動態規劃
6.2嵌套和分塊數據結構
6.3暴力法專題
6.3.1路徑尋找問題
6.3.2對抗搜尋
6.3.3精確覆蓋問題和DLX算法
6.4幾何專題
6.4.1仿射變換與矩陣
6.4.2離散化和掃描法
6.4.3運動規劃
6.5 數學專題
6.5.1小專題集錦
6.5.2快速傅立葉變換（FFT）
6.5.3線性規劃
6.6淺談代碼設計與靜態查錯
6.6.1簡單的Bash
6.6.2 《仙劍奇俠傳四》之最後的戰役
6.7小結與習題
附錄A訓練指南：使用OVa/LA題庫
A.1 UVa線上比賽推薦
A.2 LA套題（ACM/ICPC真題）推薦
A.3 UVa線上比賽單題推薦
附錄B Java、C#和Python語言簡介
B.1 Java
B.2 C#
B.3 Python
1.1思維的體操
1.2問題求解常見策略
1.3高效算法設計舉例
1.4動態規劃專題
1.5小結與習題
第2章 數學基礎
2.1基本計數方法
2.2遞推關係
2.3 數論
2.3.1基本概念
2.3.2模方程
2.4組合遊戲
2.5機率與數學期望
2.6置換及其套用
2.7矩陣和線性方程組
2.8數值方法簡介
2.9小結與習題
第3章 實用數據結構
3.1基礎數據結構回顧
3.1.1抽象數據類型（ADT）
3.1.2優先佇列
3.1.3並查集
3.2區間信息的維護與查詢
3.2.1二叉索引樹（樹狀數組）
3.2.2 RMQ問題
3.2.3線段樹（1）：點修改
3.2.4線段樹（2）：區間修改
3.3字元串（1）
3.3.1 Trie
3.3.2 KMP算法
3.3.3 Aho—Corasick自動機
3.4字元串（2）
3.4.1 後綴數組
3.4.2最長公共前綴（LCP）
3.4.3基於哈希值的LCP算法
3.5排序二叉樹
3.5.1基本概念
3.5.2用Treap實現名次樹
3.5.3用伸展樹實現可分裂與合併的序列
3.6小結與習題
第4章 幾何問題
4.1二維幾何基礎
4.1.1基本運算
4.1.2點和直線
4.1.3多邊形
4.1.4例題選講
4.1.5二維幾何小結
4.2與圓和球有關的計算問題
4.2.1 圓的相關計算
4.2.2球面相關問題
4.3二維幾何常用算法
4.3.1點在多邊形內判定
4.3.2凸包
4.3.3半平面交
4.3.4平面區域
4.4三維幾何基礎
4.4.1三維點積
4.4.2三維叉積
4.4.3三維凸包
4.4.4例題選講
4.4.5三維幾何小結
4.5小結與習題
第5章 圖論算法與模型
5.1基礎題目選講
5.2深度優先遍歷
5.2.1 無向圖的割頂和橋
5.2.2無向圖的雙連通分量
5.2.3有向圖的強連通分量
5.2.4 2—SAT問題
5.3最短路問題
5.3.1再談Dijkstra算法
5.3.2再談Bellman—Ford算法
5.3.3例題選講
5.4生成樹相關問題
5.5二分圖匹配
5.5.1二分圖最大匹配
5.5.2二分圖最佳完美匹配
5.5.3穩定婚姻問題
5.5.4常見模型
5.6網路流問題
5.6.1最短增廣路算法
5.6.2最小費用最大流算法
5.6.3建模與模型變換
5.6.4例題選講
5.7小結與習題
第6章 更多算法專題
6.1輪廓線動態規劃
6.2嵌套和分塊數據結構
6.3暴力法專題
6.3.1路徑尋找問題
6.3.2對抗搜尋
6.3.3精確覆蓋問題和DLX算法
6.4幾何專題
6.4.1仿射變換與矩陣
6.4.2離散化和掃描法
6.4.3運動規劃
6.5 數學專題
6.5.1小專題集錦
6.5.2快速傅立葉變換（FFT）
6.5.3線性規劃
6.6淺談代碼設計與靜態查錯
6.6.1簡單的Bash
6.6.2 《仙劍奇俠傳四》之最後的戰役
6.7小結與習題
附錄A訓練指南：使用OVa/LA題庫
A.1 UVa線上比賽推薦
A.2 LA套題（ACM/ICPC真題）推薦
A.3 UVa線上比賽單題推薦
附錄B Java、C#和Python語言簡介
B.1 Java
B.2 C#
B.3 Python
