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

代码实现（枚举月日）：

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