大学生程序竞赛算法基础教程

- 一线竞赛带队老师多年经验总结，贴近实战。
本书主编谈文蓉老师在高校长期从事算法类的竞赛培训工作，其他几位作者也都有15年以上的算法类竞赛培训经验，且指导学生多次获得ACM靠前大学生程序竞赛银奖，教学经验和实践经验丰富。本书内容来自作者十余年带队参加ACM靠前大学生程序竞赛积累下来的讲义资料，贴近实战。
- 注重理论与实践的结合。
书中包含大量实例及解题思路、便于读者快速入门、学以致用。
- 内容编排力求循序渐进、由浅入深，以保证教材的易用性和可读性

本书共7章，内容包括枚举、递归、贪心、二分、动态规划、图论和字符串等大学生程序竞赛中的基本算法。
本书注重理论与实践相结合，书中提供的程序样例较多，以便学生学以致用；内容编排力求循序渐进、由浅入深，以保证教材的易用性和可读性。
本书可作为高等院校理工类相关专业的基础算法类课程教材，也可作为大学生程序竞赛中基础算法的培训教材，也可供对程序设计和算法感兴趣的普通读者学习参考。

谈文蓉
四川省计算机学会副理事长，四川省计算机科学与技术专业教学指导委员会委员。长期从事计算机科学理论与应用技术的教学科研工作。先后主持主研国家社科基金、四川省科技计划等省部级及以上科研项目20余项，发表学术论文50余篇，获国家发明2项，软件著作权1项。主持教育部新工科研究与实践项目1项、四川省教学工程项目3项、省部级教改项目3项，指导学生获各级各类创新奖励30余项， 获得四川省高等教育教学成果一等奖1项、三等奖1项。

第 1章 C/C++简介 1
第  2章 基础算法  8
2.1  算法复杂度  8
2.1.1  时间复杂度  8
2.1.2  空间复杂度  9
2.2  枚举  9
2.3  递归  15
2.4  贪心  20
2.4.1  从局部分析  20
2.4.2  根据不等式确定贪心策略  22
2.5  二分  24
2.5.1  从有序数组中查找值  24
2.5.2  “最小值优选化”问题  29
第3章  基础数学  34
3.1  优选公约数  34
3.2  素数  36
3.2.1  判断素数  36
3.2.2  筛素数  37
3.3  欧拉函数  41
3.4  算术基本定理  48
3.5  快速幂  51
3.5.1  整数快速幂  52
3.5.2  矩阵快速幂  53
第4章  数据结构  56
4.1  栈和队列  56
4.2  优先队列  62
4.3  二叉树  65
4.4  并查集  68
4.5  树状数组  77
4.6  RMQ  79
4.7  线段树  82
第5章  动态规划  90
5.1  基本动态规划  90
5.2  背包  92
5.2.1  01背包  92
5.2.2  完全背包  94
5.3  单调队列  96
5.4  数位DP  101
5.5  区间DP  105
5.6  概率DP  108
第6章  图论  112
6.1  建图与遍历  112
6.1.1  邻接矩阵  113
6.1.2  Vector邻接表  114
6.1.3  链式前向星  115
6.2  搜索  116
6.2.1  深度优先搜索  116
6.2.2  广度优先搜索  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  拓扑排序  135
第7章  字符串  140
7.1  KMP  140
7.2  AC自动机  143
参考文献  149