这篇文章，将要介绍模拟，并且准备了四道题目（P1007 独木桥普及- 、P2777 [AHOI2016初中组] 自行车比赛普及/提高- P1518 [USACO2.4] 两只塔姆沃斯牛 The Tamworth Two 普及/提高-、P1582 倒水普及+/提高）循序渐进介绍模拟。

总领

按照wiki上的定义，它是这样子的。

程令计算机按照题目中的要求操作。

当然，在大部分情况下，模拟就是让你去完成题目里面的一系列操作。可是这并不意味着模拟程序就只有这些——相反，模拟可能雨任何一种其他的算法同时出现，或者说你要仔细的思考奇怪的优化方法才可以下手。这样一来，按照题目的要求操作可能是最后一步。

模拟的特点有很多，比如如下几点：

代码量大
操作繁多
复杂。

反正总结一下，就不是什么好东西。很容易就写错代码而且找不出来错。

当然，在做这一类算法题的时候会有一定的技巧，我们可以尽可能的做到如下几点：

在注释或草稿纸上写好过程，并时时刻刻按照过程写代码，一定要做到思路清晰。
动手写的时候，尽量用函数或结构体等将代码模块化，便于改错也利于思路清晰
减少各种概念的混淆，写好注释，尽量将可以转化的概念转化，如时间单位等

题目

由于这类题目没有固定的代码或者套路可以寻找，所以我们就从题目中学习和寻找方法。

P1007 独木桥

普及-

先来找一道简单一点的题目上手。

先看一下题目。

题目的大致意思就是一个只能通过一个人的独木桥，上面有若干士兵。你现在只知道每个士兵的位置，并且知道士兵在独木桥上相遇的时候会掉头走，求所有士兵离开独木桥的最大时间和最小时间。

首先先思考一下，这道题似乎最关键的点就是只能一个人同行——也是这道题目最麻烦的点。

两个人互相通过，只能掉头回去，这是这道题目最难模拟的部分。但是我们可以逆向来思考，从独木桥上方看，两个人遇到对方掉头走和两个人穿过对方继续走似乎毫无区别。

这也就是这个题目最关键的地方，想通了这一点，就很好做下面的部分了。

我们再来分析最大值和最小值。

最大值就是「每个士兵的最大值」中的最大值。「每个士兵的最大值」即士兵向左走的路程和向右走的路程中的 $max$ 值

而最小值是「每个士兵的最小值」中的最大值。注意⚠️这个位置比较坑，「每个士兵的最小值」很好理解，不过多做解释。但是为什么要取最大值呢？因为当所有的士兵都走完了才可以称为「完成」，计算总时间，而所有士兵走完的时间即为最慢的那个——也就是最大值的那个。

所以，我们就可以得到如下核心代码

cpp
for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    maxx = max(maxx, max(a, l - a + 1));
    minn = max(minn, min(a, l - a + 1));
}

P2777 [AHOI2016初中组] 自行车比赛

普及/提高-

这个题目的大致意思就是说每个人得到的积分数就是 总人数-排名数+1，也就是说排的越靠前，积分越高。现在问最后一场比赛哪些人有可能夺得桂冠。

首先我们要明白，在这道题目中可以无限制的假设，创造自己想要的环境。因为我们讨论的都是是否有可能。所以我们只要创建出任意一种情景使得 $A$ 得到第一名就可以了。换句话说，就是「万物皆有可能」。

这道题要用一种极限思维——或者说是一种贪心的感觉。如我们要计算 $A$ 号选手，我们设现在积分最高的是 $B$ 号选手。那么，我们就会假设 $A$ 得到第一且 $B$ 得到最后一名，第二名得到倒数第二名等以此类推。在这种情况下是否为 $A$ 高，如果是，那么 $A$ 就可能获得第一名。

这种思想是否正确呢？首先，我们可以证明在上述条件下（ $A$ 的成绩比 $B$ 高）， $A$ 会比第一名高。那么第二名呢？由于第二名是在这一场比赛中得到了倒数第二名，所以它加的分数也就只比第一名多一分。但是由于它之前的分数可能和之前的人重合，也就是说可能和第一名一样高——所以说这种算法不成立。

不过基本的思想是对的，我们要让「 $A$ 得到第一且 $B$ 得到最后一名，第二名得到倒数第二名等以此类推」，但是我们不能只比较第一名，而是要和每个人比较。

就这样，一个思路呈现在了我们面前。

首先，输出过后让整个数组排序（由于我们最后要求的是数量，所以数组的原始顺序并不需要备份）

cpp
sort(a + 1, a + 1 + n);

然后，我们依次让第一名加到最小的分，最后一名加到最大的分。在这个过程中，我们只要记录其中的最大值就可以了。因为超过了最大值，就相当于得到了冠军，超过了他们全部。

cpp
for (int i = 1; i <= n; i++) {
    maxx = max(maxx, a[i] + n - i + 1);
}

最后，用每个选手依次去比。比的方式就是加上 $n$ （第一名的奖励）和 maxx 比较，如果「大于等于」，即得到第一名

cpp
for (int i = n; i >= 1; i--) {
    if (a[i] + n >= maxx)
        cnt++;
    else
        break;
}

就这样，我们又完成了一道题目。

P1518 [USACO2.4] 两只塔姆沃斯牛 The Tamworth Two

普及/提高-

这个题目算法标签里面并没有「图论」，所以我尽量不使用图论的一些简洁写法，极致体验模拟的意蕴。

当然，如果你学过图论，或者在考场中遇到这种题目，你是用图论的简洁写法当然是没有问题的。

好，进入题目。这道题目规定了两个物体（我们就不使用情景的复杂表示方式了）的移动规则。问是否可以相遇。

这种题目可以算是纯模拟——没有任何算法上的优化，但是必须要理清楚思路才可以。

在前面介绍模拟的时候，我曾说过如下技巧

动手写的时候，尽量用函数或结构体等将代码模块化，便于改错也利于思路清晰

所以，我们尽量用模块化的方式来写。为了便于查看，我也会在书写教程时给每个部分分小标题，你可以从右侧目录点击查看。

输入

在输入的时候，我们要得出两个物体的初始位置。而且由于这两个物体会动，所以我们不妨把它们两个的位置直接处理为成 . (空地)，方便后期处理。

cpp
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        cin >> c[i][j];
        if (c[i][j] == 'F') {
            c[i][j] = '.';
            fx = i, fy = j;
        }
        if (c[i][j] == 'C') {
            c[i][j] = '.';
            cx = i, cy = j;
        }
    }
}

主函数运行

根据题目的意思，我们要计算它们相遇的时间，也就是说，我们要用一个 while 函数不停的运行，每次 cnt++; 。

cpp
while (check()) {
    write();
    cnt++;
    next(fx, fy, ft);
    next(cx, cy, ct);
}

其中的 check函数是为了判断是否符合结束的条件，而write 函数则是为了辅助 check 运行的，我稍后会把两个放在一块讲。

而cnt++;则是为了记录相遇的时间，为题目所求

next(fx, fy, ft);和next(cx, cy, ct);是为了移动两个物体，两个物体的移动方案是一样的，所以我们只要写一个函数，统一带入两个物体的参数分别执行就可以了。

`check` 和 `write` 函数的判断操作

首先，由于我们的 check 是放在 while 的判断栏里面的，，所以当我们判断出来程序应该结束的时候，我们就让我们的 check 函数返回 0 即可。

然后，我们来计算一下何时程序结束

当两个物体在同一个位置，也就是互相找到的时候，程序就结束了。这个代码比较好些，就是判断两个坐标是否相等

cpp
if (fx == cx && fy == cy) {
    cout << cnt;
    return 0;
}

其次，当它们永远不能相遇的时候，同样程序也会结束。如何判断呢？如果它们运行的状态和以前的某个时刻一样时，那么它们必定不能相遇，因为运行的轨迹就进入了死循环，所以二者不能相遇。至于如何记录二者的状态，我们可以用一个数字来记录，每个数位为一个关键量（两个物体的x，y要减一，因为它们本来的范围是 1~10 减掉后就是 0~9了。

我们准备一个数组记录这个数值是否被走过，如bool t[1000000];

每次走的时候，我们可以记录一下当前的状态，用 write 函数

cpp
void write() {
    // 记录现在这个状态
    long long temp;
    temp =
        (fx - 1) + (fy - 1) * 10 + ft * 100 + (cx - 1) * 1000 + (cy - 1) * 10000 + ct * 100000;
    t[temp] = 1;
}

而判断这个路径是否被走过则为

cpp
long long temp;
temp =
    (fx - 1) + (fy - 1) * 10 + ft * 100 + (cx - 1) * 1000 + (cy - 1) * 10000 + ct * 100000;
if (t[temp]) {
    cout << 0;
    return 0;
}

所以整个 check 函数为

cpp
bool check() {
    // 查是否结束了
    // 结束分为两种：和之前的状态重复（永远找不到）、找到了。
    // 不管是哪一种状态，都返回1跳出while
    // 在这个函数中输出
    if (fx == cx && fy == cy) {
        cout << cnt;
        return 0;
    }
    long long temp;
    temp =
        (fx - 1) + (fy - 1) * 10 + ft * 100 + (cx - 1) * 1000 + (cy - 1) * 10000 + ct * 100000;
    if (t[temp]) {
        cout << 0;
        return 0;
    }
    return 1;
}

`next`函数和物体的移动

首先，我们要来介绍一个知识，就是函数传入参数。

当我们在函数名前增加 &时，它就会影响到传入的变量本身。

举一个例子。

cpp
#include <bits/stdc++.h>
using namespace std;
void jia(int &a) { a++; }
int main() {
    int a = 1, b = 2, c = 3;
    jia(a), jia(b), jia(c);
    cout << a << " " << b << " " << c;
    return 0;
}

这个程序输出的就是 2 3 4 明白了吧。

然后，我们来写next 函数，程序就可以这样设计框架

cpp
void next(int &x, int &y, int &t) {……}

那么这个时候，我们要根据其传入的方向来判断下一步时什么，我们定义一个 tx 和 ty 来记录下一步的坐标。

cpp
int tx = x, ty = y;
if (t == 0)
    tx--;
else if (t == 1)
    ty++;
else if (t == 2)
    tx++;
else if (t == 3)
    ty--;

但是下一步是否可行？如果下一步在边界上或者在障碍物上则不可以行走，这个时候我们就调整一下方位。否则就可以走

cpp
if (tx == 0 || tx == n + 1 || ty == 0 || ty == n + 1) {
    t++;
    if (t == 4)
        t = 0;
} else if (c[tx][ty] == '*') {
    t++;
    if (t == 4)
        t = 0;
} else {
    x = tx, y = ty;
}

就这样，我们就可以得出完整的 next 函数

cpp
void next(int &x, int &y, int &t) {
    // 自动移动
    int tx = x, ty = y;
    if (t == 0)
        tx--;
    else if (t == 1)
        ty++;
    else if (t == 2)
        tx++;
    else if (t == 3)
        ty--;

    if (tx == 0 || tx == n + 1 || ty == 0 || ty == n + 1) {
        t++;
        if (t == 4)
            t = 0;
    } else if (c[tx][ty] == '*') {
        t++;
        if (t == 4)
            t = 0;
    } else {
        x = tx, y = ty;
    }
    return;
}

总体

这个程序的函数比较多，所以我们一起来看一下整体的程序，屏凑一下各个部分

cpp
#include <bits/stdc++.h>
using namespace std;
char c[12][12]; // 地图
int fx, fy, ft;
int cx, cy, ct;
bool t[1000000];
int cnt;
int n = 10;
void write() {
    // 记录现在这个状态
    long long temp;
    temp =
        (fx - 1) + (fy - 1) * 10 + ft * 100 + (cx - 1) * 1000 + (cy - 1) * 10000 + ct * 100000;
    t[temp] = 1;
}
bool check() {
    // 查是否结束了
    // 结束分为两种：和之前的状态重复（永远找不到）、找到了。
    // 不管是哪一种状态，都返回1跳出while
    // 在这个函数中输出
    if (fx == cx && fy == cy) {
        cout << cnt;
        return 0;
    }
    long long temp;
    temp =
        (fx - 1) + (fy - 1) * 10 + ft * 100 + (cx - 1) * 1000 + (cy - 1) * 10000 + ct * 100000;
    if (t[temp]) {
        cout << 0;
        return 0;
    }
    return 1;
}
void next(int &x, int &y, int &t) {
    // 自动移动
    int tx = x, ty = y;
    if (t == 0)
        tx--;
    else if (t == 1)
        ty++;
    else if (t == 2)
        tx++;
    else if (t == 3)
        ty--;

    if (tx == 0 || tx == n + 1 || ty == 0 || ty == n + 1) {
        t++;
        if (t == 4)
            t = 0;
    } else if (c[tx][ty] == '*') {
        t++;
        if (t == 4)
            t = 0;
    } else {
        x = tx, y = ty;
    }
    return;
}
int main() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> c[i][j];
            if (c[i][j] == 'F') {
                c[i][j] = '.';
                fx = i, fy = j;
            }
            if (c[i][j] == 'C') {
                c[i][j] = '.';
                cx = i, cy = j;
            }
        }
    }
    while (check()) {
        write();
        cnt++;
        next(fx, fy, ft);
        next(cx, cy, ct);
    }
    return 0;
}

就这样，又解决一道题目

P1582 倒水

普及+/提高

这道题目最重要的地方就是要想明白其和「二进制」的关系。

关系

首先，我们来梳理一下题目的规则。每两个瓶子可以进一个大瓶子——也就是说，满二进一。

如果我们把输入的 $N$ 转换成二进制。我们来思考一下，这个过程也就相当于自动把他合并了起来，而其中的 1 就是单独的瓶子。

当然如果这样你无法想明白的话，你可以写一个把 $n$ 个瓶子合并的程序——然后惊讶的发现它和「十进制转二进制」的程序一模一样。

cpp
while(n!=0){
    y++;
    if(n%2==0) n/=2;
    else if(n%2){
        a[y]=1;
        n=(n-1)/2;
    }
}

其中的 n=(n-1)/2; 可以化简成 n/=2;（c++特性，除去小数），而 a[y]=1; 又是 a[y]=n%2; 。所以，整个程序就和

cpp
while (n != 0) {
    y++;
    a[y] = n % 2;
    n /= 2;
}

没有区别了。

如果你还是没有办法理解，我们可以用图表的方式来感知。

n	二进制	合并
1	1	1个瓶子
2	10	1个瓶子
3	11	2个瓶子
4	100	1个瓶子
5	101	2个瓶子
6	110	2个瓶子
7	111	3个瓶子
8	1000	1个瓶子
...	...	...

基本准备

程序的基本准备，在这里统一赘述。

首先，将。 $n$ 转换为二进制，前文已经说明理由。

cpp
void n_to_2(int x) {
    while (x != 0) {
        y++;
        n_2[y] = x % 2;
        cnt_k += x % 2;
        x /= 2;
    }
    return;
}

这里的数组定义到25就可以了 int n_2[25]; ,别问我为什么，把数据范围 $2 \times10^9$ 转换成二进制，然后数位数出来的。

说起来都是泪🥱。

里面的 cnt_k 后面会用到，是用来记录一共有多少个1的。

然后，后面会用到「二进制转十进制」的位权，后文介绍「进制」专题的时候会讲到。

简单来说，位权就是你这一位的数组代表多大，如十进制中，百位的位权是 100 ，所以百位上的4 就代表 $4 \times 100$

而位权的计算方法是 $进制^{位数-1}$ ，所以得到如下程序

cpp
void quan_write() {
    quan[1] = 1;
    for (int i = 2; i < 30; i++) {
        quan[i] = quan[i - 1] * 2;
    }
}

然后是主函数的输入和上述函数调用。

cpp
int n, k;
cin >> n >> k;
n_to_2(n);
quan_write();

计算

我们可以考虑一下，如果 $n_{(2)}$ 中 1 的个数大于 $k$ 则需要尽量让两个1合并。只有在一个数位满二进一的时候，才会减少1的个数。我们可以想象成把末尾的1往前推（进位），使其和前面的1回合，从而减少1的个数。当然，如果一时理解不了也没有关系，看后面的代码或许你就会明白了。

这个代码比较复杂，我来分段讲述。

首先，我们肯定是从低位向高位取。而进制转换中，数组存储顺序是从下标低的为低数位，高的为高数位。

所以，我们只要让 $i$ 从 1 往上推就可以了。

那么这个时候，前文进制转换函数中的 cnt_k 就可以用到了。当里面1的个数「不超过」 $k$ 的时候，程序就可以结束了。

程序的框架如下

cpp
int i = 1;
while (cnt_k > k) {……}

那么访问每一位的时候，会分为两种情况——0/1/2。

0的情况就是本来没有数字。那么我们也没有必要处理，因为前文说过，我们的算法就是相当于把1加数往前推，那么既然没有1，我们也没有必要招惹他了。
1的情况就是上文说的，我们就应该给他在这一位上加上一个1，让它进位。那么，在这里加上一个1相当于加上十进制的几呢？我们就要用到上文的位权，加上一个这个位置的1就是 $1\times quan[i]$ 也就是 cnt += quan[i];。然后就是常规的这一位减下一位加。cnt_k 应该 -1+1 ，也就互相抵消了

cpp
if (n_2[i] == 1) {
    cnt += quan[i];
    n_2[i]--;
    n_2[i + 1]++;
}

至于是2的情况，就「逢二进一」，由于进位的时候少了一个1 所以 cnt_k--;。

cpp
if (n_2[i] == 2) {
    n_2[i] = 0;
    n_2[i + 1]++;
    cnt_k--;
}

综上，代码如上

cpp
int i = 1;
while (cnt_k > k) {
    if (n_2[i] == 1) {
        cnt += quan[i];
        n_2[i]--;
        n_2[i + 1]++;
    } else if (n_2[i] == 2) {
        n_2[i] = 0;
        n_2[i + 1]++;
        cnt_k--;
    }
    i++;
}

拼凑

把函数放在一起，并且算上定义输出等，就是如下代码，可以方便的理解思路和算法。

cpp
#include <bits/stdc++.h>
using namespace std;
int n_2[25];
int y;
int cnt;
int cnt_k;
long long quan[30];
void n_to_2(int x) {
    while (x != 0) {
        y++;
        n_2[y] = x % 2;
        cnt_k += x % 2;
        x /= 2;
    }
    return;
}
void quan_write() {
    quan[1] = 1;
    for (int i = 2; i < 30; i++) {
        quan[i] = quan[i - 1] * 2;
    }
}

int main() {
    int n, k;
    cin >> n >> k;
    n_to_2(n);
    quan_write();
    int i = 1;

    while (cnt_k > k) {
        if (n_2[i] == 1) {
            cnt += quan[i];
            n_2[i]--;
            n_2[i + 1]++;
        } else if (n_2[i] == 2) {
            n_2[i] = 0;
            n_2[i + 1]++;
            cnt_k--;
        }
        i++;
    }
    cout << cnt;
    return 0;
}

总结

通过本文的学习，相信你初步的，由浅入深的了解了「模拟」。

建议你在学习过后多多刷题，可以在 luogu 上搜索算法「模拟」来练习这些题目。

如果你有什么疑问或者代码上的修改，可以用「评论区」或者「邮箱」（右边联系方式）联系我。

如果你喜欢这篇文章，欢迎转发给你的同学/老师。

当然，如果本文有什么问题，也欢迎在评论区指出。

我们后会有期！

目录

总领

题目