信息学竞赛 C++ 教材

Appearance

第 33 章 现实仿真——模拟进阶 ​

🏗️ 前情回顾：M2 阶段你第一次接触模拟——按照题目描述一步步执行即可。那时你还只会处理"一条线走到底"的简单情景。但现实世界比那复杂得多——环形结构、时间线推进、复杂规则判断……这一章，我们要学会用代码"复现"一切。

🎯 本章目标 ​

学完这一章，你能：

  • 掌握大模拟的四步法：读题→提取规则→设计数据结构→逐条实现
  • 处理环形结构中的下标移动（取模）
  • 理解时间线模拟（事件驱动）和规则型模拟
  • 实现玩具谜题、乒乓球计分、多项式输出、扫雷等经典模拟题

📖 故事引入 ​

假设你是游戏设计师，老板说："做一个扫雷游戏。"

你看着屏幕上密密麻麻的格子陷入沉思——鼠标点一下，自动展开一大片空白区域；每个格子显示周围有多少雷；踩雷了游戏结束，数字都翻开就算赢。这背后全是规则，每一条都要在代码里体现。

又比如说，你和朋友打乒乓球。11 分制，10:10 后要领先 2 分才算赢。一局结束后重新开始。裁判怎么记分？换做代码——你需要跟踪双方的得分、处理"追平后领先两分"的规则、判断比赛何时结束。

这些问题的共同点是：规则明确但琐碎，数据结构简单但逻辑复杂。解决它们不需要高深的数学，需要的是——耐心、细致、和一套"把现实映射到代码"的方法论。

🧱 知识讲解 ​

33.1 大模拟四步法 ​

面对一道大模拟题，不要一上来就写代码。按这四步走：

① 读题 → 用笔圈出所有规则、限制、边界情况
② 提取规则 → 整理成简洁的要点列表
③ 设计数据结构 → 选最合适的数组/结构体/变量
④ 逐条实现 → 把规则一条条翻译成代码，写完就测

📦 类比：大模拟就像组装乐高城堡。你不能抓起一堆零件就拼——先看清图纸（读题），理解每一层的结构（提取规则），准备好对应颜色的积木块（数据结构），然后一层一层往上搭（逐条实现）。

33.2 环形模拟：玩具谜题 ​

环形结构最简单的处理方式就是取模（%）。

题目（NOIP 2016 提高组 Day1）：「玩具谜题」——n 个小人围成一圈，每个小人朝内或朝外。给定若干条指令"向左/向右数 s 个人"，小人朝内朝外影响左右方向。问最后指向谁。

核心规则整理：

  • 小人朝内（0）：左是顺时针，右是逆时针
  • 小人朝外（1）：左是逆时针，右是顺时针
  • 朝内朝外 + 左右方向 → 实际是顺时针还是逆时针

方向合并技巧：令 d = 朝内朝外 ^ 左右方向（异或），d == 0 表示顺时针，d == 1 表示逆时针。这样就免去了 if-else 的四重嵌套。

cpp
int n, m;
int dir[100005];      // 0=朝内，1=朝外
string name[100005];  // 小人名字

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> dir[i] >> name[i];

    int pos = 0;  // 当前指向的小人
    for (int i = 0; i < m; i++) {
        int a, s;  // a: 0=左, 1=右; s: 步数
        cin >> a >> s;
        if ((dir[pos] ^ a) == 0)  // 顺时针
            pos = (pos + s) % n;
        else                       // 逆时针
            pos = (pos - s % n + n) % n;
    }
    cout << name[pos] << endl;
    return 0;
}

⚠️ 环形移动公式：顺时针走 s 步：pos = (pos + s) % n；逆时针走 s 步：pos = (pos - s % n + n) % n。注意逆时针时的 + n 是为了处理负数取模。

33.3 规则型模拟：乒乓球 ​

题目（NOIP 2003 普及组）：乒乓球比赛 11 分制和 21 分制。输入一个由 'W'（华华赢）和 'L'（对手赢）组成的字符串。输出两种赛制下完整的比分记录。规则：一局结束后（一方得分 ≥ 11 / 21 且领先 ≥ 2 分），输出该局比分并开始下一局。输入以 'E' 结束。

cpp
string s, all;
int main() {
    while (cin >> s) all += s;  // 读入所有字符（'E' 也会被读入）
    
    auto solve = [&](int limit) {
        int w = 0, l = 0;
        for (char c : all) {
            if (c == 'E') break;
            if (c == 'W') w++; else l++;
            if ((w >= limit || l >= limit) && abs(w - l) >= 2) {
                cout << w << ":" << l << endl;
                w = l = 0;
            }
        }
        cout << w << ":" << l << endl;  // 最后一局（可能未完成）
    };
    
    solve(11); cout << endl;
    solve(21);
    return 0;
}

关键点：Lambda 表达式 auto solve = [&](int limit) { ... } 让你用同一个函数处理两种赛制，避免重复代码。

33.4 格式型模拟：多项式输出 ​

题目（NOIP 2009 普及组）：给定一元 n 次多项式的系数，按规范格式输出多项式字符串。规则包括：系数为 0 的项不输出；最高次项系数为 1 时不输出系数（但输出 "x"）；常数项只输出数字；负号直接输出；第一项正号不输出……

这类题的核心是把特殊情况列全，逐一处理：

cpp
void printPoly(int n, int a[]) {
    bool first = true;
    for (int i = n; i >= 0; i--) {
        if (a[i] == 0) continue;  // 系数 0，不输出

        // 符号处理
        if (!first) {
            cout << (a[i] > 0 ? "+" : "-");
        } else {
            if (a[i] < 0) cout << "-";
            first = false;
        }
        
        int absCoef = abs(a[i]);
        // 系数为 1 且不是常数项时不输出系数
        if (i > 0 && absCoef == 1) {
            cout << "x";
        } else {
            cout << absCoef;
            if (i > 0) cout << "x";
        }
        // 指数 > 1 时输出 ^
        if (i > 1) cout << "^" << i;
    }
}

📦 类比：格式输出题就像考试中的"格式规范题"——不是考你思维深度，而是考你细心程度。把所有情况列在纸上，一条条对照检查，别靠脑子硬想。

33.5 二维模拟：扫雷 ​

扫雷是典型的二维数组模拟题。

题目简化版：给定 n×m 的雷区（* 表示雷，? 表示非雷），输出每个非雷格周围 8 个方向上的雷数。

cpp
int n, m;
char mp[105][105];
int ans[105][105];

int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> mp[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (mp[i][j] == '*') {
                ans[i][j] = -1;  // 标记为雷
                continue;
            }
            int cnt = 0;
            for (int k = 0; k < 8; k++) {
                int nx = i + dx[k], ny = j + dy[k];
                if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny] == '*')
                    cnt++;
            }
            ans[i][j] = cnt;
        }
    // 输出 ans……
}

这里用了方向数组 dx[8] / dy[8]，避免写 8 段重复的判邻代码。

💡 在实际的 Windows 扫雷中，点击到数字 0 的格子会自动展开周围的空白区域——这个是在此基础上增加了 BFS/DFS 搜索，但二维计雷的核心就是上面这些。

✋ 动手试试 ​

试试 1：简化版"玩具谜题"——n 个人站成一排（不是一圈），每个人说"我左边第 s 个人穿了红衣服"。输入 n 条指令，输出结束时指向谁。

试试 2：写一个简化版"乒乓球"——只有 11 分制，输入一个 W/L 字符串，输出最终比分。

试试 3：用方向数组（不写 8 个 if）实现扫雷。

⚠️ 容易犯的错 ​

错 1：环形移动时忘了 +n ​

❌ pos = (pos - s) % n; ——当 s > pos 时，结果会变成负数（或 0），导致越界。

✅ pos = (pos - s % n + n) % n; ——永远保证非负。

错 2：大模拟一上来就写代码 ​

❌ 读一遍题就直接敲键盘，写到一半发现忘了处理"10:10 后领先两分"的规则，推倒重来。

✅ 先列出所有规则要点，然后设计数据结构，最后逐条翻译为代码。

错 3：格式输出题漏掉特殊情况 ​

❌ "系数为 1 应该省略"这条忘了，输出 1x^2 + 1x + 1。

✅ 列一张"特殊情况检查表"：系数 0、系数 1、系数 -1、常数项、最高次项、负号位置……

错 4：二维数组方向枚举时下标写死 ​

❌ 写 8 段 if (mp[i-1][j-1] == '*') cnt++; if (mp[i-1][j] == '*') cnt++; ... ——代码又长又容易漏。

✅ 用 dx[8] / dy[8] 数组 + 一个循环搞定。

📝 练习 ​

基础题 ​

1. 选择题

（1）环形数组中从位置 p 逆时针走 k 步到位置：
A. (p + k) % n   B. (p - k) % n   C. (p - k + n) % n   D. (p + k - n) % n

（2）大模拟的最佳实践顺序是：
A. 写代码→读题→调试→改代码   B. 读题→提取规则→设计数据结构→实现   C. 设计数据结构→写代码→读题→测试   D. 直接写代码

（3）扫雷中判断 8 个邻格，以下哪种写法最好？
A. 写 8 段 if   B. 写 8 个独立循环   C. 方向数组 + 一个循环   D. 递归

2. 填空题

（1）(5 - 7 % 5 + 5) % 5 的结果是 ____。

（2）乒乓球 11 分制结束一局的条件是：一方 ≥ 11 且 ____。

（3）方向数组中 dx 和 dy 下标相同的元素构成一个 ____。

提高题 ​

3. 编程题 — 报数游戏

n 个人围成一圈（编号 1~n），从第 1 个人开始报数，报到 m 的人出列。下一个人重新从 1 开始报数，直到所有人出列。按出列顺序输出编号。

4. 编程题 — 蛇形填数

输入 n，在 n×n 的二维数组中按顺时针螺旋填入 1 到 n²。例如 n=3 输出：

1 2 3
8 9 4
7 6 5

挑战题 ​

5. 编程题 — 弹珠游戏

一个 n×m 的网格，给定弹珠的初始位置和方向（上/下/左/右）。弹珠碰到边界会反弹（方向取反），给定步数 k，输出弹珠最终位置。如果弹珠进入角落（两个方向同时反弹），要正确处理。

6. 编程题 — 生命游戏

实现康威生命游戏（Conway's Game of Life）简化版：n×m 网格，活细胞 1，死细胞 0。规则：活细胞周围有 2 或 3 个活邻居则存活，否则死亡；死细胞周围恰好有 3 个活邻居则复活。输入初始状态和迭代次数 t，输出 t 代后的状态。

🧠 本章小结 ​

模拟进阶 = 把现实世界搬进代码

四步法：
  ① 读题圈规则 → ② 提取要点列表 → ③ 设计数据结构 → ④ 逐条翻译

环形模拟：
  pos = (pos + step) % n          顺时针
  pos = (pos - step % n + n) % n  逆时针

规则型模拟：
  列出所有规则、盯紧边界条件、Lambda 减少重复

格式型模拟：
  列"特殊情况检查表"、逐项打钩

二维模拟：
  方向数组 dx[8]/dy[8] 避免重复代码

模拟题的难点不在算法，在于细心和耐心！

📝 配套练习 ​

共7题。NOIP真题密集——P1042(乒乓球)/P1067(多项式)/P1563(玩具谜题)都是真题，大题量练大模拟的耐心和准确度。。★核心（课堂必做） ◆拓展（课后练习）

级别题号链接覆盖知识点
★ 核心luogu-P1042https://hydro.ac/p/luogu-P1042大模拟、计分规则、11分/21分
◆ 拓展luogu-P1067https://hydro.ac/p/luogu-P1067格式输出、多项式、检查表
◆ 拓展luogu-P1328https://hydro.ac/p/luogu-P1328规则表格、石头剪刀布扩展
◆ 拓展luogu-P1563https://hydro.ac/p/luogu-P1563环形取模、异或方向
◆ 拓展luogu-P1518https://hydro.ac/p/luogu-P1518大模拟、两只牛、方向+步数
◆ 拓展luogu-P1031https://hydro.ac/p/luogu-P1031平均分、贪心模拟
◆ 拓展luogu-P1012https://hydro.ac/p/luogu-P1012排序模拟、字符串拼接

💡 练习建议：先完成 1 道★核心题，确保掌握本章基本方法；再完成 6 道◆拓展题，覆盖不同变式和细节。

配套练习 ​

共7题。NOIP真题密集——P1042(乒乓球)/P1067(多项式)/P1563(玩具谜题)都是真题，大题量练大模拟的耐心和准确度。★核心（课堂必做） · ◆拓展（课后练习）

级别题号链接覆盖知识点
★ 核心luogu-P1042https://hydro.ac/p/luogu-P1042大模拟、计分规则、11分/21分
◆ 拓展luogu-P1067https://hydro.ac/p/luogu-P1067格式输出、多项式、检查表
◆ 拓展luogu-P1328https://hydro.ac/p/luogu-P1328规则表格、石头剪刀布扩展
◆ 拓展luogu-P1563https://hydro.ac/p/luogu-P1563环形取模、异或方向
◆ 拓展luogu-P1518https://hydro.ac/p/luogu-P1518大模拟、两只牛、方向+步数
◆ 拓展luogu-P1031https://hydro.ac/p/luogu-P1031平均分、贪心模拟
◆ 拓展luogu-P1012https://hydro.ac/p/luogu-P1012排序模拟、字符串拼接

练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 6 道◆拓展题，覆盖不同变式和细节。

自查清单：

  • [ ] 我掌握了大模拟的四步法（读题→规则→数据→实现）
  • [ ] 我能正确处理环形结构中的下标移动
  • [ ] 我会用方向数组简化二维邻格判断
  • [ ] 我能独立实现玩具谜题、乒乓球计分
  • [ ] 我知道格式型模拟要列"特殊情况检查表"
  • [ ] 面对复杂规则时，我会先整理再写代码，不冲动编程

🚀 下章预告：模拟和枚举很多时候需要 O(n²) 甚至更高复杂度。能不能更快？下一章《两只手指——双指针》，你将学会用两个游走的指针把 O(n²) 压缩到 O(n)，感受"算法优化"第一次带来的爽感！👆👇