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

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

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