[L2] 00_基础算法

核心哲学：基础算法的本质只有两步：
找出题目中的有效信息，
然后用最简单的数学逻辑把问题拆散。

本次整理

从 P4552 IncDec Sequence 观察区间加减如何变成差分单位的配对与边界分配；专题入口仍可沿 倍增策略、分治策略 与 排序体系 继续深入。

1. 知识图谱与演化

• 核心模型: 贡献度拆解、单调性观察、不变量构造、信息简化。

• 演化路径:

  1. 暴力模拟：最原始的模拟大法，瓶颈在于重复计算，往往 TLE。

  2. 降维优化：引入双指针、前缀和、离散化，将重复的搜索过程转化为简单的线性扫描或查表。

  3. 单调性：引入二分和单调栈/队列，将线性查找优化为对数查找或者线性维护。

  4. 策略与构造：证明局部最优即全局最优（贪心），或直接利用数学规律（构造）跳过计算。

2. 决策矩阵

• 场景 A: 统计区间和/异或，且数据静态。

  • 决策: 采用 前缀和/差分， $O(n)$ 预处理， $O(1)$ 查询。

• 场景 B: 答案具有单调性（越大/越小，越容易/越难达标）。

  • 决策: 采用 二分答案，复杂度为 $O(\log N)$ 次判定。

• 场景 C: 处理滑动窗口或需要寻找“最近的比我大/小的元素”。

  • 决策: 采用 双指针 / 单调栈与队列。核心是优胜劣汰，及时剪枝。

• 场景 D: 答案具有特定的数学结构或需要直接构建可行解。

  • 决策: 采用 构造 / 贪心。寻找不变量。

3. 核心板块索引

3.1 [L3] 降维技巧

• [[贡献法]]：转换视角，计算每个元素对答案的贡献。

3.2 [L3] 02 解题思维

• 贪心策略: 局部最优推导全局最优。

• 构造策略: 利用数学本质（二进制、奇偶性）拼凑解。

• 倍增策略：用二进制拆解复用成倍增长的信息。

• 分治策略：把原问题拆成结构相同、规模更小的子问题再合并。

3.3 [L3] 03 排序与二分

• 排序体系: 归并（求逆序对）与快排思想。

• 浅谈二分答案：把最优化问题转化为具有单调性的参数化判定，并寻找可行性边界。

• [[Note] 三分搜索]: 解决凸/凹函数的极值问题。

3.4 [L3] 04 搜索战术

• [[Note] 折半搜索]: 任务切半，分别搜完再合并，对数复杂度应对问题。

• [[Note] 启发式搜索]: 利用估价函数引导搜索方向。

• [[Note] 模拟退火]: 随机化算法，以概率换取最优解。