第 5 章：模拟与暴力枚举 (Simulation & Brute Force)

大道至简，重剑无锋。

如果题目规模很小，或者逻辑非常具体，不要去想复杂的动态规划或图论，直接按照题目说的做，或者把所有可能性试一遍。

5.1 模拟：翻译官的艺术

模拟 (Simulation) 就是把题目描述的规则，用代码一丝不苟地“翻译”出来。

这类题目通常不涉及复杂的算法原理，难点在于：

规则繁琐：比如“大富翁游戏”、“日期计算”、“俄罗斯方块”。
坑点多：边界条件极其恶心（比如 2 月 29 日、时间进位）。

5.1.1 模拟题的三大铁律

不要急着写：先在草稿纸上模拟一遍流程，确信自己理解了所有规则。
模块化编程：别把所有逻辑都塞进 main 函数。
- 算日期？写个 bool isLeap(int year)。
- 算距离？写个 double dist(p1, p2)。
- 这能极大降低 Debug 难度。
心态稳住：模拟题代码量通常很大（100+ 行），写错了很难受。保持耐心。

5.1.2 经典案例：日期处理

计算“两个日期之间差多少天”是经典的模拟题。不要自己手写 if-else 去加减天数，很容易错。

技巧：选取一个基准日（比如 0000年1月1日），计算两个日期分别距离基准日多少天，然后相减。

5.2 暴力枚举：计算机最擅长的事

枚举 (Enumeration)，俗称“暴力破解” (Brute Force)。核心思想是：宁可错杀一千，不可放过一个。

我们在第 4 章学过，只要运算量不超过 $10^8$ ，暴力就是所谓“正解”。

5.2.1 循环枚举

最简单的形式。题目：寻找 $1 \sim N$ 之间满足某条件的数。解法：for (int i = 1; i <= n; i++) if (check(i)) ...

5.2.2 排列枚举 ( $N \le 10$ )

题目：把 $1 \sim N$ 这 $N$ 个数字排成一排，问哪种排列满足条件？ 复杂度： $10! = 3,628,800$ （非常安全）。工具：next_permutation（第 3 章提过，这里是它的主场）。

模板代码：

vector<int> p = {1, 2, 3, 4}; // 初始必须是最小排列
do {
    // 在这里检查 p 是否符合题目要求
    // if (check(p)) ...
} while (next_permutation(p.begin(), p.end()));

5.2.3 子集枚举 ( $N \le 20$ )

题目：给你 $N$ 个物品，每个物品可以选或不选，问哪种组合最好？ 复杂度： $2^{20} \approx 10^6$ （非常安全）。技巧：二进制状态压缩（Bitmask）。

我们可以用一个整数 s 来代表一个子集。如果 s 的二进制第 $i$ 位是 1，表示选第 $i$ 个物品。

模板代码（必背）：

// 假设 n = 3，循环从 0 (000) 到 7 (111)
for (int s = 0; s < (1 << n); s++) { 
    // 检查这个子集 s
    vector<int> subset;
    for (int i = 0; i < n; i++) {
        // 检查 s 的第 i 位是否为 1
        if (s & (1 << i)) {
            subset.push_back(items[i]);
        }
    }
    // 对 subset 进行计算...
}

5.3 剪枝 (Pruning)：让暴力跑得更快

虽然是暴力，但也不能在那傻算。剪枝的意思是：在搜索过程中，如果你发现当前这条路绝对不可能得到最优解（或合法解），就立刻回头 (break/return)，不要继续往下搜了。

案例演练：选数求和

题目：从 $N$ 个数中选出 $K$ 个数，判断它们的和是否等于 $T$ 。 暴力 DFS：尝试选第 1 个，然后选第 2 个……

剪枝策略：

可行性剪枝：如果当前选出来的数字之和已经 $> T$ 了，后面哪怕选最小的负数也救不回来（假设都是正数），直接 return。
最优性剪枝：如果题目求“最小代价”，而你当前的代价已经超过了之前找到的某个答案 min_cost，直接 return。

// DFS 伪代码示例
void dfs(int index, int current_sum) {
    // 剪枝：如果已经超过目标，没必要继续了
    if (current_sum > target) return; 
 
    if (index == n) {
        if (current_sum == target) ans = true;
        return;
    }
    
    // 选当前数
    dfs(index + 1, current_sum + nums[index]);
    // 不选当前数
    dfs(index + 1, current_sum);
}

5.4 什么时候不能用暴力？

回到第 4 章的表格。

$N=1000$ ，想枚举全排列？ $1000!$ 是天文数字 $\rightarrow$ 死路一条。
$N=10^5$ ，想用 $O(N^2)$ 的双重循环？ $\rightarrow$ TLE。

做题策略：

先看 $N$ 。
如果 $N$ 小，直接暴力（模拟/DFS/二进制枚举）。
如果 $N$ 大，暴力只是用来对拍的（用来验证你的高级算法对不对）。

🧠 本章小结与练习

不要因为学了高级算法就看不起暴力。绝大多数比赛的铜牌题（Bronze）就是纯粹的模拟或暴力。

练习作业：

P1157 组合的输出 (洛谷)：练习 DFS 或二进制枚举。
P1003 [NOIP2011 提高组] 铺地毯：经典的模拟题。注意：不要开二维数组去模拟地毯覆盖（ $N$ 很大），要想办法倒着查坐标。

掌握了暴力法，你就拥有了保底的能力。但要处理 $N=10^5$ 的数据，你需要更高效的方法。 下一章，我们将学习最基础的优化算法——如何通过“排序”和“二分”把 $O(N)$ 降维打击成 $O(\log N)$ 。