大學(xué)生程序競賽算法基礎(chǔ)教程

第 1章 C/C++簡介 1
第　2章 基礎(chǔ)算法　8
2．1　算法復(fù)雜度　8
2．1．1　時(shí)間復(fù)雜度　8
2．1．2　空間復(fù)雜度　9
2．2　枚舉　9
2．3　遞歸　15
2．4　貪心　20
2．4．1　從局部分析　20
2．4．2　根據(jù)不等式確定貪心策略　22
2．5　二分　24
2．5．1　從有序數(shù)組中查找值　24
2．5．2　“最小值最大化”問題　29
第3章　基礎(chǔ)數(shù)學(xué)　34
3．1　最大公約數(shù)　34
3．2　素?cái)?shù)　36
3．2．1　判斷素?cái)?shù)　36
3．2．2　篩素?cái)?shù)　37
3．3　歐拉函數(shù)　41
3．4　算術(shù)基本定理　48
3．5　快速冪　51
3．5．1　整數(shù)快速冪　52
3．5．2　矩陣快速冪　53
第4章　數(shù)據(jù)結(jié)構(gòu)　56
4．1　棧和隊(duì)列　56
4．2　優(yōu)先隊(duì)列　62
4．3　二叉樹　65
4．4　并查集　68
4．5　樹狀數(shù)組　77
4．6　RMQ　79
4．7　線段樹　82
第5章　動(dòng)態(tài)規(guī)劃　90
5．1　基本動(dòng)態(tài)規(guī)劃　90
5．2　背包　92
5．2．1　01背包　92
5．2．2　完全背包　94
5．3　單調(diào)隊(duì)列　96
5．4　數(shù)位DP　101
5．5　區(qū)間DP　105
5．6　概率DP　108
第6章　圖論　112
6．1　建圖與遍歷　112
6．1．1　鄰接矩陣　113
6．1．2　Vector鄰接表　114
6．1．3　鏈?zhǔn)角跋蛐恰?15
6．2　搜索　116
6．2．1　深度優(yōu)先搜索　116
6．2．2　廣度優(yōu)先搜索　120
6．3　最小生成樹　122
6．3．1　Prim算法　122
6．3．2　Kruskal算法　125
6．4　最短路　129
6．4．1　Floyed算法　130
6．4．2　Dijkstra算法　130
6．5　拓?fù)渑判颉?35
第7章　字符串　140
7．1　KMP　140
7．2　AC自動(dòng)機(jī)　143
參考文獻(xiàn)　149