枚举
今天带着两步走：先把答案的空间想清楚，再把空间的边界砍下来。
今天下课时，你必须能自己说出这三句话
① 说得出「枚举什么」
看到一道题，先找出枚举的要素：枚举谁？枚举几层？可能情况一共有多少种？
② 砍得动「枚举空间」
枚举范围定在哪里？哪些情况根本不必枚举？把 10⁹ 砍到 10⁶ 才是真本事。
③ 写得出「枚举代码」
循环嵌套顺序、边界取模、判环标记——三道容易踩空的坑，今天一次填平。
🔥 课前热身：先凭直觉答，不要想太久
下列哪一句最接近「枚举」的本质？
枚举是什么：定义 + 四步法
📖 定义
枚举就是把所有可能的答案一一列举出来，再加以判断， 又称暴力枚举、穷举。
判据只有两条：穷尽（不重不漏）＋判断（每个候选都能验真伪）。
🧭 做题四步法
前 3 步来自原课例的「三步骤」，第 4 步是本课补上的 工程落地一步——今天有一道真题会专门讲它。
🎯 小练：把四步法按正确顺序点出来（点四次）
枚举算法常见题型：四大类 · 八小类
点开每张卡片，看它「枚举什么、怎么砍空间」。
🔢 基础枚举
数值枚举
遍历区间 [1, n]，筛选满足条件的数
例：被 3 整除且各位和为偶数
🔤 基础枚举
字符串枚举
遍历字符/字符串集合，匹配特定模式
例：以指定字母开头且长度为偶数
🧩 组合枚举
子集枚举
位运算 / 递归枚举子集再筛选
例：元素和能被 k 整除
🧩 组合枚举
排列枚举
回溯生成全排列再筛选
例：无重复数字且能被指定数整除
⚙️ 算法结合
枚举 + 贪心
枚举关键状态后应用贪心策略
例：任务分配顺序枚举 + 贪心分配资源
⚙️ 算法结合
枚举 + 动态规划
枚举状态后用 DP 解子问题
例：背包容量枚举 + DP 求最优解
🏕️ 场景枚举
生活场景
枚举活动组合，求最大兼容活动数
例：时间安排问题
🎮 场景枚举
游戏场景
枚举移动方向，搜索迷宫路径
例：BFS/DFS 遍历方向
[ABC258B] 数字盒子 Number Box
📄 题意
有一个 N × N 的数字方格网，上下边缘相连、左右边缘相连。
先在 8 个方向（上下左右 + 四斜向）中选一个，再从任意格出发移动一格， 重复 N − 1 次，共经过 N 格。
把经过的格子上的数字按顺序拼成一个整数，求最大值。
数据范围：1 ≤ N ≤ 10，1 ≤ A[i][j] ≤ 9。
🔍 先找枚举要素
💡 样例
输入
4 1161 1119 7111 1811
输出
9786
下一屏我们把「为什么是 9786」算给你看。
为什么是 9786：把网格「铺开」看环绕
因为网格上下左右都是循环的，所以我们把 4 组数据粘起来，模拟出循环的样子。
正式网格（4×4，点击任意数字设为起点）
铺开后的 8×8：把 4×4 横竖各接一份自己
🧮 手动走一遍：同一条路线，两种画法
(2,4) → (3,1) → (4,2) → (1,3)
数字依次 9、7、8、6
(2,4) → (3,5) → (4,6) → (5,7)
数字依次 9、7、8、6 → 拼成 9786
两条路线取到的数字完全一样——这就是「环绕」的本质： 走出去的格子，其实就是对面那一格的另一份拷贝。铺开只是把我们心里绕的那一下，画成了直线。
动手枚举：换方向，答案就变了
点数字改起点，点下面的米字格按钮换方向。
当前枚举
🎯 体会「枚举空间」
起点 4² = 16 个 × 方向 8 个 = 128 种情况，每种拼一个 4 位整数，取最大。
如果这道题是 N = 2000 呢？8N³ 早就爆了——那时就得靠「砍空间」，而这题的数据范围告诉你：放心枚。
🏁 全班挑战
把方向全部试一遍，说出最大整数是多少？它是哪个起点、哪个方向走出来的？（答案在下一屏）
方向数组（上）：八个方向怎么记、怎么定义
八个方向写 8 段 if-else 也能过，但循环不起来。方向数组让「试遍所有方向」变成一行 for。
① 怎么记：米字格 + 相对坐标变化
红格是当前所在格 (x, y)，要从它走到周围 8 格， 需要的就是每一格相对它的坐标变化量 (dx, dy)。点右边表格的任意一行，这里会亮起对应那一格。
② 定义：两个「平行数组」
// 下标 k 是同一层的意思，两个数组相同 k 取出的就是一对 int dx[8] = {-1,-1,-1, 0, 1, 1, 1, 0}; int dy[8] = {-1, 0, 1, 1, 1, 0,-1,-1};
| k | dx[k] | dy[k] | 方向 | 行列怎么变 |
|---|---|---|---|---|
| 0 | -1 | -1 | 左上 | 行 −1、列 −1 |
| 1 | -1 | 0 | 上 | 行 −1 |
| 2 | -1 | 1 | 右上 | 行 −1、列 +1 |
| 3 | 0 | 1 | 右 | 列 +1 |
| 4 | 1 | 1 | 右下 | 行 +1、列 +1 |
| 5 | 1 | 0 | 下 | 行 +1 |
| 6 | 1 | -1 | 左下 | 行 +1、列 −1 |
| 7 | 0 | -1 | 左 | 列 −1 |
顺序是「从左上开始顺时针」。因为 8 个方向最终都要走到， 顺序不影响答案——但固定一个顺序，调试和讲课都好对照。
点完米字格就翻下一页，四条知识点和两个翻车点留到下一页再给。
方向数组（下）：怎么用、要小心什么
三个动作 + 两种边界，再加六条动手前必扫的知识点。
③ 怎么用：把「试遍所有方向」拆成三个动作
int nx = x + dx[k];int ny = y + dy[k];先只算，不动 x、y
有墙／会走出去 →
continue 跳过这个方向环形相连（本题）→ 用取模绕回去
x = (x + dx[k] + n) % n;y = (y + dy[k] + n) % n;先算再判后赋值，下标永不越界
// 4 方向版本：把 8 换成 4，循环体一个字都不用改 int dx[4] = {-1, 0, 1, 0}; int dy[4] = { 0, 1, 0,-1}; for (int k = 0; k < 4; k++) { int nx = x + dx[k], ny = y + dy[k]; if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; // 出界，跳过这个方向 // …在这里处理 (nx, ny)… }
· 题面说「越界就不合法」→ 用
continue 跳过；· 题面说「上下相连、左右相连」（本题）→ 用
(… + n) % n 绕回去。走错门就会「样例过、提交挂」。
④ 相关知识点（六条，动手前扫一眼）
| 知识点 | 要点 |
|---|---|
| 为什么要用数组 | 把「变化规律」放进表里，循环体只写一遍。for (k = 0; k < 8; k++) 就等价于
「所有方向各试一次」，不用写 8 段搬来搬去的 if-else。 |
| dx 管行，dy 管列 | 最容易写反的一处：dx 是行（上下）的变化，dy 是列（左右）的变化。 写反了程序照样跑、不报错，但方向全错——典型的「编译通过、答案全错」。 |
| 数组长度必须等于方向数 | 循环写 k < 8 而数组只开了 4 个元素 → 越界读，拿到的是内存里的随机值。
本地小数据可能侥幸过，交到 OJ 上就是 WA 或 Runtime Error。 |
| 中心 (0,0) 绝不能写进去 | 加上它就等于「原地不动」：判环会误判，不判环则直接死循环。 |
| 同一套外壳能换「步法」 | 国际象棋「马走日」：dx[8]={1,1,-1,-1,2,2,-2,-2}、
dy[8]={2,-2,2,-2,1,-1,1,-1}；三维网格加一个 dz；
六边形网格是 6 个方向。方向数组是「枚举移动」的通用外壳。 |
| 起点和方向是两个维度 | 本题在方向数组外面还套了一层「起点」循环：外层遍历 8 个方向、内层遍历每个格点 (i,j) 作为起点。 方向和起点是互相独立的两个枚举要素，所以总情况数是 N² × 8，而不是 N² + 8。 |
①
dx/dy 抄错一位 → 8 个方向里有一个是错的，本地样例可能照样过。
动手前先把 8 个方向在纸上逐个口述一遍。② 取模忘写
+ n → C++ 里负数取模仍是负数，下标越界。写取模时顺手把 + n 打上，
再用一组「起点在最左边、方向朝左」的数据自测一次。
最后用一个问题过渡到下一页代码：「如果题目没说上下相连，该用
continue 还是取模？」代码走读：三处关键，一处易错
// 8 个方向的相对坐标变化数组 int dx[8] = {-1,-1,-1, 0, 1, 1, 1, 0}; int dy[8] = {-1, 0, 1, 1, 1, 0,-1,-1}; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int k = 0; k < 8; k++) { int x = i, y = j; // ① 起点每个方向都要重置 long long num = 0; // ② 必须 64 位 for (int c = 0; c < n; c++) { num = num * 10 + (g[x][y] - '0'); x = (x + dx[k] + n) % n; // ③ 加 n 防负数 y = (y + dy[k] + n) % n; } ans = max(ans, num); }
🔑 三层循环各管什么
视频里把
int x = i, y = j; 写在了方向循环外面。它在本题（环形网格）里其实恒正确——
因为在环形网格上平移是一一对应的——每个格子恰好被走到一次，既不重复也不漏。
无论 N 是几、无论走几步，起点虽没重置，绕完 8 个方向仍覆盖全部 N²×8 种组合，一个不漏。但它只在"网格首尾相连"时成立：普通（有墙）网格里起点会随方向漂移，大量组合被跳过而直接出错（实测 3 万组随机数据 22068 组不一致）。 所以工程上一律写在方向循环内部——这不是"视频侥幸"，而是"你写的下一题多半不是环形"。结果正确 ≠ 写法可迁移。
✍️ 三连问
① ans 和 num 如果声明成 int，会发生什么？
② 取模写成 x = (x + dx[k]) % n 会怎样？
[ABC265C] 传送带 Belt Conveyor
📄 题意
H 行 W 列网格，每格写着 U D L R 之一，表示站在该格时往哪个方向移动一格。
从 (1,1) 出发，不断重复操作，直到无法再移动为止：
- G[i][j] 是
U且 i ≠ 1 → 移到 (i-1,j) - G[i][j] 是
D且 i ≠ H → 移到 (i+1,j) - G[i][j] 是
L且 j ≠ 1 → 移到 (i,j-1) - G[i][j] 是
R且 j ≠ W → 移到 (i,j+1) - 都不满足 → 停住
输出停住时所在的格子；若永远走不停，输出 -1。
🔍 先找枚举要素
💡 样例 1 / 样例 2
样例 1（输出 1 3）
2 3 RDU LRU
样例 2（输出 -1）
2 3 RRD ULL
下一页的模拟器里还准备了两组课堂加练样例（4×4 走 11 格停住、5×5 走 15 格后死循环），可以现场切着走。
亲手走一遍：停住还是转圈？
选择样例 → 点「走一步」或「自动走」 → 观察什么时候必须停下来。
🧠 判环的三条线索
① 用 vis[i][j] 记录到过的格子；
② 又踩到 已经访问过 的格子 → 说明成了一个环，永远出不来 → 输出 -1；
③ 下一步会走出网格 → 立刻停在当前格并输出坐标。
补充：也可以用「步数超过 H×W 就判环」的写法，等价但不如标记数组直观。
⚠️ 输出的是哪一格？
输出的是停在的那一格，也就是「移动前」的格子，不是越界后想象中的那一格。
样例 1 的终点是 (1,3) —— 你如果输出了 (1,4)，就是这一类错误。
代码走读：一个 while，三个出口
int x = 1, y = 1; while (true) { if (vis[x][y]) { // 出口 1：判环 cout << -1; return 0; } vis[x][y] = true; int nx = x, ny = y; char c = g[x][y]; if (c == 'U') nx--; else if (c == 'D') nx++; else if (c == 'L') ny--; else ny++; // 'R' if (nx < 1 || nx > h || ny < 1 || ny > w) { // 出口 2：出界 cout << x << " " << y; return 0; } x = nx, y = ny; // 出口 3：继续走 }
🔑 三处判断的顺序很重要
nx, ny 试探，不动真格① 把
if (vis[nx][ny]) 写在出界判断之前：网格外那一圈的下标也落在数组里，
vis 一旦开小就是 RE。② 输出成「移动后的坐标」：样例 1 会变成 (1,4)，白丢分。
✍️ 两连问
① 这题为什么不能用 BFS 求最短路？
② 从 (1,1) 出发，最多可能走多少步？
四句话，先投票，再讲理
凭直觉点「对」或「错」，再点「看解析」。
① 枚举就是最笨的暴力，纯粹浪费时间，能不用就不用。
② 数字盒子里，方向循环内部的起点 x,y 必须重新赋值。
③ 传送带中，走到已访问过的格子就说明进入了死循环。
-1。④ 传送带里，先判 vis[nx][ny] 再判出界，反正数组开大点就行。
枚举知识树：一棵主干，四条分支
🏁 今天带走一句话
先把答案空间想清楚，再把空间的边界砍下来；能枚就枚，枚完再想优化。
一道题 100 分是分档给的——不会正解也要先拿保底
复赛一道题的 100 分由十几到二十几个测试点组成， 前面几档专门为「没想出正解的人」准备。四道题各拿 30~40 分， 加起来往往就是一等奖和二等奖的分界。
① 特判档：先别想算法，看数据范围表
题目给的数据范围表就是出题人给你的送分清单。看到「n = 1」「只有一组数据」这类一行，
就先写个 if 直接输出答案。2 分钟换 5~10 分，全场最划算。
② 暴力档：按题意最直白地写一遍
多重循环、DFS 全枚举、朴素 O(n³)……不要优化，只要保证最小那档全对。 它既是保底分，又是后面对拍的标尺——没有它你无法证明正解是对的。
③ 特殊性质档：题目里那句「若……」
常见的送分性质：数据已经有序、所有值完全相同、规模小到可以 O(n²)、 只出现一种类型。题目写出来就是让你拿的，专门写一份即可。
④ 正解档：思路定了，就赢了八成
考场上的时间几乎都花在想思路上，不是写代码。写完先跑样例， 再用第 ② 档的暴力版造小数据对拍——这是唯一能证明你思路对的办法。
本讲 2 道题，各自的四档怎么走
数字盒子 / Number Box · ENUM258B
第1档 · 2 分钟N == 1 时只有一个格子，答案 1 或 0；格子字符全同时先手算一遍
第2档 · 8 分钟
每格 × 8 个方向 × N 个字符逐字比，O(8N³)，N ≤ 10 完全跑得完
第3档 · 10 分钟
先只做 4 个正方向（下/右/上/左），拿到一半分再补 4 个斜向
第4档 · 15 分钟
8 个方向数组 + 下标取模，把环面当普通数组走
传送带 / Belt Conveyor · ENUM265C
第1档 · 2 分钟
起点就是终点 → 输出 0；棋盘上没有箭头格 → 退化成普通网格 BFS
第2档 · 8 分钟
直接 BFS，把「滑行」当成一步一步走，N ≤ 20 稳过
第3档 · 10 分钟
预处理每个箭头格「最终滑到哪一格」，把整段滑行压成一条边
第4档 · 15 分钟
0-1 BFS：滑行边权 0、步行边权 1，用 deque
0–5 分钟 读题 + 圈出数据范围表里最小的那几档 → 5–15 分钟 写完第 1、2 档并先交一次（保住 20~30 分）→ 15–40 分钟 冲第 3、4 档 → 40–50 分钟 造小数据对拍、检查
freopen 与文件名。三道小题 + 两道真题提交
🧪 速答三题
① 工程上为什么要求把起点写在方向循环内部？
② 传送带输出的是哪一格？
③ 传送带判环，最直观的做法是？
💻 上机任务（椰程信奥 OJ）
📌 提交前自查四件事
① 答案变量是否 64 位？ ② 取模有没有加 n？
③ 起点是否写在方向循环内部？ ④ 判环 / 出界的顺序对不对？
知识补给站：课前该会、课后能拓
前面两道真题默认你会了一些"基本功"，也埋了几个能往深处走的口子。这里一次补齐。
🧰 前置补给（默认你会、但课上没讲）
① 字符网格读入：先读行 cin>>s 或 getline，再逐字符 s[j]-'0' 转数字。
② c-'0' 才是数字：char 直接当 int 拿到的是 ASCII（'0'=48），必须减 '0'。
③ 0-based / 1-based 别套错：258B 用 0-based 坐标，265C 用 1-based（vis[505][505] 的 505 是 1-based 余量）。跨题照搬必 WA。
④ 静态数组尺寸：int a[505][505] 开在栈上，太大（≈1e6 个 int 量级）会栈溢出；要么缩小，要么开全局 / vector。
⑤ 整型临界：int 上限 2147483647（10 位）。N=10 拼 10 位数→必用 long long；N≥19 连 long long 都超（需 __int128 / 字符串）。
⑥ printf 格式：printf("%d", (long long)x) 是未定义行为，必须 %lld。
⑦ vis / ans 初值：每个测试点 memset(vis,0) 清零；求最大别把 ans 初始化成 0（可能全负）。
🚀 横向扩展（把枚举从"会做"升到"看得透"）
① 判环不止 vis：Floyd 快慢指针（龟兔赛跑）边走边判，免 vis 数组、额外 O(1) 空间。
② 抽屉原理证步数上限：传送带每格唯一方向，H×W 步内必重复或到达——走超 H×W 步还没到就直接判 -1，不用 vis 也能定上界。
③ 乘法原理升维：本题 N²（起点）×8（方向）= N²×8，是"独立要素相乘"而非相加；多个独立枚举要素都这么算。
④ 二分 / 折半枚举：答案单调时，枚一半、算另一半，把 O(N²) 降到 O(N log N)。
⑤ 大数延伸：N≥19 拼数超 long long → 上字符串 / 高精度，或只比位数与字典序。
⑥ 环面一一对应（回扣本课）：起点写循环外在环形网格恒对，正是因为"平移一一对应、每个格子恰好走到一次"——这页前半的坑，根上都在这。
课前用「前置补给」自查：哪条你其实不会，先补再上机。课后用「横向扩展」挑 1—2 条当微专题，下次课用 8 分钟串讲，枚举专题就真正"成体系"了。