GESP 1-4级 -- GESP 5-8级 -- CSP-J/S --

官方题单知识点专项

枚举

把可能情况枚举完整，再配合剪枝把搜索范围压下去。

开始练习 ← 返回广场

题数：24题

完成度：0/24

枚举算法概述 定义：通过遍历所有可能的情况（或部分可能情况）来寻找答案的算法思想。 核心思想：将问题拆解为有限的状态集合，通过逐一检查找出满足条件或最优的方案。 常用用途：暴力搜索、最优值验证、组合生成、合法方案统计等。 --- 一、朴素枚举 思想：直接枚举所有可能的变量组合，逐一判断是否合法或计算结果。 常见形式： - 单层循环：枚举一个变量； - 双层循环：枚举有序或无序对； - 三层循环：枚举三元组、三角形、三人组等。 --- 二、常数枚举 思想：朴素的循环嵌套枚举在枚举对象较多的情况下可能复杂度过高，循环嵌套的枚举如果是 $k$ 层循环， 那么对应的复杂度为 $O(n^k)$， 当题目中给出了一定的常数级别限制条件时，可以减少我们的循环的次数， 降低时间复杂度从而通过题目。 模板例题：公交换乘 --- 三、子矩阵枚举（二维枚举） 场景：在二维矩阵中统计或判断所有子矩阵（如最大子矩阵和、满足条件的区域计数等）。 思路： 1. 枚举左上角坐标 $(x_1, y_1)$； 2. 枚举右下角坐标 $(x_2, y_2)$； 3. 计算该区域的结果或属性。 典型应用： - 最大子矩阵和问题； - 子矩阵计数问题； - 最大平均子矩阵或满足条件的区域搜索。 --- 四、二进制枚举（子集枚举） 场景：需要枚举所有子集或状态（常用于 $n \le 20$ 的问题）。 思想：用一个长度为 $n$ 的二进制数表示集合的选取状态。 【思维导图】 【题目知识点分类】