模拟算法实战：铺地毯、回文日期与扫雷题解

模拟算法概述

枚举是模拟算法的核心，本质就是把所有可能的情况罗列出来，筛选出符合题意的那一个。虽然暴力枚举容易超时，但在数据范围允许的情况下，它是最直接的解法。如果直接枚举会超时，就需要结合题目特性优化枚举顺序或对象（比如二分、双指针等）。思考重点在于：枚举什么？按什么顺序？怎么枚举？

经典例题解析

1. 铺地毯

问题描述：给定 n 张地毯的坐标和长宽，查询某个点被哪张最后铺设的地毯覆盖。

思路： 我们需要找到覆盖该点的最后一张地毯。如果正序遍历，必须检查完所有地毯才能确定结果；如果逆序遍历，一旦找到第一张覆盖的点，就是答案，可以直接返回。这种优化能显著减少不必要的判断。

代码实现：

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
LL a[N], b[N], g[N], k[N]; // x, y, width, height
int n;

int find(int x, int y) {
    for (int i = n; i >= 1; i--) {
        if (x >= a[i] && y >= b[i] && x <= a[i] + g[i] && y <= b[i] + k[i]) {
            return i;
        }
    }
    return -1;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> g[i] >> k[i];
    LL x, y;
    cin >> x >> y;
    cout << find(x, y) << endl;
    return 0;
}

2. 回文日期

问题描述：在给定日期范围内，统计有多少个日期是回文的。

思路： 回文日期的特点是年份由月日决定，或者月日由年份决定。 策略一：枚举月日组合，反推年份。复杂度 O(12*31)，效率最高。注意闰年 2 月只有 29 天。 策略二：枚举年份，反推月日。复杂度 O(年份差)，稍慢但逻辑直观。

代码实现（枚举月日）：

#include <iostream>
using namespace std;

int m[13] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int main() {
    int begin, end;
    cin >> begin >> end;
    int ret = 0;
    for (int i = 1; i <= 12; i++) {
        for (int j = 1; j <= m[i]; j++) {
            // 构造回文年份部分
            int k = j % 10 * 1000 + j / 10 * 100 + i % 10 * 10 + i / 10;
            int num = k * 10000 + i * 100 + j;
            if (num >= begin && num <= end) ret++;
        }
    }
    cout << ret << endl;
    return 0;
}

代码实现（枚举年份）：

#include <iostream>
using namespace std;

bool check_year(int y) {
    return (y % 4 == 0 && y % 100 != 0) || (y % 400 == 0);
}

int reverse_num(int x) {
    int k = 0;
    while (x) {
        k = k * 10 + x % 10;
        x /= 10;
    }
    return k;
}

int main() {
    int begin, end;
    cin >> begin >> end;
    int x = begin / 10000;
    int y = end / 10000;
    int ret = 0;
    for (int i = x; i <= y; i++) {
        int k = reverse_num(i);
        int month = k / 100;
        int day = k % 100;
        bool flag = false;
        if (month > 0 && month <= 12) {
            if (month == 2) {
                flag = check_year(i) ? (day <= 29) : (day <= 28);
            } else if (month == 4 || month == 6 || month == 9 || month == 11) {
                flag = day <= 30;
            } else {
                flag = day <= 31;
            }
        }
        if (flag) {
            int palindrome_date = i * 10000 + month * 100 + day;
            if (palindrome_date >= begin && palindrome_date <= end) ret++;
        }
    }
    cout << ret << endl;
    return 0;
}

3. 扫雷

问题描述：已知第二列的数字，推断第一列是否有雷。

思路： 这是一个状态推导问题。第一列的状态决定了后续行的状态。由于第一行第一列要么有雷要么没雷，只有两种可能。我们可以分别假设第一格有雷和无雷，然后依次推导后续格子是否合法。 注意边界条件：需要多判断一行（n+1），确保推导出的第 n+1 个格子没有雷，逻辑才闭环。

代码实现：

#include <iostream>
using namespace std;

const int N = 1e4 + 10;
int a[N], b[N]; // a: 第一列，b: 第二列

int check1(int n) {
    a[1] = 0; // 假设第一格无雷
    for (int i = 2; i <= n + 1; i++) {
        a[i] = b[i - 1] - a[i - 1] - a[i - 2];
        if (a[i] < 0 || a[i] > 1) return 0;
    }
    return a[n + 1] == 0 ? 1 : 0;
}

int check2(int n) {
    a[1] = 1; // 假设第一格有雷
    for (int i = 2; i <= n + 1; i++) {
        a[i] = b[i - 1] - a[i - 1] - a[i - 2];
        if (a[i] < 0 || a[i] > 1) return 0;
    }
    return a[n + 1] == 0 ? 1 : 0;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> b[i];
    int ret = 0;
    ret += check1(n);
    ret += check2(n);
    cout << ret << endl;
    return 0;
}