信息学算法进阶实例精讲 pdf下载

本书是在算法入门的基础上,进一步夯实基础算法并加以提升的算法精讲教程,注重知识剖析,将知识与算法实例分析有机结合;注重思维方法和代码实现能力的培养。全书包 括:算法基础、字符串、数据结构、图论、动态规划、数学知识共六章。本书通过对例题进行深入剖析,提炼算法精髓和解决问题的思想方法。本书内容精练、代码简洁易懂,适合作为算法爱好者用于夯实算法基础,提升代码实现能力,也适 合中小学信息学社团的教师用作算法精讲教程,还适合备战信息学竞赛、ACM 比赛的读者用作学习教程。

本书编委会作者团队阵容实力强大，作者均为北京市教学名师，全国信息学竞赛金牌教练组成，团队实力强大，并且长期处于信息学教学一线，教学实践经验丰富，并且在近两年辅导的学生在全国信息学各项比赛中成绩名列前茅

目录

第一章 算法基础 …………………………………………………………………………… 1

第一节 高精度运算 ……………………………………………………………………… 1

第二节 查找算法 ………………………………………………………………………… 7

第三节 排序算法 ………………………………………………………………………… 11

第四节 前缀和与差分 …………………………………………………………………… 20

第五节 快速幂 …………………………………………………………………………… 30

第六节 搜索 ……………………………………………………………………………… 33

第二章 字符串 ……………………………………………………………………………… 52

第一节 字符串哈希 ……………………………………………………………………… 52

第二节 KMP算法 ……………………………………………………………………… 61

第三节 Manacher算法 ………………………………………………………………… 68

第四节 Trie树…………………………………………………………………………… 72

第五节 AC自动机算法 ………………………………………………………………… 79

第三章 数据结构 …………………………………………………………………………… 86

第一节 堆 ………………………………………………………………………………… 86

第二节 优先队列 ………………………………………………………………………… 92

第三节 单调队列 ………………………………………………………………………… 96

第四节 单调栈 ………………………………………………………………………… 103

第五节 ST表 …………………………………………………………………………… 107

第六节 树状数组 ……………………………………………………………………… 109

第七节 线段树 ………………………………………………………………………… 117

第八节 并查集 ………………………………………………………………………… 130

第九节 二叉排序树 …………………………………………………………………… 144

第十节 平衡树 ………………………………………………………………………… 150

第四章 图论………………………………………………………………………………… 187

第一节 图论基础 ……………………………………………………………………… 187

第二节 最短路算法 …………………………………………………………………… 200

第三节 拓扑排序 ……………………………………………………………………… 218

第四节 最小生成树 …………………………………………………………………… 227

第五章 动态规划 ………………………………………………………………………… 243

第一节 递推与动态规划 ……………………………………………………………… 243

第二节 背包专题 ……………………………………………………………………… 250

第三节 区间DP ……………………………………………………………………… 261

第四节 树形DP ……………………………………………………………………… 266

第五节 数位DP ……………………………………………………………………… 275

第六节 状压DP ……………………………………………………………………… 282

第六章 数学………………………………………………………………………………… 290

第一节 组合数学 ……………………………………………………………………… 290

第二节 概率 …………………………………………………………………………… 295

第三节 初等数论 ……………………………………………………………………… 302

第四节 矩阵的相关知识 ……………………………………………………………… 317

参考文献 ……………………………………………………………………………………… 325

随着以计算机技术为基础的现代信息技术逐步深入社会生活的方方面面,利用计算机程序解决问题对现代科技发展的推动作用日益突显。计算机核心技术对我国科技发展十分重要,特别是近年来科技领域国际分工出现的新情况,让我们感受到必须在关键领域下功夫,并且要实现整体科技水平从跟跑向并跑、领跑的战略性转变。要实现这一转变,就需要从基础学科、基础教育抓起。

学习算法是进入信息技术核心领域的关键一步,也是深入应用计算机的重要途径。由于算法学习难度较大,而且需要先精通编程语言,因此,本书是向已经掌握了C++程序设计语言,并且具备一定编程能力和简单算法应用能力的读者,重点介绍计算机应用的经典算法的相关知识。本书各章首先介绍相关知识点,再通过对经典例题的剖析和算法核心思想的提炼,辅以清晰的代码,让看起来复杂的知识点得到自然展现。

本书是信息学名师工作室教师集体智慧的结晶,凝聚了多位教师的心血。本书由北京大学信息科学技术学院副教授蒋婷婷,北京航空航天大学计算机学院教授、博士生导师尹宝林,清华大学计算机科学与技术系副教授王宏,北京航空航天大学计算机学院硕士生导师赵启阳,清华大学计算机科学与技术系助理研究员韩文弢担任顾问;首都师范大学附属中学杨森林,北京市第八十中学贾志勇,中国人民大学附属中学叶金毅,北京师范大学附属实验中学胡伟栋担任主编。具体编写分工如下。第一章由贾志勇负责编写;第二章由叶金毅负责编写;第三章由中国人民大学附属中学佟松龄、谷多玉、李战元负责编写;第四章由首都师范大学附属中学高一轩负责编写;第五章由首都师范大学附属中学杨森林负责编写;第六章由北京师范大学附属实验中学胡伟栋、张康负责编写。全书由杨森林统稿,贾志勇、叶金毅和胡伟栋负责校正,高一轩、谷多玉、佟松龄、李战元、张康和北京科学中心张军、张珊负责本书课件以及相关教学资源制作。

信息学名师工作室于2021年编写并出版了《信息学竞赛入门篇》,带领读者学习了C++程序设计语言的基本知识,初步学习了数据结构的基本知识以及入门算法,是信息学名师工作室开展编程科普活动的一个阶段总结。本书是在此基础上,带领读者进一步拓展高级数据结构和高级算法应用的知识和方法,是信息学名师工作室编程科普活动另一个阶段的提炼和总结,希望能够为读者的算法水平进阶提供帮助。

由于编者水平有限,难免有不足之处,敬请各位同行和广大读者批评、指正。

编 者

2022年3月