算法競賽入門到進階

第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巴什遊戲與Pposition、Nposition
 
8.5.2尼姆遊戲
 
8.5.3圖遊戲與SpragueGrundy函數
 
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.82SAT問題
 
10.9最短路
 
10.9.1FloydWarshall
 
10.9.2BellmanFord
 
10.9.3SPFA
 
10.9.4Dijkstra
 
10.10最小生成樹
 
10.10.1prim演算法
 
10.10.2kruskal演算法
 
10.11最大流
 
10.11.1FordFulkerson方法
 
10.11.2EdmondsKarp演算法
 
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題Friendship of Frog(hdu 5578)
 
12.2.2K題Kingdom of Black and White(hdu 5583)
 
12.2.3L題LCM Walk(hdu 5584)
 
12.2.4A題An Easy Physics Problem(hdu 5572)
 
12.2.5B題Binary Tree(hdu 5573)
 
12.2.6D題Discover Water Tank(hdu 5575)
 
12.2.7E題Expection of String(hdu 5576)
 
12.2.8G題Game of Arrays(hdu 5579)
 
12.2.9I題Infinity Point Sets(hdu 5581)
 
參考文獻