【算法通关指南：算法基础篇 】模拟算法专题：1. 铺地毯 2. 回文日期 3. 扫雷
🔥小龙报：个人主页
🎬作者简介：C++研发，嵌入式，机器人方向学习者
❄️个人专栏：《算法通关指南》
✨ 永远相信美好的事情即将发生
文章目录
前言
本专栏聚焦算法题实战，系统讲解算法模块：以《c++编程》，《数据结构和算法》《基础算法》《算法实战》 等几个板块以题带点，讲解思路与代码实现，帮助大家快速提升代码能力ps:本章节题目分两部分，比较基础笔者只附上代码供大家参考，其他的笔者会附上自己的思考和讲解，希望和大家一起努力见证自己的算法成长
一、模拟算法
枚举顾名思义，就是把所有情况全都罗列出来，然后找出符合题目要求的那⼀个。因此，枚举是⼀种纯暴力的算法。
⼀般情况下，枚举策略都是会超时的。此时要先根据题目的数据范围来判断暴力枚举是否可以通过。如果不行的话，就要用其他各种算法来进行优化（如：二分，双指针，前缀和与差分等）。
使用枚举策略 时，重点思考枚举的对象（枚举什么），枚举的顺序（正序还是逆序），以及枚举的方式（普通枚举？递归枚举？⼆进制枚举）。
二、模拟的经典算法题
2.1 铺地毯
2.1.1题目
链接：铺地毯
2.1.2 算法原理
枚举所有的地毯，判断哪⼀个地毯能够覆盖(x, y)这个位置。
优化枚举方式：
• 因为我们要的是最后⼀个能够覆盖(x, y)位置的地毯，那么逆序枚举所有的地毯，第⼀次找到覆
盖(x, y) 位置的就是结果；
• 如果从前往后枚举，我们至少要把所有地毯都枚举完，才能知道最终结果。
2.1.3代码
#include<iostream> using namespace std;typedeflonglong LL;constint N =1e5+10; LL a[N], b[N],g[N],k[N];int n;intfind(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;}intmain(){ 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;return0;}2.2 回文日期
2.2.1题目
链接：回文日期
2.2.2 算法原理
核心：每一个固定的年份有且只有一个月日组合可以与其构成回文关系，反之每一个固定的月日组合有且只有一个年份可以与其构成回文关系
两个枚举策略 :
策略一 ：枚举所有日月的组合，然后根据回文的特性推出年份，然后比较这个数字时候在题目给定的区间内（复杂度最优10^3左右）
注意 ：策略一在枚举2月时候因为0229反过来9220为闰年且合法故可以直接用打表的方式定为29天。
策略二 ：枚举所有年的组合然后根据回文的特性推出月份和日，然后比较这个数字时候在题目给定的区间内(复杂度在10^4左右)
总结：解决问题时不同的枚举对象能大大优化问题的解决效率，这是我们在解决问题时要多多思考的.
2.2.3代码
2.2.3.1 枚举月 + 日
#include<iostream> using namespace std;int m[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};intmain(){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;return0;}2.2.3.2 枚举年
#include<iostream> using namespace std;//判断是否为闰年 bool check_year(int y){if(y %4==0&& y %100!=0|| y %400==0)return true;elsereturn false;}intnum(int x){int k =0;while(x){ k = k *10+ x %10; x /=10;}return k;}intmain(){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 =num(i);int m = k /100;int d = k %100;int flag =0;//校验日期是否合法if(m >1|| m <=12){if(check_year(i)&& m ==2) flag =(d <=29);elseif((m ==1|| m ==3|| m ==5|| m ==7|| m ==8|| m ==10|| m ==12)&& d <=31) flag =(d <=31);elseif(m ==2) flag =(d <=28);elseif(m ==4|| m ==6|| m ==9|| m ==11) flag =(d <=30);if(flag){ k += i *10000;if(k >= begin && k <= end) ret++;}}} cout << ret << endl;return0;}2.3 扫雷
2.3.1题目
链接：扫雷
2.3.2 算法原理
我们发现，当第⼀列中，第⼀行的格子的状态确定了之后，其实后续行的状态也跟着固定下来。而第⼀列中，第⼀行的状态要么有雷，要么没有雷，所以最终的答案就在0, 1, 2 中。因此，我们枚举第⼀列中，第一行的两种状态：要么有雷，要么没雷。然后依次计算剩下行的值，看看是否能满足所给的数据。
注意：
（1）如何判断当前格子是否有雷：
第二列的格子中：第i个格子决定了第一列第i，i - 1，i + 1个格子是否有雷，故定义两个数组a和b表示第一列和第二列，故可以推出关系式a[i] = b[i - 1] - a[i - 1] - a[i - 1]
（2）极端情况如下：
|1 | 1 |
|0 | 3 |
如果我们只枚举到n当出现这种特例时看着好像正确，但却是错误的，故我们要枚举到n + 1，判段第n + 1个格子是否为0才能让整个逻辑闭环
2.3.3代码
#include<iostream> using namespace std;constint N =1e4+10;int a[N], b[N];intcheck1(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)return0;}if(a[n +1])return0;return1;}intcheck2(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)return0;}if(a[n +1])return0;return1;}intmain(){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;return0;}总结与每日励志
✨本文介绍了模拟算法的基本概念及其应用，通过三个经典算法题（铺地毯、回文日期、扫雷）展示了模拟算法的解题思路与优化方法。文章强调枚举策略的选择对解题效率的影响，并提供了详细代码实现。最后以励志话语"永远相信美好的事情即将发生"作结，鼓励读者坚持学习与成长。
