Basic Algorithm

自动关联目录:Basic Algorithm

这一组是不依赖特定数据结构的通用算法思想。它们不是"某一类题的解法",而是思考问题的方式——后面所有高级算法都是它们的组合。

一张表

思想一句话适用信号
枚举把候选答案一个个试过去答案空间有限,能判定
二分答案/区间有单调性,每次砍一半"最大的最小值""满足条件的最早时刻"
贪心每步取局部最优有贪心选择性质(最难证明)
递归 / 分治大问题拆成同构的小问题结构可递归定义(树、序列)
倍增预处理2k2^k 的跳跃,按需拼装需要"跳nn 次"的重复操作
前缀和 / 差分区间求和↔区间修改的对偶静态区间查询 / 批量区间加
排序先有序再处理元素间有偏序关系

它们的共性

都是"减少工作量"的手段:

  • 枚举:诚实干活,靠剪枝减少
  • 二分:靠单调性排除一半
  • 贪心:靠最优子结构 + 贪心选择只走一条路
  • 分治:靠子问题独立并行处理
  • 倍增:靠二进制拆分把nn 次变log⁡n\log n 次
  • 前缀和:靠预处理把O(n)O(n) 查询变O(1)O(1)

识别"哪些工作可以不做",就是算法优化的本质。

章节

章节核心
Binary Search二分查找 / 二分答案 / 边界处理
Binary Lifting倍增、ST 表、LCA
Enumerate子集枚举、排列枚举、剪枝
Greedy贪心策略与证明方法
Recursion & Divide and Conquer递归式、主定理、分治模板
Sort各类排序及稳定性/复杂度
前缀和 & 差分区间操作的对偶技巧

通用的边界检查清单

写完先自查这几项,能挡掉大半的 WA:

  • 输入为空 /n=0n = 0 /n=1n = 1
  • 元素全相同、全不同、已有序、逆序
  • 最大值 / 最小值 / 负数 / 0
  • 溢出(int 够不够?中间结果会不会爆?)
  • 循环边界是 < 还是 <=(尤其二分)