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

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

第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 有向图的强连通性

缩点

2-SAT问题

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

第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 优化转移

逆序对数列

夏令营

能量收集

最长上升子序列

面包师

任务安排1 任务安排2 任务安排3

18.3 课后习题与实验

翻转矩形

缩小社交圈

找宝石

编程较量

第5部分数学专题选讲

第19章进阶数论

19.1 模意义下的数和运算

19.2 乘法逆元

小凯的数学

乘法逆元

19.3 同余方程与中国剩余定理

小曹养牛

19.4 线性筛与积性函数(选读)

拆分

19.5 欧拉函数(选读)

光速幂

Longge的问题

19.6 课后习题与实验

裴蜀定理

有理数取余

好日子

朋友

求质数

超级最大公约数

最长子序列

最大公约数表

余数游戏

回首过去

集合的正确用法

第20章组合数学与计数

20.1 集合与容斥原理

Emiya家今天的饭

盒子与球1

20.2 常见的组合计数方法

种树

20.3 二项式定理

高度相同

20.4 卡塔兰数与斯特林数

盒子与球2

20.5 课后习题与实验

组合数问题

有趣的数列

纸牌

划分

第21章概率与统计

21.1 事件

21.2 概率模型

世界杯门票

21.3 数学期望

成功与失败

树上的游戏

21.4 课后习题与实验

条件概率

连击游戏

单选错位

考试

第22章基础线性代数

22.1 向量与矩阵变换

斐波那契数列

22.2 高斯消元

线性方程组

22.3 课后习题与实验

广义斐波那契数列

矩阵加速

千足虫

行列式求值

小莉的手环

球形空间产生器

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