Basic Algorithm
自动关联目录:Basic Algorithm
这一组是不依赖特定数据结构的通用算法思想。它们不是"某一类题的解法",而是思考问题的方式——后面所有高级算法都是它们的组合。
一张表
| 思想 | 一句话 | 适用信号 |
|---|---|---|
| 枚举 | 把候选答案一个个试过去 | 答案空间有限,能判定 |
| 二分 | 答案/区间有单调性,每次砍一半 | "最大的最小值""满足条件的最早时刻" |
| 贪心 | 每步取局部最优 | 有贪心选择性质(最难证明) |
| 递归 / 分治 | 大问题拆成同构的小问题 | 结构可递归定义(树、序列) |
| 倍增 | 预处理 的跳跃,按需拼装 | 需要"跳 次"的重复操作 |
| 前缀和 / 差分 | 区间求和↔区间修改的对偶 | 静态区间查询 / 批量区间加 |
| 排序 | 先有序再处理 | 元素间有偏序关系 |
它们的共性
都是"减少工作量"的手段:
- 枚举:诚实干活,靠剪枝减少
- 二分:靠单调性排除一半
- 贪心:靠最优子结构 + 贪心选择只走一条路
- 分治:靠子问题独立并行处理
- 倍增:靠二进制拆分把 次变 次
- 前缀和:靠预处理把 查询变
识别"哪些工作可以不做",就是算法优化的本质。
章节
| 章节 | 核心 |
|---|---|
| Binary Search | 二分查找 / 二分答案 / 边界处理 |
| Binary Lifting | 倍增、ST 表、LCA |
| Enumerate | 子集枚举、排列枚举、剪枝 |
| Greedy | 贪心策略与证明方法 |
| Recursion & Divide and Conquer | 递归式、主定理、分治模板 |
| Sort | 各类排序及稳定性/复杂度 |
| 前缀和 & 差分 | 区间操作的对偶技巧 |
通用的边界检查清单
写完先自查这几项,能挡掉大半的 WA:
- 输入为空 / /
- 元素全相同、全不同、已有序、逆序
- 最大值 / 最小值 / 负数 / 0
- 溢出(
int够不够?中间结果会不会爆?) - 循环边界是
<还是<=(尤其二分)
许可协议:CC BY
作者:Davids
本文链接:https://hustjjd.github.io/612f48da.html
更新于:2026年11月16日