算法競賽入門到進階

目錄

第1章算法競賽概述

1.1培養(yǎng)杰出程序員的捷徑

1.1.1編寫大量代碼

1.1.2豐富的算法知識

1.1.3計算思維和邏輯思維

1.1.4團隊合作精神

1.2算法競賽與創(chuàng)新能力的培養(yǎng)

1.3算法競賽入門

1.3.1競賽語言和訓(xùn)練平臺

1.3.2判題和基本的輸入與輸出

1.3.3測試

1.3.4編碼速度

1.3.5模板

1.3.6題目分類

1.3.7代碼規(guī)范

1.4天賦與勤奮

1.5學(xué)習(xí)建議

1.6本書的特點

第2章算法復(fù)雜度

2.1計算的資源

2.2算法的定義

2.3算法的評估

第3章STL和基本數(shù)據(jù)結(jié)構(gòu)

3.1容器

3.1.1vector

3.1.2棧和stack

3.1.3隊列和queue

3.1.4優(yōu)先隊列和priority_queue

3.1.5鏈表和list

3.1.6set

3.1.7map

3.2sort()

3.3next_permutation()

第4章搜索技術(shù)

4.1遞歸和排列

4.2子集生成和組合問題

4.3BFS

4.3.1BFS和隊列

4.3.2八數(shù)碼問題和狀態(tài)圖搜索

4.3.3BFS與A*算法

4.3.4雙向廣搜

4.4DFS

4.4.1DFS和遞歸

4.4.2回溯與剪枝

4.4.3迭代加深搜索

4.4.4IDA*

4.5小結(jié)

第5章高級數(shù)據(jù)結(jié)構(gòu)

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區(qū)間修改

5.3.5線段樹習(xí)題

5.4樹狀數(shù)組

5.5小結(jié)

第6章基礎(chǔ)算法思想

6.1貪心法

6.1.1基本概念

6.1.2常見問題

6.1.3Huffman編碼

6.1.4模擬退火

6.1.5習(xí)題

6.2分治法

6.2.1歸并排序

6.2.2快速排序

6.3減治法

6.4小結(jié)

第7章動態(tài)規(guī)劃

7.1基礎(chǔ)DP

7.1.1硬幣問題

7.1.20/1背包

7.1.3最長公共子序列

7.1.4最長遞增子序列

7.1.5基礎(chǔ)DP習(xí)題

7.2遞推與記憶化搜索

7.3區(qū)間DP

7.4樹形DP

7.5數(shù)位DP

7.6狀態(tài)壓縮DP

7.7小結(jié)

第8章數(shù)學(xué)

8.1高精度計算

8.2數(shù)論

8.2.1模運算

8.2.2快速冪

8.2.3GCD、LCM

8.2.4擴展歐幾里得算法與二元一次方程的整數(shù)解

8.2.5同余與逆元

8.2.6素數(shù)

8.3組合數(shù)學(xué)

8.3.1鴿巢原理

8.3.2楊輝三角和二項式系數(shù)

8.3.3容斥原理

8.3.4Fibonacci數(shù)列

8.3.5母函數(shù)

8.3.6特殊計數(shù)

8.4概率和數(shù)學(xué)期望

8.5公平組合游戲

8.5.1巴什游戲與Pposition、Nposition

8.5.2尼姆游戲

8.5.3圖游戲與SpragueGrundy函數(shù)

8.5.4威佐夫游戲

8.6小結(jié)

第9章字符串

9.1字符串的基本操作

9.2字符串哈希

9.3字典樹

9.4KMP

9.5AC自動機

9.6后綴樹和后綴數(shù)組

9.6.1概念

9.6.2用倍增法求后綴數(shù)組

9.6.3用后綴數(shù)組解決經(jīng)典問題

9.7小結(jié)

第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小結(jié)

第11章計算幾何

11.1二維幾何基礎(chǔ)

11.1.1點和向量

11.1.2點積和叉積

11.1.3點和線

11.1.4多邊形

11.1.5凸包

11.1.6最近點對

11.1.7旋轉(zhuǎn)卡殼

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小結(jié)

第12章ICPC區(qū)域賽真題

12.1ICPC亞洲區(qū)域賽(中國大陸)情況

12.2ICPC區(qū)域賽題目解析

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)

參考文獻