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

前言

模拟算法的核心思想是枚举，即把所有可能的情况都罗列出来，从中找出符合题目要求的那一个。虽然这是一种暴力方法，容易超时，但在数据范围允许的情况下，它是最直接的解法。

使用枚举策略时，重点思考三个问题：枚举的对象是什么？枚举的顺序如何（正序还是逆序）？以及枚举的方式（普通循环、递归还是二进制）。

一、铺地毯

题目描述 给定 n 张地毯，每张地毯由左下角坐标 (x, y) 和长宽 g, k 定义。查询某个位置 (X, Y) 被哪一张地毯覆盖。如果有多个，输出最后放置的那一张。

思路解析 我们需要找到覆盖 (X, Y) 的地毯中编号最大的那个。如果从前往后枚举，必须遍历完所有地毯才能确定结果。更优的做法是逆序枚举：从最后一张地毯开始往前找，第一次遇到覆盖该位置的地毯，就是答案。

代码实现

#include<iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL a[N], b[N], g[N], k[N];
int n;

int find_pos(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_pos(x, y) << endl;
    return 0;
}

二、回文日期

题目描述 给定两个日期 begin 和 end，统计区间内有多少个回文日期。

思路解析 回文日期具有对称性。对于固定的年份，只有特定的月日组合能构成回文；反之亦然。这里提供两种枚举策略：

1. 枚举月 + 日：复杂度约 10^3。根据月日反推年份，检查是否在区间内且合法。注意 2 月 29 日的闰年判断。
2. 枚举年：复杂度约 10^4。根据年份反推月日，校验合法性。

策略一通常更快，因为月份和日期的组合远少于年份的组合。

代码实现：枚举月 + 日

#include<iostream>
using namespace std;
// 每月天数表，2 月设为 29 天方便处理闰年逻辑
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(check_year(i) && month == 2) flag = (day <= 29);
            else if((month == 1 || month == 3 || month == 5 || month == 7 || month == 8 || month == 10 || month == 12) && day <= 31) flag = true;
            else if(month == 2) flag = (day <= 28);
            else if(month == 4 || month == 6 || month == 9 || month == 11) flag = (day <= 30);
            
            if(flag){
                int palindrome_date = k + i * 10000;
                if(palindrome_date >= begin && palindrome_date <= end) ret++;
            }
        }
    }
    cout << ret << endl;
    return 0;
}

三、扫雷

题目描述 已知第二列每个格子周围的雷数，推断第一列是否有雷。

思路解析 这是一个典型的递推问题。一旦确定了第一列第一个格子的状态（有雷或无雷），后续行的状态就被第二列的数据唯一确定了。

我们只需要枚举第一列第一个格子的两种情况：有雷（1）和无雷（0）。然后依次推导后续行，看是否能满足所有约束条件。

注意点

1. 递推公式：第二列第 i 个格子的雷数等于第一列第 i-1, i, i+1 个格子的雷数之和。因此可以反推第一列的状态。
2. 边界检查：需要额外检查推导出的第 n+1 个格子是否为 0，确保逻辑闭环。

代码实现

#include<iostream>
using namespace std;
const int N = 1e4 + 10;
int a[N], b[N];

// 假设第一格没有雷
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;
    }
    if(a[n + 1]) return 0;
    return 1;
}

// 假设第一格有雷
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;
    }
    if(a[n + 1]) return 0;
    return 1;
}

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;
}