《算法競賽入門到進階》是2019年清華大學出版社出版的圖書，作者是羅勇軍、郭衛斌。
基本介紹
- 書名：算法競賽入門到進階
- 作者：羅勇軍、郭衛斌
- ISBN：9787302529156
- 定價：59.80元
- 出版社：清華大學出版社
- 出版時間：2019年8月1日
- 印次：1-2
- 印刷日期：2019.07.19
圖書簡介,圖書目錄,
圖書簡介
本書是算法競賽的入門和進階教材，包括算法思路、模板代碼、知識體系、賽事相關等內容。本書把競賽常用的知識點和競賽題結合起來，講解清晰、透徹，幫助初學者建立自信心，快速從實際問題入手，模仿經典代碼解決問題，進入中級學習階段。 全書分為12章，覆蓋了目前算法競賽中的主要內容，包括算法競賽概述、算法複雜度、STL和基本數據結構、搜尋技術、高級數據結構、基礎算法思想、動態規劃、數學、字元串、圖論、計算幾何。 本書適合用於高等院校開展的ICPC、CCPC等算法競賽培訓，中學NOI信息學競賽培訓，以及需要學習算法、提高計算思維的計算機工作者。
圖書目錄
目錄
第1章算法競賽概述
1.1培養傑出程式設計師的捷徑
1.1.1編寫大量代碼
1.1.2豐富的算法知識
1.1.3計算思維和邏輯思維
1.1.4團隊合作精神
1.2算法競賽與創新能力的培養
1.3算法競賽入門
1.3.1競賽語言和訓練平台
1.3.2判題和基本的輸入與輸出
1.3.3測試
1.3.4編碼速度
1.3.5模板
1.3.6題目分類
1.3.7代碼規範
1.4天賦與勤奮
1.5學習建議
1.6本書的特點
第2章算法複雜度
2.1計算的資源
2.2算法的定義
2.3算法的評估
第3章STL和基本數據結構
3.1容器
3.1.1vector
3.1.2棧和stack
3.1.3佇列和queue
3.1.4優先佇列和priority_queue
3.1.5鍊表和list
3.1.6set
3.1.7map
3.2sort()
3.3next_permutation()
第4章搜尋技術
4.1遞歸和排列
4.2子集生成和組合問題
4.3BFS
4.3.1BFS和佇列
4.3.2八數碼問題和狀態圖搜尋
4.3.3BFS與A*算法
4.3.4雙向廣搜
4.4DFS
4.4.1DFS和遞歸
4.4.2回溯與剪枝
4.4.3疊代加深搜尋
4.4.4IDA*
4.5小結
第5章高級數據結構
5.1並查集
5.2二叉樹
5.2.1二叉樹的存儲
5.2.2二叉樹的遍歷
5.2.3二叉搜尋樹
5.2.4Treap樹
5.2.5Splay樹
5.3線段樹
5.3.1線段樹的概念
5.3.2點修改
5.3.3離散化
5.3.4區間修改
5.3.5線段樹習題
5.4樹狀數組
5.5小結
第6章基礎算法思想
6.1貪心法
6.1.1基本概念
6.1.2常見問題
6.1.3Huffman編碼
6.1.4模擬退火
6.1.5習題
6.2分治法
6.2.1歸併排序
6.2.2快速排序
6.3減治法
6.4小結
第7章動態規劃
7.1基礎DP
7.1.1硬幣問題
7.1.20/1背包
7.1.3最長公共子序列
7.1.4最長遞增子序列
7.1.5基礎DP習題
7.2遞推與記憶化搜尋
7.3區間DP
7.4樹形DP
7.5數位DP
7.6狀態壓縮DP
7.7小結
第8章數學
8.1高精度計算
8.2數論
8.2.1模運算
8.2.2快速冪
8.2.3GCD、LCM
8.2.4擴展歐幾里得算法與二元一次方程的整數解
8.2.5同餘與逆元
8.2.6素數
8.3組合數學
8.3.1鴿巢原理
8.3.2楊輝三角和二項式係數
8.3.3容斥原理
8.3.4Fibonacci數列
8.3.5母函式
8.3.6特殊計數
8.4機率和數學期望
8.5公平組合遊戲
8.5.1巴什遊戲與Pposition、Nposition
8.5.2尼姆遊戲
8.5.3圖遊戲與SpragueGrundy函式
8.5.4威佐夫遊戲
8.6小結
第9章字元串
9.1字元串的基本操作
9.2字元串哈希
9.3字典樹
9.4KMP
9.5AC自動機
9.6後綴樹和後綴數組
9.6.1概念
9.6.2用倍增法求後綴數組
9.6.3用後綴數組解決經典問題
9.7小結
第10章圖論
10.1圖的基本概念
10.2圖的存儲
10.3圖的遍歷和連通性
10.4拓撲排序
10.5歐拉路
10.6無向圖的連通性
10.6.1割點和割邊
10.6.2雙連通分量
10.7有向圖的連通性
10.7.1Kosaraju算法
10.7.2Tarjan算法
10.82SAT問題
10.9最短路
10.9.1FloydWarshall
10.9.2BellmanFord
10.9.3SPFA
10.9.4Dijkstra
10.10最小生成樹
10.10.1prim算法
10.10.2kruskal算法
10.11最大流
10.11.1FordFulkerson方法
10.11.2EdmondsKarp算法
10.11.3Dinic算法和ISAP算法
10.12最小割
10.13最小費用最大流
10.14二分圖匹配
10.15小結
第11章計算幾何
11.1二維幾何基礎
11.1.1點和向量
11.1.2點積和叉積
11.1.3點和線
11.1.4多邊形
11.1.5凸包
11.1.6最近點對
11.1.7旋轉卡殼
11.1.8半平面交
11.2圓
11.2.1基本計算
11.2.2最小圓覆蓋
11.3三維幾何
11.3.1三維點和向量
11.3.2三維點積
11.3.3三維叉積
11.3.4最小球覆蓋
11.3.5三維凸包
11.4幾何模板
11.5小結
第12章ICPC區域賽真題
12.1ICPC亞洲區域賽(中國大陸)情況
12.2ICPC區域賽題目解析
12.2.1F題FriendshipofFrog(hdu5578)
12.2.2K題KingdomofBlackandWhite(hdu5583)
12.2.3L題LCMWalk(hdu5584)
12.2.4A題AnEasyPhysicsProblem(hdu5572)
12.2.5B題BinaryTree(hdu5573)
12.2.6D題DiscoverWaterTank(hdu5575)
12.2.7E題ExpectionofString(hdu5576)
12.2.8G題GameofArrays(hdu5579)
12.2.9I題InfinityPointSets(hdu5581)
參考文獻
第1章算法競賽概述
1.1培養傑出程式設計師的捷徑
1.1.1編寫大量代碼
1.1.2豐富的算法知識
1.1.3計算思維和邏輯思維
1.1.4團隊合作精神
1.2算法競賽與創新能力的培養
1.3算法競賽入門
1.3.1競賽語言和訓練平台
1.3.2判題和基本的輸入與輸出
1.3.3測試
1.3.4編碼速度
1.3.5模板
1.3.6題目分類
1.3.7代碼規範
1.4天賦與勤奮
1.5學習建議
1.6本書的特點
第2章算法複雜度
2.1計算的資源
2.2算法的定義
2.3算法的評估
第3章STL和基本數據結構
3.1容器
3.1.1vector
3.1.2棧和stack
3.1.3佇列和queue
3.1.4優先佇列和priority_queue
3.1.5鍊表和list
3.1.6set
3.1.7map
3.2sort()
3.3next_permutation()
第4章搜尋技術
4.1遞歸和排列
4.2子集生成和組合問題
4.3BFS
4.3.1BFS和佇列
4.3.2八數碼問題和狀態圖搜尋
4.3.3BFS與A*算法
4.3.4雙向廣搜
4.4DFS
4.4.1DFS和遞歸
4.4.2回溯與剪枝
4.4.3疊代加深搜尋
4.4.4IDA*
4.5小結
第5章高級數據結構
5.1並查集
5.2二叉樹
5.2.1二叉樹的存儲
5.2.2二叉樹的遍歷
5.2.3二叉搜尋樹
5.2.4Treap樹
5.2.5Splay樹
5.3線段樹
5.3.1線段樹的概念
5.3.2點修改
5.3.3離散化
5.3.4區間修改
5.3.5線段樹習題
5.4樹狀數組
5.5小結
第6章基礎算法思想
6.1貪心法
6.1.1基本概念
6.1.2常見問題
6.1.3Huffman編碼
6.1.4模擬退火
6.1.5習題
6.2分治法
6.2.1歸併排序
6.2.2快速排序
6.3減治法
6.4小結
第7章動態規劃
7.1基礎DP
7.1.1硬幣問題
7.1.20/1背包
7.1.3最長公共子序列
7.1.4最長遞增子序列
7.1.5基礎DP習題
7.2遞推與記憶化搜尋
7.3區間DP
7.4樹形DP
7.5數位DP
7.6狀態壓縮DP
7.7小結
第8章數學
8.1高精度計算
8.2數論
8.2.1模運算
8.2.2快速冪
8.2.3GCD、LCM
8.2.4擴展歐幾里得算法與二元一次方程的整數解
8.2.5同餘與逆元
8.2.6素數
8.3組合數學
8.3.1鴿巢原理
8.3.2楊輝三角和二項式係數
8.3.3容斥原理
8.3.4Fibonacci數列
8.3.5母函式
8.3.6特殊計數
8.4機率和數學期望
8.5公平組合遊戲
8.5.1巴什遊戲與Pposition、Nposition
8.5.2尼姆遊戲
8.5.3圖遊戲與SpragueGrundy函式
8.5.4威佐夫遊戲
8.6小結
第9章字元串
9.1字元串的基本操作
9.2字元串哈希
9.3字典樹
9.4KMP
9.5AC自動機
9.6後綴樹和後綴數組
9.6.1概念
9.6.2用倍增法求後綴數組
9.6.3用後綴數組解決經典問題
9.7小結
第10章圖論
10.1圖的基本概念
10.2圖的存儲
10.3圖的遍歷和連通性
10.4拓撲排序
10.5歐拉路
10.6無向圖的連通性
10.6.1割點和割邊
10.6.2雙連通分量
10.7有向圖的連通性
10.7.1Kosaraju算法
10.7.2Tarjan算法
10.82SAT問題
10.9最短路
10.9.1FloydWarshall
10.9.2BellmanFord
10.9.3SPFA
10.9.4Dijkstra
10.10最小生成樹
10.10.1prim算法
10.10.2kruskal算法
10.11最大流
10.11.1FordFulkerson方法
10.11.2EdmondsKarp算法
10.11.3Dinic算法和ISAP算法
10.12最小割
10.13最小費用最大流
10.14二分圖匹配
10.15小結
第11章計算幾何
11.1二維幾何基礎
11.1.1點和向量
11.1.2點積和叉積
11.1.3點和線
11.1.4多邊形
11.1.5凸包
11.1.6最近點對
11.1.7旋轉卡殼
11.1.8半平面交
11.2圓
11.2.1基本計算
11.2.2最小圓覆蓋
11.3三維幾何
11.3.1三維點和向量
11.3.2三維點積
11.3.3三維叉積
11.3.4最小球覆蓋
11.3.5三維凸包
11.4幾何模板
11.5小結
第12章ICPC區域賽真題
12.1ICPC亞洲區域賽(中國大陸)情況
12.2ICPC區域賽題目解析
12.2.1F題FriendshipofFrog(hdu5578)
12.2.2K題KingdomofBlackandWhite(hdu5583)
12.2.3L題LCMWalk(hdu5584)
12.2.4A題AnEasyPhysicsProblem(hdu5572)
12.2.5B題BinaryTree(hdu5573)
12.2.6D題DiscoverWaterTank(hdu5575)
12.2.7E題ExpectionofString(hdu5576)
12.2.8G題GameofArrays(hdu5579)
12.2.9I題InfinityPointSets(hdu5581)
參考文獻
