登录

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

http://oj.oldmoon.cn/p/U1617DB3

Easy

字符图案放大

按题目给定的放大比例,重复输出每行字符(横向放大)和每一行(纵向放大)。

Speeding Ticket

http://oj.oldmoon.cn/p/U1516DB2

Easy

速度检测

遍历每段路程的速度,判断是否超过限速,统计超速次数。

The Lost Cow

http://oj.oldmoon.cn/p/U1617OB1

Easy

位置移动模拟

模拟奶牛的移动方向和距离,直到找到目标位置,计算总移动路程。

The Bovine Shuffle

http://oj.oldmoon.cn/p/U1718DB2

Easy

洗牌后的位置跟踪

用数组记录每次洗牌后每个位置的元素变化,模拟多次洗牌后的最终状态。

The Bucket List

http://oj.oldmoon.cn/p/U1819DB2

Easy

桶的牛奶分配与转移

按题目规则分配牛奶到桶中,处理“桶满溢出”的边界条件,统计最终结果。

2. Harder(较难题,青铜进阶练习)

这类题目操作更复杂(如循环操作、多状态同步),或需处理更多边界条件,共 9 道,按难度进一步细分:

难度等级

题目名称

核心考点

解题关键

Normal

http://oj.oldmoon.cn/p/U1819FB3

Measuring Traffic

交通流量统计

模拟不同路段的车辆进出,处理“拥堵”“分流”等条件,计算最终流量。

Normal

http://oj.oldmoon.cn/p/U1516FB2

Circular Barn

环形谷仓的牛分配

模拟牛在环形谷仓中的移动,确保每个谷仓的牛数量不超过容量,记录分配结果。

Normal

http://oj.oldmoon.cn/p/U1617DB2

Block Game

方块放置与碰撞

模拟方块在网格中的放置过程,判断是否与已有方块碰撞,统计可放置数量。

Normal

Team Tic Tac Toe

团队井字棋胜负判断

模拟多轮下棋过程,检查每行、每列、对角线是否满足获胜条件。

Normal

Mowing the Field

草坪修剪路径跟踪

记录修剪机的移动路径,判断是否重复修剪同一区域,计算首次重复的时间。

Normal

Reflection

光线反射模拟

模拟光线在矩形边界的反射方向变化,计算光线射出矩形的位置和方向。

Hard

Censoring

字符串过滤(旧青铜题)

模拟字符串的输入与过滤,删除包含敏感词的子串,处理过滤后的字符串拼接。

Hard

Milk Measurement

牛奶产量统计与排名

跟踪多户农场的牛奶产量变化,实时更新排名,统计排名变化的次数。

Very Hard

Stuck in a Rut

奶牛移动阻塞模拟

模拟多只奶牛的移动,处理“相互阻塞”的情况,计算每只奶牛最终的移动距离。

登录