枚举

枚举算法概述

• 定义：通过遍历所有可能的情况（或部分可能情况）来寻找答案的算法思想。
• 核心思想：将问题拆解为有限的状态集合，通过逐一检查找出满足条件或最优的方案。
• 常用用途：暴力搜索、最优值验证、组合生成、合法方案统计等。

---

一、朴素枚举

• 思想：直接枚举所有可能的变量组合，逐一判断是否合法或计算结果。
• 常见形式：
  • 单层循环：枚举一个变量；
  • 双层循环：枚举有序或无序对；
  • 三层循环：枚举三元组、三角形、三人组等。

---

二、常数枚举

• 思想：朴素的循环嵌套枚举在枚举对象较多的情况下可能复杂度过高，循环嵌套的枚举如果是 $k$ 层循环， 那么对应的复杂度为 $O(n^k)$， 当题目中给出了一定的常数级别限制条件时，可以减少我们的循环的次数， 降低时间复杂度从而通过题目。
  模板例题：公交换乘

---

三、子矩阵枚举（二维枚举）

• 场景：在二维矩阵中统计或判断所有子矩阵（如最大子矩阵和、满足条件的区域计数等）。
• 思路：
  1. 枚举左上角坐标 $(x_1, y_1)$；
  2. 枚举右下角坐标 $(x_2, y_2)$；
  3. 计算该区域的结果或属性。
• 典型应用：
  • 最大子矩阵和问题；
  • 子矩阵计数问题；
  • 最大平均子矩阵或满足条件的区域搜索。

---

四、二进制枚举（子集枚举）

• 场景：需要枚举所有子集或状态（常用于 $n \le 20$ 的问题）。
• 思想：用一个长度为 $n$ 的二进制数表示集合的选取状态。

【思维导图】

【题目知识点分类】