程序设计竞赛专题挑战教程

目 录

第 1章　蓝桥杯软件类大赛介绍　1

1.1　蓝桥杯软件类大赛的竞赛规则　1

1.2　竞赛题示例　4

1.3　算法知识点总览　5

1.4　历年真题知识点统计　7

1.5　蓝桥杯软件类大赛的评测系统　9

小结　12

第 2章　手算题和杂题　13

2.1　手算题攻略　13

2.1.1　巧用编辑器　13

2.1.2　眼看手数　14

2.1.3　巧用Excel　16

2.1.4　巧用Python　17

2.2　杂题　22

小结　32

第3章　基础数据结构　33

3.1　数组　33

3.2　链表　37

3.2.1　C 链表实现　38

3.2.2　Python链表实现　42

3.3　队列　44

3.3.1　C 普通队列　44

3.3.2　Python普通队列　47

3.3.3　C 优先队列　49

3.3.4　Python优先队列　51

3.4　栈　51

3.4.1　C 栈的实现　52

3.4.2　Python栈的实现　55

3.4.3　例题　57

3.5　二叉树　59

3.5.1　二叉树的定义　60

3.5.2　二叉树的存储　60

3.5.3　二叉树的遍历　61

3.5.4　例题　63

小结　66

第4章　基本算法　67

4.1　算法复杂度　67

4.1.1　算法的概念　67

4.1.2　计算资源　68

4.1.3　选择解题方法　69

4.1.4　算法复杂度概述　71

4.2　排序　73

4.2.1　C 的sort()函数　73

4.2.2　Python的sort()和sorted()函数　74

4.2.3　Java的sort()函数　75

4.2.4　例题　75

4.3　排列和组合　87

4.3.1　C 的全排列函数next_permutation()　88

4.3.2　Python的排列函数permutations()　89

4.3.3　Python的组合函数combinations()　89

4.3.4　手写排列和组合代码　90

4.3.5　例题　92

4.4　尺取法　97

4.4.1　尺取法的概念　97

4.4.2　反向扫描　98

4.4.3　同向扫描　99

4.5　二分法　102

4.5.1　二分法的概念　102

4.5.2　整数二分　103

4.5.3　整数二分例题　104

4.5.4　实数二分　112

4.6　倍增法和ST算法　114

4.6.1　用暴力法解决区间问题　115

4.6.2　ST算法　116

4.6.3　ST算法的模板代码　118

4.7　前缀和　119

4.8　贪心算法　124

小结　132

第5章　搜索　133

5.1　DFS基础　134

5.1.1　递归和记忆化搜索　134

5.1.2　DFS的代码框架　136

5.1.3　DFS的所有路径　137

5.1.4　DFS与排列组合　140

5.1.5　DFS应用详解　143

5.1.6　DFS真题　147

5.2　BFS基础　152

5.2.1　BFS的原理　152

5.2.2　BFS与短路径　154

5.3　连通性判断　158

5.3.1　DFS连通性判断　159

5.3.2　BFS连通性判断　161

5.3.3　连通性例题　163

5.4　BFS与判重　168

5.5　双向广搜　171

5.6　剪枝　174

小结　182

第6章　高级数据结构　183

6.1　并查集　183

6.1.1　用并查集检查连通性　183

6.1.2　并查集的基本操作　185

6.1.3　路径压缩　188

6.1.4　例题　189

6.2　树状数组　197

6.2.1　区间和问题　197

6.2.2　树状数组的原理　199

6.2.3　lowbit()　201

6.2.4　树状数组的代码　202

6.2.5　逆序对问题　203

6.3　线段树　207

6.3.1　线段树的概念　208

6.3.2　区间查询　209

6.3.3　区间查询例题　214

6.3.4　区间修改和懒惰标记　221

小结　226

第7章　动态规划　227

7.1　动态规划的概念　227

7.2　动态规划基础　228

7.3　线性DP　235

7.4　状态压缩DP　247

7.4.1　状态压缩DP的概念　247

7.4.2　状态压缩DP的原理　249

7.4.3　位运算　249

7.4.4　例题　250

7.5　树形DP　255

7.6　数位DP　259

小结　264

第8章　数学　265

8.1　模运算　265

8.2　快速幂　266

8.3　矩阵乘法　271

8.4　矩阵快速幂　273

8.5　GCD和LCM　278

8.5.1　GCD的定义和性质　278

8.5.2　GCD的编程实现　278

8.5.3　LCM　279

8.5.4　例题　280

8.6　素数　286

8.6.1　素数的判断　287

8.6.2　素数的筛选　290

8.6.3　区间素数　294

8.6.4　分解质因子　295

8.7　组合数学　297

8.7.1　基本计数　297

8.7.2　鸽巢原理　301

8.7.3　二项式定理和杨辉三角　302

8.8　几何　304

8.8.1　普通几何题　305

8.8.2　点和向量　306

8.8.3　点积和叉积　307

8.8.4　点和线的关系　310

小结　314

第9章　字符串　316

9.1　字符串函数　316

9.1.1　C 的字符串函数　316

9.1.2　Python的字符串处理　317

9.1.3　Java的字符串函数　318

9.2　简单字符串例题　319

9.3　朴素模式匹配算法　325

9.4　KMP算法　326

9.4.1　模式串P的特征与匹配的关系　327

9.4.2　长公共前后缀和Next[]数组　328

9.4.3　例题　329

小结　335

第 10章　图论　336

10.1　图的基本概念　336

10.2　图的存储　337

10.3　拓扑排序　338

10.4　Floyd算法　342

10.4.1　Floyd算法思想　342

10.4.2　例题　344

10.5　Dijkstra算法　347

10.5.1　Dijkstra算法思想　348

10.5.2　编程实现Dijkstra算法　349

10.5.3　例题　350

10.6　Bellman-Ford算法　352

10.7　SPFA　355

10.7.1　SPFA原理　355

10.7.2　SPFA的模板代码　356

10.8　小生成树　358

10.8.1　Prim算法　358

10.8.2　Kruskal算法　360

小结　363