Simulation
一、模块核心定位与学习目标
1. 模拟题型的本质
模拟题不依赖复杂算法,核心是将题目描述的“过程”转化为代码逻辑,直接复现操作步骤,重点考察:
对 C++ 基础语法(循环、数组、输入输出)的熟练运用。
对题目细节的把控能力(如边界条件、操作顺序)。
对内置数据结构(如数组、动态数组)的基础操作。
2. 青铜级适用场景
在 USACO 青铜级中,模拟题是“保底题型”,当题目要求“求某个过程的最终结果”或“判断某个事件何时发生”时,朴素模拟(不优化时间复杂度)通常即可AC(因青铜级数据规模小,无需担心超时)。
3. 参考资源
模块内容基于 Darren Yao 著作的第 5 章(IUSACO 5 - Simulation),该资源是 USACO 备考经典资料,侧重实战性讲解。
二、经典实例解析(含完整思路与代码)
网页提供 2 道青铜级基础模拟题,覆盖“状态更新”和“资源转移”两类典型场景,是模拟题的入门范本。
1. 实例 1:Shell Game(贝壳游戏)
http://oj.oldmoon.cn/p/U1819JB1
(1)题目背景(青铜 - Easy)
场景:有 3 个位置,每个位置下藏 1 个贝壳;Bessie 会多次交换两个位置的贝壳,Elsie 会多次猜测某个位置是否有贝壳。
目标:计算 Elsie 最多能猜对多少次(即某个贝壳被猜测的总次数)。
(2)解题思路
核心是“用数组跟踪贝壳位置,模拟交换与猜测过程”:
1. 状态存储:用数组 shell 记录每个位置(索引 0/1/2)对应的贝壳编号(如 shell[0] = 1 表示位置 0 下是贝壳 1)。
2. 模拟交换:每次交换两个位置时,直接交换数组中对应索引的元素(如交换位置 a 和 b,执行 swap(shell[a], shell[b]))。
3. 统计猜测次数:用另一个数组 count 记录每个贝壳被猜测的次数(如 Elsie 猜位置 x,就将 count[shell[x]]++)。
4. 求最大值:最终 count 数组的最大值即为 Elsie 最多能猜对的次数。
(3)完整代码实现
#include <algorithm>
#include <cstdio>
#include <vector>
using std::vector;
int main() {
freopen("shell.in", "r", stdin); // 读取输入文件(USACO 竞赛常用)
freopen("shell.out", "w", stdout); // 写入输出文件
int n;
scanf("%d", &n); // 读取交换+猜测的总次数
vector<int> shell = {0, 1, 2}; // 初始状态:位置0→贝壳0,位置1→贝壳1,位置2→贝壳2
vector<int> count(3, 0); // 统计每个贝壳被猜测的次数,初始为0
for (int i = 0; i < n; ++i) {
int a, b, g;
scanf("%d %d %d", &a, &b, &g); // 读取交换的两个位置a、b,以及猜测的位置g(注意:题目输入可能是1-based,需转0-based)
a--; // 转为0-based索引(若题目输入是1-based)
b--;
g--;
swap(shell[a], shell[b]); // 模拟交换贝壳
count[shell[g]]++; // 统计当前猜测位置对应的贝壳被猜次数
}
// 输出最大猜测次数
int max_count = std::max({count[0], count[1], count[2]});
printf("%d\n", max_count);
return 0;
}2. 实例 2:Mixing Milk(混合牛奶)
http://oj.oldmoon.cn/p/U1819DB1
(1)题目背景(青铜 - Easy)
场景:有 3 个桶,每个桶有最大容量(固定)和当前牛奶量;执行 100 次操作,每次将一个桶的牛奶倒入另一个桶。
目标:模拟所有操作后,输出每个桶的最终牛奶量。
(2)解题思路
核心是“计算每次倒奶的实际量,更新两个桶的牛奶状态”:
1. 状态存储:用两个数组分别记录“桶的最大容量”(c,固定不变)和“桶的当前牛奶量”(m,随操作更新)。
2. 关键计算:每次从桶 i 倒奶到桶 j 时,实际倒奶量 = min(桶 i 当前牛奶量 m[i], 桶 j 剩余空间 c[j] - m[j])(避免倒超或倒空)。
3. 状态更新:桶 i 的牛奶量减去实际倒奶量(m[i] -= pour),桶 j 的牛奶量加上实际倒奶量(m[j] += pour)。
4. 循环执行:重复 100 次操作,最终输出 m 数组。
(3)完整代码实现
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
const int N = 3; // 桶的数量(固定为3)
const int TURN_NUM = 100; // 操作总次数(固定为100)
int main() {
freopen("mixmilk.in", "r", stdin);
freopen("mixmilk.out", "w", stdout);
vector<int> c(N); // 存储每个桶的最大容量
vector<int> m(N); // 存储每个桶的当前牛奶量
for (int i = 0; i < N; ++i) {
cin >> c[i] >> m[i]; // 读取每个桶的容量和初始牛奶量
}
for (int turn = 0; turn < TURN_NUM; ++turn) {
int from = turn % N; // 倒奶的桶(循环:0→1→2→0→...)
int to = (turn + 1) % N;// 接奶的桶(循环:1→2→0→1→...)
int pour = min(m[from], c[to] - m[to]); // 计算实际倒奶量
m[from] -= pour; // 倒奶桶减少
m[to] += pour; // 接奶桶增加
}
// 输出每个桶的最终牛奶量
for (int milk : m) {
cout << milk << endl;
}
return 0;
}三、分级练习题推荐
网页按难度将模拟题分为“Easier(简单)”和“Harder(较难)”两类,覆盖不同场景的模拟需求,建议按难度梯度练习,巩固解题思路。
1. Easier(简单题,青铜入门必刷)
这类题目操作流程直接,边界条件少,适合刚学模拟的初学者,共 5 道:
题目名称 | 难度 | 核心考点 | 解题关键 |
|---|---|---|---|
The Cow-Signal | Easy | 字符图案放大 | 按题目给定的放大比例,重复输出每行字符(横向放大)和每一行(纵向放大)。 |
Speeding Ticket | Easy | 速度检测 | 遍历每段路程的速度,判断是否超过限速,统计超速次数。 |
The Lost Cow | Easy | 位置移动模拟 | 模拟奶牛的移动方向和距离,直到找到目标位置,计算总移动路程。 |
The Bovine Shuffle | Easy | 洗牌后的位置跟踪 | 用数组记录每次洗牌后每个位置的元素变化,模拟多次洗牌后的最终状态。 |
The Bucket List | Easy | 桶的牛奶分配与转移 | 按题目规则分配牛奶到桶中,处理“桶满溢出”的边界条件,统计最终结果。 |
2. Harder(较难题,青铜进阶练习)
这类题目操作更复杂(如循环操作、多状态同步),或需处理更多边界条件,共 9 道,按难度进一步细分:
难度等级 | 题目名称 | 核心考点 | 解题关键 |
|---|---|---|---|
Normal | Measuring Traffic | 交通流量统计 | 模拟不同路段的车辆进出,处理“拥堵”“分流”等条件,计算最终流量。 |
Normal | Circular Barn | 环形谷仓的牛分配 | 模拟牛在环形谷仓中的移动,确保每个谷仓的牛数量不超过容量,记录分配结果。 |
Normal | Block Game | 方块放置与碰撞 | 模拟方块在网格中的放置过程,判断是否与已有方块碰撞,统计可放置数量。 |
Normal | Team Tic Tac Toe | 团队井字棋胜负判断 | 模拟多轮下棋过程,检查每行、每列、对角线是否满足获胜条件。 |
Normal | Mowing the Field | 草坪修剪路径跟踪 | 记录修剪机的移动路径,判断是否重复修剪同一区域,计算首次重复的时间。 |
Normal | Reflection | 光线反射模拟 | 模拟光线在矩形边界的反射方向变化,计算光线射出矩形的位置和方向。 |
Hard | Censoring | 字符串过滤(旧青铜题) | 模拟字符串的输入与过滤,删除包含敏感词的子串,处理过滤后的字符串拼接。 |
Hard | Milk Measurement | 牛奶产量统计与排名 | 跟踪多户农场的牛奶产量变化,实时更新排名,统计排名变化的次数。 |
Very Hard | Stuck in a Rut | 奶牛移动阻塞模拟 | 模拟多只奶牛的移动,处理“相互阻塞”的情况,计算每只奶牛最终的移动距离。 |