顶部
收藏

深入浅出程序设计竞赛(进阶篇)


作者:
汪楚奇
定价:
79.50 元
版面字数:
760.00千字
开本:
16开
装帧形式:
平装
页数:
452
最新
印次时间:
2026年07月
ISBN:
978-7-04-062400-7
物料号:
62400-00
出版时间:
2024-09-30
读者对象:
高等职业教育
一级分类:
计算机大类
二级分类:
计算机类
三级分类:
软件技术

本书分为5部分:第1部分介绍一些进阶技巧与思想,包括单调性优化、前缀、差分、离散化、分治、倍增、搜索剪枝等策略;第2部分介绍进阶数据结构,包括二叉堆、线段树、树状数组和字典树;第3部分介绍图论算法,包括树的性质、图的最短路和生成树,以及连通性问题;第4部分介绍动态规划,从动态规划的概念开始,逐渐深入,介绍线性、区间、树与图、状态压缩等不同形式的动态规划,最后介绍动态规划的优化策略;第5部分介绍算法竞赛中需要用到的数学知识,包括数论、组合数学与计数原理、概率与统计和基本线性代数;最后在附录中提供调试与对拍、命令行与脚本以及常数优化技巧的相关内容。

本书主要面向具有一定基础的程序设计竞赛(包括NOI系列比赛、ICPC系列比赛)选手,也适用于希望深入了解算法和数据结构的读者。

本书配套有课件、勘误表等教辅资源,读者可以发邮件至编辑邮箱1548103297@qq.com或者在洛谷讨论区中获取。

  • 目录
    • 前辅文
      • 第1部分 进阶技巧与思想
        • 第1章 常见优化技巧
          • 1.1 双指针法
            • 1.2 空间换时间
              • 1.3 单调栈
                • 1.4 单调队列
                  • 1.5 课后习题与实验
                  • 第2章 前缀和、差分与离散化
                    • 2.1 前缀和与二维前缀和
                      • 2.2 差分
                        • 2.3 离散化
                          • 2.4 课后习题与实验
                          • 第3章 分治与倍增
                            • 3.1 归并排序与快速幂
                              • 3.2 其他序列上的分治
                                • 3.3 倍增与ST表
                                  • 3.4 课后习题与实验
                                  • 第4章 进阶搜索
                                    • 4.1 状态剪枝
                                      • 4.2 迭代加深与双向搜索
                                        • 4.3 启发式搜索
                                          • 4.4 课后习题与实验
                                        • 第2部分 进阶数据结构
                                          • 第5章 二叉堆与树状数组
                                            • 5.1 二叉堆的实现
                                              • 5.2 优先队列
                                                • 5.3 树状数组
                                                  • 5.4 课后习题与实验
                                                  • 第6章 线段树
                                                    • 6.1 线段树的建立与操作
                                                      • 6.2 线段树的应用
                                                        • 6.3 权值线段树(选读)
                                                          • 6.4 课后习题与实验
                                                          • 第7章 字符串
                                                            • 7.1 KMP算法
                                                              • 7.2 字典树
                                                                • 7.3 课后习题与实验
                                                                • 第8章 线段树的进阶用法
                                                                  • 8.1 可持久化线段树
                                                                    • 8.2 树状数组套权值线段树
                                                                      • 8.3 课后习题与实验
                                                                    • 第3部分 图论
                                                                      • 第9章 树
                                                                        • 9.1 树的性质与遍历
                                                                          • 9.2 树的直径与重心
                                                                            • 9.3 最近公共祖先
                                                                              • 9.4 树的重链剖分
                                                                                • 9.5 课后习题与实验
                                                                                • 第10章 最短路
                                                                                  • 10.1 单源最短路径
                                                                                    • 10.2 负环与差分约束
                                                                                      • 10.3 次短路
                                                                                        • 10.4 多源最短路径与传递闭包
                                                                                          • 10.5 课后习题与实验
                                                                                          • 第11章 最小生成树
                                                                                            • 11.1 最小生成树及其应用
                                                                                              • 11.2 次小生成树(选读)
                                                                                                • 11.3 课后习题与实验
                                                                                                • 第12章 连通性问题
                                                                                                  • 12.1 无向图的边双连通性
                                                                                                    • 12.2 无向图的点双连通性
                                                                                                      • 12.3 有向图的强连通性
                                                                                                        • 12.4 课后习题与实验
                                                                                                      • 第4部分 动态规划
                                                                                                        • 第13章 动态规划的引入
                                                                                                          • 13.1 动态规划
                                                                                                            • 13.2 状态、转移与有向无环图
                                                                                                              • 13.3 拓扑排序与记忆化搜索
                                                                                                                • 13.4 动态规划的解法
                                                                                                                  • 13.5 课后习题与实验
                                                                                                                  • 第14章 线性状态动态规划
                                                                                                                    • 14.1 单序列问题
                                                                                                                      • 14.2 多序列问题
                                                                                                                        • 14.3 高维问题
                                                                                                                          • 14.4 课后习题与实验
                                                                                                                          • 第15章 区间与环形动态规划
                                                                                                                            • 15.1 区间动态规划
                                                                                                                              • 15.2 环形动态规划
                                                                                                                                • 15.3 课后习题与实验
                                                                                                                                • 第16章 树与图上的动态规划
                                                                                                                                  • 16.1 树上动态规划
                                                                                                                                    • 16.2 图上动态规划
                                                                                                                                      • 16.3 课后习题与实验
                                                                                                                                      • 第17章 状态压缩动态规划
                                                                                                                                        • 17.1 状态压缩
                                                                                                                                          • 17.2 状态压缩的一般技巧
                                                                                                                                            • 17.3 状态压缩与其他算法的交叉应用
                                                                                                                                              • 17.4 课后习题与实验
                                                                                                                                              • 第18章 动态规划的设计与优化
                                                                                                                                                • 18.1 设计动态规划
                                                                                                                                                  • 18.2 优化转移
                                                                                                                                                    • 18.3 课后习题与实验
                                                                                                                                                  • 第5部分 数学专题选讲
                                                                                                                                                    • 第19章 进阶数论
                                                                                                                                                      • 19.1 模意义下的数和运算
                                                                                                                                                        • 19.2 乘法逆元
                                                                                                                                                          • 19.3 同余方程与中国剩余定理
                                                                                                                                                            • 19.4 线性筛与积性函数(选读)
                                                                                                                                                              • 19.5 欧拉函数(选读)
                                                                                                                                                                • 19.6 课后习题与实验
                                                                                                                                                                • 第20章 组合数学与计数
                                                                                                                                                                  • 20.1 集合与容斥原理
                                                                                                                                                                    • 20.2 常见的组合计数方法
                                                                                                                                                                      • 20.3 二项式定理
                                                                                                                                                                        • 20.4 卡特兰数与斯特林数
                                                                                                                                                                          • 20.5 课后习题与实验
                                                                                                                                                                          • 第21章 概率与统计
                                                                                                                                                                            • 21.1 事件
                                                                                                                                                                              • 21.2 概率模型
                                                                                                                                                                                • 21.3 数学期望
                                                                                                                                                                                  • 21.4 课后习题与实验
                                                                                                                                                                                  • 第22章 基础线性代数
                                                                                                                                                                                    • 22.1 向量与矩阵变换
                                                                                                                                                                                      • 22.2 高斯消元
                                                                                                                                                                                        • 22.3 课后习题与实验
                                                                                                                                                                                      • 附录
                                                                                                                                                                                        • 附录A 调试与对拍
                                                                                                                                                                                          • A.1 IDE调试
                                                                                                                                                                                            • A.2 输出中间变量调试
                                                                                                                                                                                              • A.3 GDB调试
                                                                                                                                                                                                • A.4 对拍
                                                                                                                                                                                                  • A.5 使用Python制造测试数据
                                                                                                                                                                                                  • 附录B 命令行与脚本
                                                                                                                                                                                                    • B.1 命令行的使用
                                                                                                                                                                                                      • B.2 使用命令行完成算法竞赛题目
                                                                                                                                                                                                      • 附录C 常数优化技巧
                                                                                                                                                                                                        • C.1 读写优化
                                                                                                                                                                                                          • C.2 缓存优化
                                                                                                                                                                                                            • C.3 编译优化
                                                                                                                                                                                                              • C.4 算法常数优化
                                                                                                                                                                                                                • C.5 实践出真知

                                                                                                                                                                                                            相关图书