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

二、回文日期

1. 题目描述

给定两个日期 begin 和 end，统计其中有多少个日期是回文数（例如 20211202）。

2. 思路分析

回文日期的特点是年月日数字对称。这里提供两种枚举策略：

1. 枚举月 + 日：固定月和日，根据回文特性反推年份。复杂度约为 O(10^3)。注意 2 月 29 日仅在闰年存在，需特殊处理或验证。
2. 枚举年：固定年份，根据回文特性反推月和日。复杂度约为 O(10^4)。

策略一效率更高，因为月份和日的组合远少于年份的组合。在实现时需注意日期合法性校验（如闰年判断、每月天数限制）。

3. 代码实现

策略一：枚举月 + 日

#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;
            // 组合成完整日期数字 YYYYMMDD
            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) {
    if ((y % 4 == 0 && y % 100 != 0) || (y % 400 == 0)) return true;
    else return false;
}

// 数字反转函数
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;
        int flag = 0;
        
        // 校验日期是否合法
        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 = 1;
            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. 题目描述

第一列给出每行格子周围地雷的总数，第二列给出地雷分布情况。已知第二列的部分信息，推断第一列是否有雷。

2. 思路分析

这是一个典型的逻辑推导问题。第一列的状态决定了后续行的状态。由于第一行第一列要么有雷（1），要么没雷（0），我们可以枚举这两种初始状态，然后依次推导后续行是否满足给定的地雷数量约束。

关键点在于边界检查：当计算到第 n 行时，需要确保第 n+1 行的地雷数为 0，否则说明推导出的状态不合法。此外，中间过程若出现负数或多于 1 的情况，也直接判定为非法。

3. 代码实现

#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;
    }
    // 检查第 n+1 行是否闭合（应为 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;
}

通过这三道题，我们可以看到模拟算法不仅仅是简单的循环，更需要结合数学规律进行剪枝和优化。在实际编码中，务必注意数组越界、闰年判断等细节，这些往往是调试时的'坑'。