蓝桥杯基础--模拟

目录1. 模拟算法简介2. 例题2.1扫雷2.2灌溉2.3回文日期在蓝桥杯以及各种编程竞赛中有一种题型几乎每次都会出现它不需要你掌握多么高深复杂的数据结构比如线段树、图论也不需要你推导晦涩的数学公式它考验的纯粹是你的“代码实现能力”和“细心程度”。这种题型我们通常称之为“模拟”。今天我们就来详细聊聊模拟算法并结合三道经典的蓝桥杯真题带你掌握应对模拟题的技巧。1. 模拟算法简介模拟Simulation顾名思义就是“题目怎么说你就怎么做”。模拟题的核心特征是题目会给你一套非常明确的规则、流程或者操作步骤你需要做的就是用代码把这个过程一步一步地“翻译”出来。计算机的优势在于计算速度极快且不会出错我们要利用这一优势让计算机去重现题目中描述的物理过程或逻辑流程。虽然模拟题在思维难度上通常不大但往往是比赛中最容易让人“翻车”的题型。因为模拟题通常具有以下特点细节繁多可能会有各种边界条件和特殊情况需要处理。代码量大流程一旦复杂嵌套的 if-else 和循环就会非常多容易写错或者漏掉条件。状态依赖很多模拟过程是按时间推进的当前状态往往依赖于上一个状态状态更新时的顺序极其重要。做好模拟题的秘诀只有两个字细心。在动手敲代码之前一定要先在草稿纸上把流程图或者状态变化画清楚理清变量的更新顺序然后再开始编写。2. 例题下面我们通过三道不同类型的蓝桥杯真题来看看模拟题在实战中是如何考察的。2.1扫雷https://www.lanqiao.cn/problems/549/learning/?page1first_category_id1problem_id549思路解析这道题是经典的二维数组模拟。题目要求我们根据给定的地雷分布计算出每个非地雷格子周围一圈也就是常见的九宫格区域有多少颗地雷。 对于这种题最直白的方法就是遍历整个二维矩阵。当我们遇到一个格子时 如果是地雷值为1我们就按题目要求或者为了方便标记将结果标记为9。 如果不是地雷我们就再写两层小循环遍历它周围3乘3的区域统计地雷的个数。 这段代码中有一个非常精妙的防越界技巧在内层循环中使用了 max 和 min 函数。比如_i的范围是max(1, i - 1)到min(n, i 1)这样就算当前格子在矩阵的最边缘也不会发生数组越界报错。#include bits/stdc.h using namespace std; const int N 110; int mp[N][N], ans[N][N]; int main() { int n, m; cin n m; for(int i 1; i n; i) { for(int j 1; j m; j) { cin mp[i][j]; } } for(int i 1; i n; i) { for(int j 1; j m; j) { if(mp[i][j] 1) { ans[i][j] 9; continue; } for(int _i max(1, i - 1); _i min(n, i 1); _i) { for(int _j max(1, j - 1); _j min(m, j 1); _j) { if(mp[_i][_j]) ans[i][j]; } } } } for(int i 1; i n; i) { for(int j 1; j m; j) { cout ans[i][j] ; } cout \n; } return 0; }2.2灌溉https://www.lanqiao.cn/problems/551/learning/?page1first_category_id1problem_id551思路解析这是一道非常经典的状态推演模拟题。水管每分钟都会向上下左右四个方向蔓延。我们需要模拟这个蔓延的过程持续 k 分钟。 这里的核心考点是状态的隔离。如果我们在原来的矩阵上直接修改把没水的改成有水那么在同一分钟内刚刚被水蔓延到的新格子可能紧接着又会向外蔓延这就导致了一分钟蔓延了多步的错误。 为了解决这个问题代码中使用了两个矩阵mp用来保存当前分钟的初始状态ans用来记录蔓延后的新状态。每次遍历mp找到有水的地方将周围的格子在ans中标记为有水。一分钟结束后再把ans的状态同步回mp准备下一分钟的模拟。参考代码#include bits/stdc.h using namespace std; const int N 110; bool mp[N][N], ans[N][N]; int main() { int n, m, t; cin n m; cin t; for(int i 1; i t; i) { int x, y; cin x y; mp[x][y] 1; ans[x][y] 1; } int k; cin k; while(k--) { for(int i 1; i n; i) { for(int j 1; j m; j) { if(mp[i][j]) ans[i][j] ans[i - 1][j] ans[i 1][j] ans[i][j - 1] ans[i][j 1] 1; } } for(int i 1; i n; i) { for(int j 1; j m; j) { mp[i][j] ans[i][j]; } } } int ret 0; for(int i 1; i n; i) { for(int j 1; j m; j) { if(mp[i][j]) ret; } } cout ret \n; return 0; }2.3回文日期https://www.lanqiao.cn/problems/498/learning/?page1first_category_id1problem_id498思路解析这是一道非常经典的日期模拟题。题目要求找出一个给定日期之后的下一个回文日期以及下一个满足 ABABBABA 格式的特殊回文日期。 如果一天一天地往后加还需要处理复杂的进位和闰年判断既容易超时又极其容易写错。 换一种更聪明的模拟思路既然是回文日期前四位年份直接决定了后四位月日。所以我们大可不必一天一天枚举直接从给定的年份开始向下枚举年份。 对于每一个年份我们通过反转拼凑出对应的8位回文日期然后判断这个日期是否比输入的日期 n 大。是否是一个合法的真实日期利用打表的 days 数组和闰年判断函数 isleapYear。 如果是合法日期我们再通过简单的数学运算分离出A和B判断是否满足 ABABBABA 格式即可。这样不仅代码逻辑清晰而且运行速度极快。参考代码#include bits/stdc.h using namespace std; int days[13] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; bool isleapYear(int year) { return (year % 4 0 year % 100 ! 0) || (year % 400 0); } bool checkDate(int year, int month, int day) { if(month 1 || month 12 || day 1) return false; if(month ! 2) return day days[month]; if(isleapYear(year)) return day 29; return day 28; } int main() { int n; cin n; bool found1 false, found2 false; int startYear n / 10000; for(int i startYear; i 9999; i) { int date i * 10000 (i % 10) * 1000 (i / 10 % 10) * 100 (i / 100 % 10) * 10 (i / 1000); if(date n) continue; int month (date / 100) % 100; int day date % 100; if(checkDate(i, month, day)) { if(!found1) { cout date \n; found1 true; } int A1 i /1000; int B1 (i / 100) % 10; int A2 (i / 10) % 10; int B2 i % 10; if(!found2 A1 A2 B1 B2 A1 ! B1) { cout date \n; found2 true; } } if(found1 found2) break; } return 0; }本章完。