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

由 syzhaoss 在 2026-03-24 创建开放分组：全部用户上次编辑时间：2026-06-19

第1部分进阶技巧与思想

第 1 章常见优化技巧

1.1 双指针法

A-B数对

逛画展

最大字段和

1.2 空间换时间

1.3 单调栈

糟糕的一天

1.4 单调队列

理想的正方形

1.4 课后习题与实验

唯一的雪花

稳赚不赔

钻石收藏家

贴海报

平衡的队列

小琪的格子

第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 课后习题与实验

忠诚数

STEP

三元上升子序列

煮酒

Points

第7章字符串

7.1 KMP算法

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 课后习题与练习

最短路计数

买药水

通行费

小K的农场

传送门

电梯

灾后重建

第11章最小生成树

11.1 最小生成树及其应用

最小生成树

买礼物

构造树

11.2 次小生成树(选读)

严格次小生成树

11.3 课后习题与实验

营救

口袋的天空

灌溉

逐个击破

电网

免费道路

能量树

第12章连通性问题

12.1 无向图的边双连通性

12.2 无向图的点双连通性

12.3 有向图的强连通性

12.4 课后习题与实验

第4部分动态规划

第13章动态规划的引入

13.1 动态规划

纸币问题1

数字三角形

13.2 状态、转移与又向无环图

纸币问题2

纸币问题3

13.3 拓扑排序与记忆化搜索

食物链总数

13.4 动态规划的解法

最大子段和

整数划分

13.5 课后习题与实验

打怪、吃药、获得经验

疯狂的采药

小A点菜

线段

金明的预算方案

小k考前临时抱佛脚

第14章线性状态动态规划

14.1 单序列问题

大师赛

14.2 多序列问题

最长公共子序列

最长公共子序列

14.3 高维问题

14.4 课后习题与实验

樱花

奶牛展览

262144

第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 课后习题与实验

关于《深入浅出程序设计竞赛》(进阶篇) 的讨论