⭐ 信息学奥赛考前复习提纲

本文不是我原创，此处仅作记录。

一、二分答案类问题

1.1 最小化最大值问题

• 问题1：如何解决数组分割类的最小化最大值问题？

• • 问题类型：二分答案 - 数组分割
• • 问题特征：将数组分成k段，使各段和的最大值最小
• • 核心判断点：验证函数需要贪心分割，确保每段和不超过mid
• • 常见做法：二分答案 + 贪心验证
• • 推荐例题：LeetCode 410 Split Array Largest Sum

• 问题2：如何解决资源分配类的最小化最大值问题？

• • 问题类型：二分答案 - 资源分配
• • 问题特征：将任务分配给工人，使最大工作时间最小
• • 核心判断点：验证函数需要合理分配任务，不超过工人能力
• • 常见做法：二分答案 + 回溯/贪心验证
• • 推荐例题：LeetCode 1723 完成所有工作的最短时间

• 问题3：如何解决距离类的最小化最大值问题？

• • 问题类型：二分答案 - 距离优化
• • 问题特征：在直线上选择点，使任意两点间最小距离最大
• • 核心判断点：验证函数需要贪心放置点，保证最小间距
• • 常见做法：二分答案 + 贪心放置
• • 推荐例题：POJ 2456 Aggressive cows

1.2 最大化最小值问题

• 问题4：如何解决切割类的最大化最小值问题？

• • 问题类型：二分答案 - 切割优化
• • 问题特征：将材料切成等长段，使每段长度最大
• • 核心判断点：验证函数计算能切出的段数是否足够
• • 常见做法：二分答案 + 数学计算验证
• • 推荐例题：POJ 1064 Cable master

• 问题5：如何解决预算分配类的最大化最小值问题？

• • 问题类型：二分答案 - 预算分配
• • 问题特征：在预算限制下，使最小分配额最大
• • 核心判断点：验证函数需要合理分配预算
• • 常见做法：二分答案 + 贪心分配
• • 推荐例题：CF 460C Present

二、动态规划类问题

2.1 线性DP

• 问题6：如何解决单序列线性DP问题？

• • 问题类型：线性DP - 单序列
• • 问题特征：状态只与序列前i个元素相关
• • 核心判断点：定义dp[i]为前i个元素的最优解
• • 常见做法：单重循环，状态转移基于前序状态
• • 推荐例题：LeetCode 300 最长递增子序列

• 问题7：如何解决双序列线性DP问题？

• • 问题类型：线性DP - 双序列
• • 问题特征：状态与两个序列的前缀相关
• • 核心判断点：定义dp[i][j]为序列A前i个和序列B前j个的最优解
• • 常见做法：双重循环，考虑匹配、插入、删除等操作
• • 推荐例题：LeetCode 1143 最长公共子序列

2.2 区间DP

• 问题8：如何解决合并类的区间DP问题？

• • 问题类型：区间DP - 合并优化
• • 问题特征：合并区间元素，代价与合并顺序相关
• • 核心判断点：定义dp[l][r]为合并区间[l,r]的最小代价
• • 常见做法：枚举分割点k，dp[l][r] = min(dp[l][k] + dp[k+1][r] + cost)
• • 推荐例题：Luogu P1880 石子合并

• 问题9：如何解决回文类的区间DP问题？

• • 问题类型：区间DP - 回文处理
• • 问题特征：处理回文子串、回文分割等问题
• • 核心判断点：dp[l][r]表示区间[l,r]是否为回文
• • 常见做法：中心扩展或区间DP判断回文
• • 推荐例题：LeetCode 132 分割回文串 II

2.3 背包DP

• 问题10：如何解决0-1背包问题？

• • 问题类型：背包DP - 0-1背包
• • 问题特征：每个物品选或不选，容量限制
• • 核心判断点：dp[j] = max(dp[j], dp[j-w] + v)
• • 常见做法：倒序遍历容量，避免重复选择
• • 推荐例题：Luogu P1048 采药

• 问题11：如何解决完全背包问题？

• • 问题类型：背包DP - 完全背包
• • 问题特征：每个物品可选无限次
• • 核心判断点：正序遍历容量，允许重复选择
• • 常见做法：dp[j] = max(dp[j], dp[j-w] + v)
• • 推荐例题：Luogu P1616 疯狂的采药

• 问题12：如何解决多重背包问题？

• • 问题类型：背包DP - 多重背包
• • 问题特征：每个物品有数量限制
• • 核心判断点：二进制优化或单调队列优化
• • 常见做法：将多重背包转化为0-1背包
• • 推荐例题：Luogu P1776 宝物筛选

2.4 状态压缩DP

• 问题13：如何解决棋盘覆盖类状态压缩DP？

• • 问题类型：状态压缩DP - 棋盘覆盖
• • 问题特征：在n×m棋盘上放置骨牌或方块
• • 核心判断点：用二进制表示每行状态，状态转移考虑兼容性
• • 常见做法：轮廓线DP或逐行DP
• • 推荐例题：POJ 2411 Mondriaan's Dream

• 问题14：如何解决旅行商类状态压缩DP？

• • 问题类型：状态压缩DP - 旅行商问题
• • 问题特征：访问所有城市一次并返回起点
• • 核心判断点：dp[mask][i]表示已访问城市集合mask，当前在城市i
• • 常见做法：枚举子集，状态转移考虑未访问城市
• • 推荐例题：Luogu P1171 售货员的难题

三、图论类问题

3.1 最短路径问题

• 问题15：如何解决非负权单源最短路径？

• • 问题类型：最短路径 - 非负权单源
• • 问题特征：边权非负，求单源最短路径
• • 核心判断点：选择Dijkstra算法
• • 常见做法：优先队列优化，时间复杂度O((V+E)logV)
• • 推荐例题：Luogu P4779 单源最短路径

• 问题16：如何解决带负权单源最短路径？

• • 问题类型：最短路径 - 带负权单源
• • 问题特征：边权可能为负，检测负环
• • 核心判断点：选择Bellman-Ford或SPFA算法
• • 常见做法：松弛操作，检测负环
• • 推荐例题：POJ 3259 Wormholes

• 问题17：如何解决全源最短路径？

• • 问题类型：最短路径 - 全源最短路径
• • 问题特征：求所有点对之间的最短路径
• • 核心判断点：选择Floyd-Warshall算法
• • 常见做法：三重循环，动态规划思想
• • 推荐例题：POJ 1125 Stockbroker Grapevine

3.2 最小生成树问题

• 问题18：如何解决稀疏图的最小生成树？

• • 问题类型：最小生成树 - 稀疏图
• • 问题特征：边数相对较少
• • 核心判断点：选择Kruskal算法
• • 常见做法：并查集 + 边排序，时间复杂度O(ElogE)
• • 推荐例题：Luogu P3366 最小生成树

• 问题19：如何解决稠密图的最小生成树？

• • 问题类型：最小生成树 - 稠密图
• • 问题特征：边数接近完全图
• • 核心判断点：选择Prim算法
• • 常见做法：优先队列优化，时间复杂度O(ElogV)
• • 推荐例题：POJ 1258 Agri-Net

3.3 网络流问题

• 问题20：如何解决最大流问题？

• • 问题类型：网络流 - 最大流
• • 问题特征：求从源点到汇点的最大流量
• • 核心判断点：选择Dinic或ISAP算法
• • 常见做法：分层图 + 多路增广
• • 推荐例题：Luogu P3376 网络最大流

• 问题21：如何解决最小割问题？

• • 问题类型：网络流 - 最小割
• • 问题特征：求使源汇不连通的最小边权割集
• • 核心判断点：最大流最小割定理
• • 常见做法：求最大流，最小割等于最大流
• • 推荐例题：POJ 2914 Minimum Cut

• 问题22：如何解决费用流问题？

• • 问题类型：网络流 - 最小费用最大流
• • 问题特征：在最大流基础上最小化总费用
• • 核心判断点：选择SSP或Primal-Dual算法
• • 常见做法：最短路增广，使用SPFA找负权路
• • 推荐例题：Luogu P3381 最小费用最大流

四、数据结构类问题

4.1 线段树问题

• 问题23：如何解决区间求和单点更新问题？

• • 问题类型：线段树 - 区间求和
• • 问题特征：频繁区间求和和单点更新
• • 核心判断点：线段树节点存储区间和
• • 常见做法：建树、更新、查询操作
• • 推荐例题：Luogu P3374 树状数组1

• 问题24：如何解决区间最值单点更新问题？

• • 问题类型：线段树 - 区间最值
• • 问题特征：频繁查询区间最值和单点更新
• • 核心判断点：线段树节点存储区间最值
• • 常见做法：建树、更新、查询操作
• • 推荐例题：Luogu P1531 I Hate It

• 问题25：如何解决区间修改区间查询问题？

• • 问题类型：线段树 - 区间修改
• • 问题特征：需要区间修改和区间查询
• • 核心判断点：使用懒惰标记(lazy propagation)
• • 常见做法：延迟更新，查询时下推标记
• • 推荐例题：Luogu P3372 线段树1

4.2 树状数组问题

• 问题26：如何解决单点更新前缀查询问题？

• • 问题类型：树状数组 - 单点更新
• • 问题特征：频繁单点更新和前缀查询
• • 核心判断点：使用树状数组维护前缀和
• • 常见做法：lowbit操作，update和query函数
• • 推荐例题：Luogu P3374 树状数组1

• 问题27：如何解决区间更新单点查询问题？

• • 问题类型：树状数组 - 区间更新
• • 问题特征：需要区间更新和单点查询
• • 核心判断点：使用差分数组+树状数组
• • 常见做法：维护差分数组的前缀和
• • 推荐例题：Luogu P3368 树状数组2

4.3 平衡树问题

• 问题28：如何解决动态排名查询问题？

• • 问题类型：平衡树 - 排名查询
• • 问题特征：动态维护集合，查询第k大元素
• • 核心判断点：选择Treap、Splay或FHQ Treap
• • 常见做法：维护子树大小，通过旋转保持平衡
• • 推荐例题：Luogu P3369 普通平衡树

• 问题29：如何解决区间翻转操作问题？

• • 问题类型：平衡树 - 区间操作
• • 问题特征：需要对序列区间进行翻转等操作
• • 核心判断点：选择Splay或FHQ Treap
• • 常见做法：分裂合并操作，懒惰标记
• • 推荐例题：Luogu P3391 文艺平衡树

五、字符串类问题

5.1 字符串匹配问题

• 问题30：如何解决单模式串匹配问题？

• • 问题类型：字符串匹配 - 单模式
• • 问题特征：在文本中查找单个模式串
• • 核心判断点：选择KMP算法
• • 常见做法：构建next数组，失配时跳转
• • 推荐例题：LeetCode 28 实现strStr()

• 问题31：如何解决多模式串匹配问题？

• • 问题类型：字符串匹配 - 多模式
• • 问题特征：在文本中查找多个模式串
• • 核心判断点：选择AC自动机算法
• • 常见做法：Trie树 + fail指针
• • 推荐例题：Luogu P3796 AC自动机

5.2 字符串处理问题

• 问题32：如何解决最长回文子串问题？

• • 问题类型：字符串处理 - 回文子串
• • 问题特征：求字符串中的最长回文子串
• • 核心判断点：选择Manacher算法
• • 常见做法：中心扩展，利用对称性
• • 推荐例题：LeetCode 5 最长回文子串

• 问题33：如何解决字符串编辑距离问题？

• • 问题类型：字符串处理 - 编辑距离
• • 问题特征：计算两个字符串的相似度
• • 核心判断点：动态规划求解
• • 常见做法：dp[i][j]表示A前i个和B前j个的编辑距离
• • 推荐例题：LeetCode 72 编辑距离

六、数学类问题

6.1 数论问题

• 问题34：如何解决素数判定与筛法问题？

• • 问题类型：数论 - 素数
• • 问题特征：判断素数或生成素数表
• • 核心判断点：选择适当的筛法
• • 常见做法：埃氏筛、欧拉筛、米勒-拉宾素性测试
• • 推荐例题：Luogu P3383 线性筛素数

• 问题35：如何解决最大公约数与同余问题？

• • 问题类型：数论 - 公约数与同余
• • 问题特征：涉及gcd、lcm、同余方程
• • 核心判断点：欧几里得算法、扩展欧几里得算法
• • 常见做法：辗转相除法、求解线性同余方程
• • 推荐例题：POJ 1061 青蛙的约会

• 问题36：如何解决组合数计算问题？

• • 问题类型：数论 - 组合数学
• • 问题特征：计算组合数C(n,m)模大数
• • 核心判断点：预处理阶乘和逆元
• • 常见做法：卢卡斯定理、预处理组合数
• • 推荐例题：Luogu P3807 卢卡斯定理

6.2 计算几何问题

• 问题37：如何解决凸包问题？

• • 问题类型：计算几何 - 凸包
• • 问题特征：求点集的凸包
• • 核心判断点：选择Graham扫描或Andrew算法
• • 常见做法：极角排序或坐标排序
• • 推荐例题：POJ 1113 Wall

• 问题38：如何解决最近点对问题？

• • 问题类型：计算几何 - 最近点对
• • 问题特征：求点集中距离最近的两个点
• • 核心判断点：分治法求解
• • 常见做法：按x坐标排序，分治合并
• • 推荐例题：POJ 3714 Raid

---

复习建议：

• 按问题类型分组练习，每组选择2-3道典型例题
• 对于每个子类型，总结模板代码和易错点
• 定期回顾，建立自己的解题知识体系
• 注重理解算法思想，而不仅仅是记忆代码

祝你通过系统训练，在竞赛中取得优异成绩！