一道+ / edao.plus

枚举法

按某个顺序把所有可能性“走一遍”，保证不重不漏。

直观场景

当问题的结构还看不清、公式不好套的时候，干脆一个一个列出来——只要建立清晰的“排列顺序”，答案就会从列表里浮出来。

推导思路

  1. 先设计一个能保证“不重”的枚举顺序（按大小、按字典序、按层）。
  2. 边枚举边检查是否满足题目条件。
  3. 收集所有满足条件的情况，统计个数或读出答案。

公式 / 要点

  • 分层枚举：先固定一个变量，再枚举另一个。
  • 对称性：有时可以只枚举一半再乘 2。

典型例题

1数对
方程 x + y = 10（x, y 均为正整数）有多少组解？
  1. 固定 x 从 1 枚举到 9，y = 10 − x 自动确定。
  2. x = 1..9 共 9 组解。
2三位数
用 1、2、3、4 中的数字（可重复）组成三位数，其中各位之和为 6 的有多少个？
  1. 按百位分类枚举：
  2. 百位 1：十 + 个 = 5，组合有 (1,4)(2,3)(3,2)(4,1)，4 个。
  3. 百位 2：十 + 个 = 4，有 (1,3)(2,2)(3,1)，3 个。
  4. 百位 3：十 + 个 = 3，有 (1,2)(2,1)，2 个。
  5. 百位 4：十 + 个 = 2，有 (1,1)，1 个。
  6. 共 4 + 3 + 2 + 1 = 10 个。

小结：“按百位分类 + 小范围枚举”是典型组合。

常见误区

  • 没有排序就容易漏或重复，先定顺序再开枚举。

用到“枚举法”的题目

#10006 棋盘上的线段·计数最值
计数六年级
#10025 韩信点兵·余同问题
数论六年级
#10033 枚举法·数字计数
计数三年级
#10067 装信错排·欧拉问题
杂题六年级
#10074 车站选址·总距离最短
杂题五年级
#10078 生产利润最大化·资源分配
杂题六年级
#10109 不等号数阵·3×3 排列
杂题五年级
#10158 网格计数·缺角4×4点阵中的正方形
计数五年级

相关知识点

分类讨论容斥原理