信息学奥赛 智码开门一点通 提高篇

本书针对以在规定时间内、快速准确地解决尽可能多的题目为目的的程序设计竞赛，以CCF推出的CSP-J中要求的知识为内容范围，即从零基础的C++语言介绍开始，包含三大控制结构、多重循环、递归、基础数据结构、动态规划和C++自带的STL库，对算法及其在相关问题中的应用，按照难易程度及其相互的关系，从易到难划分为多个主题进行介绍并进行技巧讲解。本书对每个主题由算法介绍和例题讲解两部分组成，书中的源代码均采用C++实现。本书适合所有对编程计算法有兴趣的初学者。

符水波，镇海中学副校长，浙江省特级教师，信息学国际金牌教练，教育部师范专业认证专家；培养了200多名信奥获奖选手，3人获得国际金牌；主编新课程改革计算机专业教材《多媒体技术应用基础》等。应平安，毕

第1章离线算法
1.1莫队算法
1.1.1莫队算法的定义
1.1.2莫队问题求解
1.1.3例题选讲
1.2CDQ分治
1.2.1CDQ分治的定义
1.2.2例题选讲
第2章动态规划进阶
2.1数位动态规划算法
2.1.1数位动态规划算法的概念
2.1.2数位动态规划算法的基本思想
2.1.3例题选讲
2.2其他动态规划算法
2.2.1例题选讲
2.3树形动态规划
2.3.1树形动态规划的概念
2.3.2例题选讲
2.4状态压缩动态规划
2.4.1状态压缩的定义
2.4.2状态压缩结合动态规划的策略1
2.4.3状态压缩结合动态规划的策略2
2.4.4例题实战
2.4.5状态压缩动态规划小结
2.5插头动态规划
2.5.1插头动态规划概述
2.5.2例题选讲
2.6动态规划优化
2.6.1斜率优化
2.6.2四边形不等式优化
2.6.3例题选讲
2.6.4小结
第3章进阶图论
3.1差分约束系统
3.1.1差分约束的定义
3.1.2差分约束问题的求解
3.1.3例题选讲
3.1.4小结
3.2Tarjan四部曲
3.2.1强连通分量
3.2.2双连通分量
3.2.3割点和桥
3.2.4圆方树
3.2.4小结
第4章匹配算法
4.1二分图匹配
4.1.1二分图的概念
4.1.2二分图优选匹配
4.1.3例题选讲
4.1.4其他相关概念
第5章高级数据结构
5.1树状数组、线段树
5.1.1树状数组
5.1.2线段树
5.1.3树状数组、线段树小结
5.2网络流
5.2.1优选流问题
5.2.2最小割问题
5.2.3费用流
5.2.4小结
5.3可持久化数据结构
5.3.1可持久化数据结构
5.3.2可持久化权值线段树
5.3.3例题选讲
5.3.4小结
5.4ST表
5.4.1ST表是什么？
5.4.2例题选讲
5.5Splay树和LCT
5.5.1Splay树的定义及操作
5.5.2LCT的定义及操作
5.5.3例题选讲
5.6树链剖分
5.6.1重链剖分
5.6.2长链剖分
5.6.3例题讲解
5.6.4小结
第6章组合与期望
6.1乘法逆元和快速傅里叶变换(FFT)
6.1.1乘法逆元定义
6.1.2乘法逆元求法
6.1.3快速傅里叶变换
6.1.4例题选讲
6.2概率动态规划
6.2.1概率、期望的性质
6.2.2概率动态规划的做法
第7章字符串进阶
7.1字典树
7.1.1插入操作
7.1.2查询操作
7.1.3字典树的功能
7.1.4例题选讲
7.2KMP算法
7.2.1KMP算法的定义
7.2.2KMP算法的实现
7.2.3例题选讲
7.3AC自动机
7.3.1多模式串的字符串匹配问题
7.3.2构造AC自动机
7.3.3例题选讲
7.3.4小结
7.4后缀数组
7.4.1后缀数组的定义及求法
7.4.2后缀数组的应用
7.4.3例题选讲
7.4.4小结