模拟算法

简介

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

模拟题目通常具有码量大、操作多、思路繁复的特点。由于它码量大，经常会出现难以查错的情况，如果在考试中写错是相当浪费时间的。

竞赛模拟题特点

简洁性：变量名简短（通常单字母），代码紧凑
效率性：注重算法效率而非代码可读性
快速实现：省略不必要的封装和模块化
输入输出简单：通常使用标准输入输出，不处理复杂格式

例题

例题 1：数字反转（NOIP 普及组真题）

#include <iostream>
using namespace std;

int main() {
    int n, ans = 0;
    cin >> n;
    while(n) {
        ans = ans * 10 + n % 10;
        n /= 10;
    }
    cout << ans;
    return 0;
}

特点分析：

变量名简短：n表示输入数字，ans表示答案
直接使用基本数据类型
不处理特殊情况注释（如负数）
省略不必要的空格和空行

例题 2：小玉买文具（CSP-J 真题）

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    cout << (a * 10 + b) / 19;
    return 0;
}

典型模拟题分类与解法

1. 简单规则模拟

例题：计算星期几（已知 1900 年 1 月 1 日是星期一）

#include <iostream>
using namespace std;

int md[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

int main() {
    int y, m, d, cnt = 0;
    cin >> y >> m >> d;
    
    for(int i=1900; i<y; i++) {
        cnt += 365 + ((i%4==0 && i%100!=0) || (i%400==0);
    }
    
    for(int i=1; i<m; i++) {
        cnt += md[i];
        if(i==2 && ((y%4==0 && y%100!=0) || (y%400==0))) cnt++;
    }
    
    cnt += d - 1;
    cout << (cnt % 7 + 1);
    return 0;
}

2. 网格移动模拟

例题：机器人移动（CSP-S 模拟题）

#include <iostream>
using namespace std;

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

int main() {
    int n, m, x=1, y=1, d=1;
    cin >> n >> m;
    int g[n+2][m+2] = {0};
    
    for(int k=1; k<=n*m; k++) {
        g[x][y] = k;
        int nx = x + dx[d], ny = y + dy[d];
        if(nx<1 || nx>n || ny<1 || ny>m || g[nx][ny]) {
            d = (d+1)%4;
            nx = x + dx[d], ny = y + dy[d];
        }
        x = nx, y = ny;
    }
    
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            printf("%4d", g[i][j]);
        }
        cout << endl;
    }
    return 0;
}

3. 时间序列模拟

例题：红绿灯问题（NOIP 提高组模拟）

#include <iostream>
using namespace std;

int main() {
    int n, t, now = 0;
    cin >> n;
    while(n--) {
        cin >> t;
        if(now < t) now = t; // 等待绿灯
        now += 10; // 通过路口
    }
    cout << now;
    return 0;
}

模拟题优化技巧

输入输出优化：

ios::sync_with_stdio(false);
cin.tie(0);

使用数组代替复杂数据结构：

int q[100010], hh=0, tt=-1; // 数组模拟队列

位运算加速：

if(s >> i & 1) // 检查第 i 位是否为 1

预处理常用数据：

const int N = 1e6+10;
int primes[N], cnt;
bool st[N];

注意事项

变量命名：
- 循环变量：i, j, k
- 答案变量：ans, res
- 临时变量：t, tmp
避免使用：
- STL 容器（除非必要）
- 面向对象特性
- 过多的指针

必备模板：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5+10;

技巧

写模拟题时，遵循以下的建议有可能会提升做题速度：

在动手写代码之前，在草纸上尽可能地写好要实现的流程。
在代码中，尽量把每个部分模块化，写成函数、结构体或类。
对于一些可能重复用到的概念，可以统一转化，方便处理：如，某题给你 "YY-MM-DD 时：分" 把它抽取到一个函数，处理成秒，会减少概念混淆。
调试时分块调试。模块化的好处就是可以方便的单独调某一部分。
写代码的时候一定要思路清晰，不要想到什么写什么，要按照落在纸上的步骤写。

实际上，上述步骤在解决其它类型的题目时也是很有帮助的。

例题详解

例题

一只长度不计的蠕虫位于 $n$ 英寸深的井的底部。它每次向上爬 $u$ 英寸，但是必须休息一次才能再次向上爬。在休息的时候，它滑落了 $d$ 英寸。之后它将重复向上爬和休息的过程。蠕虫爬出井口需要至少爬多少次？如果蠕虫爬完后刚好到达井的顶部，我们也设作蠕虫已经爬出井口。

解题思路

直接使用程序模拟蠕虫爬井的过程就可以了。用一个循环重复蠕虫的爬井过程，当攀爬的长度超过或者等于井的深度时跳出。

参考代码

#include <iostream>

using namespace std;

int main() {
  int n = 0, u = 0, d = 0;
  cin >> u >> d >> n;
  int time = 0, dist = 0;
  while (true) {  // 用死循环来枚举
    dist += u;
    time++;
    if (dist >= n) break;  // 满足条件则退出死循环
    dist -= d;
  }
  cout << time << '\n';  // 输出得到的结果
  return 0;
}

例题

Status

Problem

模拟算法

On this page