注册 登录 进入教材巡展
#

出版时间:2024-09-30

出版社:高等教育出版社

以下为《深入浅出程序设计竞赛(进阶篇)》的配套数字资源,这些资源在您购买图书后将免费附送给您:
  • 高等教育出版社
  • 9787040624007
  • 1
  • 529202
  • 平装
  • 16开
  • 2024-09-30
  • 760
  • 452
内容简介

本书分为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 实践出真知