模拟

一、概念

模拟就是用计算机来模拟题目中要求的操作。

建模：就是把事物进行抽象，根据实际问题来建立对应的数：学模型。

如果把实际问题建模成数学问题，就会大大地方便计算机来”理解“和”解决“。

1.1常见题型

模拟算法常见题型：

• 基本操作模拟：理解题目操作步骤，用代码准确实现。

• 简单场景模拟：以简单生活或游戏场景为背景，依地图信息和规则，模拟角色移动、探索等行为。

• 复杂系统模拟：模拟复杂系统或机制，如乘车购票，考虑因素相互影响，设计数据结构与算法实现。

• 算法结合模拟：将模拟与数学思维(找规律、快速幂、快排等）等高级算法结合考查。

练习题一： https://oj.yecheng.tv/p/GESP2304C4A

枚举

枚举就是把所有可能的答案一一列举出来再加以判断，又称：暴力枚举、穷举。

做题步骤：

• 1.建立数学模型 可能的情况是什么？要枚举哪些要素？

• 2.减少枚举的空间 枚举的范围是什么？是所有的内容都需要枚举吗？

• 3.选择合适的枚举顺序 从前往后，还是从后往前进行枚举

枚举算法常见题型：

基础枚举

• 数值枚举：遍历区间[1，n]，筛选满足条件的数（如被3整除且名各位和为偶数）
• 字符串枚举：遍历字符/字符串集合，匹配特定模式（如以指定字母开头且长度为偶数）。

  组合枚举

• 子集枚举：用位运算/递归枚举集合子集，筛选符合条件的子集（如元素和能被k整除）
• 排列枚举：通过回溯生成全排列，筛选符合条件的排列（如无重复数字且能被指定数整除）。

  算法结合

• 枚举+贪心：枚举关键状态后应用贪心策略（如任务分配顺序枚举+贪心资源分配）。
• 枚举+动态规划：枚举状态后用DP求解子问题（如背包容量枚举+DP计算最优解）。

  场景枚举

• 生活场景：枚举活动组合，求解最大兼容活动数（如时间安排问题）。
• 游戏场景：枚举移动方向，搜索迷宫路径（如BFS/DFS遍历方向）。

贪心

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

贪心算法的使用前提：局部最优解一定能导致全局最优解

例：有一堆钞票，你可以拿走十张，如果想达到最大的金额你要怎么拿？

解题步骤：

• 1.将问题分解为若干个子问题
• 2.找出适合的贪心策略
• 3.求解每一个子问题的最优解
• 4.将局部最优解堆叠成全局最优解

使用贪心一定要证明，一般有两种方法：数学归纳法、反证法

实际做题过程中，数学归纳较为麻烦，我们需要大胆假设，小心求证。找到一组反例 就可以推翻贪心！

二分