对模拟和枚举的认识
模拟其实是一个比较宽泛的概念了，一般来说，不是常规的最短路问题，比如它不是用动归规划解决的最优解，不是贪心，也不是最短路问题的时候，就可以考虑能否用模拟结合枚举进行解题。
枚举这个理念的出现倒是比较直接简单了，在认知中，就是循环嘛。
简单来说，也就是暴力嘛。这个了，确实是这么一回事儿。
可能人人都会写枚举，但不一定写出来的枚举就可以Ac。正是因为枚举的思想是挺直接简单的，所以枚举的考点放在了细节的处理上。
待会就系统结合的枚举的历年真题，切实的感受一下它的玩法，以及总结一些枚举中经常用到的小技巧和思考方向
枚举首先要考虑的是如何在遍历的途中，把咱们需要的答案查找出来。
既然是可以直接暴力获得部分的分，那么就可以通过题目中隐藏的信息进行优化的。
还有一个比较重要的知识是，如何通过给定的数据范围确定自己最多可以进行几重循环。这个我在壹之型中总结了。
因为没有模板，模拟的题了，要么都会，此时需要注意的是细节；要么都不会。
不像其他算法，比如，我忘记SPFA的模板怎么写了，执梗记得，那么我就没有这个分了。模拟说直白点了，确实就是循环，但是怎么循环也是一门学问了，看能不能get到题目中的隐藏的信息，以及处理好一些小技巧。模拟的题，细节是真的多。
一触即发
第一话、第十届蓝桥杯省赛C++B组 特别数的和
进入题目描述环节
题目描述
解题报告
这个题算是枚举中相当乖的一道题了，读完题目以后，脑海中确实很难把它归纳到某一类专门的算法中，此时就乖乖的拿出我们的枚举大法吧。
解题思路：
枚举输入的范围内的中每一个数，然后将这个数，比如是39，用取模运算符和整除运算符将39中的每一位都取出来。
参考代码(C++版本)
#include <iostream> #include <cstring> #include <algorithm> using namespace std; int main() { int n; cin >> n; int res = 0; for(int i = 1; i <= n;i++) { int x = i; while(x)//当这个数还存在的时候，就持续取它 { int t = x %10 ; //取出个位 x /= 10; //删掉x的个位 if(t == 2 || t == 0 || t == 1 || t == 9) { //将符合条件的数字累加起来 res += i; break; } } } //输出结果 cout << res << endl; return 0; }
第二话、第四届蓝桥杯省赛C++A/B组 错误票据
这道题最主要的思想是对于一串数据，可以先处理为字符串。那么此时就要考虑：
1、字符串的读入
2、怎么把字符串处理为其他类型的数据
题目描述
解题报告
这道题难度也是不大，将输入的n nn行数据进行排序之后，再逐一枚举这n nn个数。
如果相邻的两个数的数值相同，就是重号；如果相邻的两个数，数值只差大于等于2，比如3 33和5 55。那么就是断号
比较棘手同时也是需要掌握的是这道题的输入技巧。【重点】
1、掌握cin的读取原理：
当 cin读取数据时，它会传递并忽略任何前导白色空格字符（空格、制表符或换行符）。
一旦它接触到第一个非空格字符即开始读取，当它读取到下一个空白字符时，它将停止读取。
因为咱们要读取的这串数据中有太多空格，而且数量也是未知，所以cin和scanf都劝退
2、getline函数
为了解决这个问题，可以使用 getline 这个函数。它可读取整行，包括前导和嵌入的空格，并将其存储在字符串对象中。
使用的语法如下：
getline(cin, inputLine);//其中 cin 是正在读取的输入流，而 inputLine 是 string 类型的变量，用于接收输入的字符串 //题目中的使用代码 getline(cin,line);
3、stringstream快速实现string类型和int类型之间的转换
< sstream > 定义了三个类：istringstream、ostringstream 和 stringstream，分别用来进行流的输入、流的输出和流的输入输出操作。
参考代码(C++版本)
#include <iostream> #include <cstring> #include <sstream> #include <algorithm> #include <string.h> using namespace std; const int N = 10010; int n; int a[N]; int main() { int cnt; cin >> cnt; string line; //第一个坑 getline(cin,line);//注意！这里用于忽略掉第一行的回车。引入输入cnt之后，是有一个回车的。要解决它 while(cnt--) { //正常的使用getline函数来读入 getline(cin,line); //把line这个字符串中的信息，通过stringstream加载到ssin中 stringstream ssin(line); //因为 stringstream是输入输出流，此时Ssin就可以像cin一样,将ssin中存储的信息，输入到数组a中 while(ssin >> a[n]) n++; } sort(a,a+n); // for(int i = 0;i < n;i++) printf("%d",a[i]); //输出效果如图，可以看到输入数据中的空格现在没有了：568991011127 int res1,res2; for(int i =1;i < n;i++) if(a[i] == a[i-1]) res2 = a[i];//重号 else if(a[i] >= a[i-1]+2) res1 = a[i]-1;//断号 cout << res1 << ' ' << res2 << endl; return 0; }
第三话、第六届蓝桥杯省赛C++B组 移动距离
移动距离主要想让大家了解曼哈顿距离，其次是再次熟悉一下映射的思想。
题目描述
解题报告
这道题应该是可以用宽搜来做的，一题可以多解，但是打比赛的时候，找到一个对于自己而言，选择一个写起来简单，也不容易错的算法就好。
对于折线求最短路径，可以使用几何学中的曼哈顿距离进行求解。结合公式，只要知道两个位置的坐标，就可以快速算出距离。
曼哈顿距离概述：
曼哈顿距离的命名原因是从规划为方型建筑区块的城市（如曼哈顿）间，最短的行车路径而来。
曼哈顿距离的计算：
咱们生活中零零散散的还有其他距离的定义，感兴趣的小伙伴可以了解一下呀~
其他距离的拓展
映射思想：
现在咱们的目标是出楼号m mm和楼号n nn的坐标，然后带入公式中就可以顺利求解
通过映射，我们让所有数都减1，在总数量不变的情况下，行号和列号都是从0开始的时候，回到咱们熟悉的二维数组的形式，那么可能更好发现规律，作图一看，确实是的
从一般到特殊的思考方向：
好啦，这道题最主要的是掌握住曼哈顿距离和映射的思想，咱们学的应该是思想。
参考代码(C++报告)
//考察的是曼哈顿距离加上一些映射思想 #include <cstring> #include <iostream> #include <algorithm> using namespace std; int main() { int w,m,n; cin >> w >>m >> n; m--,n--; //通过自己的模拟，实现行号的转换 int x1 = m/w,x2 = n/w; //求列号 int y1 = m % w,y2 = n % w; //因为是蛇形的，列号在奇数列是存在不同的 if(x1 % 2) y1 = w -1-y1;//套入翻转的规律 if(x2 % 2) y2 = w-1-y2; //带入曼哈顿距离的公式，输出答案 cout << abs(x1-x2) + abs(y1-y2) << endl; return 0; }
第四话、第八届蓝桥杯省赛C++B组 日期问题
日期问题中，在我现在的认知里，最重要的是知道怎么判读一个日期是否合法。
比如怎么快速的知道一个月份对应的天数；比如怎么判断闰年平年；比如闰年平年二月份的处理。
题目描述
解题报告
对我自己而言
这道题敲定了两种思考方向：
1、直接从答案出发，验证这个解是不是在1960年1月1日到2059年12月31日的范围内
2、老老实实从1960年1月1日枚举2059年12月31日，把里面符合条件的筛选出来
但是因为应该方法一我加了诸多判断条件，代码的落实就比较头疼
对于处理日期问题的两小招：
1、将日期数字化之后取出年月日
//把年月日取出来 int year = date / 10000,month = date%10000/100,day = date % 100;
2、检查日期的年月日是否合法
具体的实现结合代码一看会很清晰喔，我这里额外解释一下这种将每一个月的天数存在的操作。
通过这种提前存下1到12月的天数，需要时候就可以快速查询
int days[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};//把1月到12月的天数先定下来，检查月的天数时，就直接查表。然后0月就是0
小技巧：补齐前导零——使用%02d
printf("%d-%02d-%02d\n",year,month,day);
参考代码(C++版本）
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int days[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};//把1月到12月的天数先定下来，然后0月就是0 //核心：检查输入的年份是否符合条件的函数 bool check_vails(int year,int month,int day) { if(month == 0 || month > 13) return false; if(day == 0) return false; if(month != 2)//先处理不是二月的情况 { if(day > days[month]) return false; }else //处理二月 { //判断平年还是闰年。是平年，leap就是0，是闰年,leap就是1 int leap = year % 100 &&year % 4 == 0 || year % 400 == 0; if(day > 28 + leap) return false; } return true; } int main() { int a,b,c; scanf("%d/%d/%d",&a,&b,&c); //枚举它给的所有日期 for(int date = 19600101;date<= 20591231;date++) { //把年月日取出来 int year = date / 10000,month = date%10000/100,day = date % 100; //判断是否合法 if(check_vails(year,month,day)) { if(year % 100 == a && month == b && day == c || //年/月/日 month == a && day == b &&year % 100 == c || //月/日/年 day == a && month == b && year % 100 == c) //日/月/年 //输出，这里可以使用格式化输出中的02，表示不足两位就补零 printf("%d-%02d-%02d\n",year,month,day); } } return 0; }
第五话、第十一届蓝桥杯省赛C++A\B组 回文日期
省赛这边是考过一个回文日期的题目，但是难度较低而且没有代表性，我在y总可爱的acwing上物色到了一道更典型，更通用的处理时间问题的习题。咱们就着重迎战它吧。
蓝桥这道题的参考代码我放到最后的链接中，点击以后就可以从gitee中获取
题目描述
解题报告
这道题有两个在处理时间上十分重要的思想：
一、将一个数字通过不断的自身乘10+原数据的个位，将一个日期变成回文日期
date = date * 10 + tmp % 10;
二、检查一个日期是否合法的。
其中包括了将一个日期的年、月、日分别取出;
以及如何用打表的形式来判断一个月的天数是否符合要求，以及在平年和闰年对二月的处理
bool check_vaild(int date);
参考代码(C++版本)
#include <cstdio> #include <iostream> #include <algorithm> using namespace std; int days[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31}; //判断一个日期是否合法的核心函数 bool check_vaild(int date) { //取出date中的年、月、日 ===> 记得最好，记不得了直接拿样例然后模拟就好 int year = date / 10000; int month = date % 10000 /100; int day = date % 100; //判断月份是否合法 if(month < 0 || month > 13) return false; //判断一个月中的每一天是否合法 //先处理非2月的情况 if(day == 0 || month != 2 && day> days[month]) return false; else { //求一下当前这年是平年还是闰年 //想特例吧，比如2020年是，1900不是闰年 int leap = year % 100 && year % 4 == 0 || year % 400 ==0; if(day > days[month]+leap) return false; } return true; } int main() { int date1,date2; cin >> date1 >>date2; //枚举年份，在枚举的同时将这个年份处理成一个回文的 //紧接着去判断这个年份是否是合法的 int res = 0; for(int i = 1000; i <= 9999;i++) { int date = i , tmp = i; //将当前这个日期处理成回文的 for(int j = 0; j < 4;j++) { //将回文后的数字重新赋值给date date = date * 10 + tmp % 10;//把个位抠出来，通过扩展位数的方式，实现回文拼接 tmp /= 10; } //判断这个日期是否在给定范围内，以及是否合法，统计结果 if(date1 <= date && date <= date2 && check_vaild(date)) res ++; } //输出结果 cout << res << endl; }
第六话、第九届蓝桥杯省赛C++A组 航班时间
航班时间这个题，主要是想介绍这种算时差的思想。
算时差是可以类比到初中物理中常见的，小船顺流而下时，怎么处理水速问题，逆流而上又怎么处理。
题目描述
解题报告
1、在时差下航行时间
去程起飞时间+航行时间+时差=去程降落时间 (公式一)
回程起飞时间+航行时间-时差=回程降落时间 (公式二)
已知:去程起飞时间,回程起飞时间,去程降落时间,回程降落时间
根据公式一+公式二:
去程起飞时间+回程起飞时间+2*航行时间=去程降落时间+回程降落时间
则：航行时间=(去程降落时间-去程起飞时间+回程降落时间-回程起飞时间)/2
2、将字符串处理成处理为整型数据
第一步：通过getline函数将整个字符串读入。
第二步：通过sscanf将字符串中的时分秒信息，结合c_str方法，输入到整型变量进行存储中
sscanf与scanf类似，都是用于输入的，只是后者以键盘(stdin)为输入源，前者以固定字符串为输入源。
假如没有这个C++ API的小伙伴可以到下面的链接中进行下载喔
c++API.chm
3、将数字化的时间取出时分秒
int hour = myTime /3600,minute = myTime%3600/60,second = myTime % 60;
4、碎碎念
可能有小伙伴觉得，天呀，好多要记得嗷~这是学习算法吗，感觉像学语文了
在acwing求学的时候，y总说过一句，大概是这种的(记不得原话了，可恶)： 所有存在时间限制的事儿，比如考试，都不是让我们去创造，而是回忆自己的所学，再类推到当前问题。包括学习也是这么一回事，我们是理解并记忆前人留下的知识。
我高中数学老师，平时喊他阳哥，他喜欢吐槽我们不记忆题型，经常说的一句话是我清楚的记得这个题，在哪一年真题的第几题，不信你去翻，不是的话，我今天操场luo 奔。这可能就是中国数学协会会员的底气吧~
所以不要这么抗拒记忆喔~
参考代码(C++版本)
#include <cstdio> #include <cstring> #include <iostream> #include <string.h> #include <algorithm> using namespace std; //补全函数 int get_seconds(int h,int m,int s) { return h * 3600 + m * 60 + s; } int get_time() { //使用getline读入整行的数据 string line; getline(cin,line); int len = line.length(); char ch = line[len-1]; //手动对第一种当天出发当天到的情况加上(0) // if(line.back() != ')') line += " (+0)"; if(ch != ')') line += " (+0)"; int h1,m1,s1,h2,m2,s2,d; sscanf(line.c_str(),"%d:%d:%d %d:%d:%d (+%d)",&h1,&m1,&s1,&h2,&m2,&s2,&d); return get_seconds(h2,m2,s2) - get_seconds(h1,m1,s1) + d * 24 * 3600; } int main() { int n; scanf("%d",&n); string line; getline(cin,line);//忽略掉第一行的回车 while(n--) { int myTime = (get_time() + get_time()) / 2; int hour = myTime /3600,minute = myTime%3600/60,second = myTime % 60; printf("%02d:%02d:%02d\n",hour,minute,second); } return 0; }
第七话、 第十一届蓝桥杯决赛C++A组 天干地支
和处理每一个月的天数一样，使用打表的思想。
只是需要注意细节，这个表，从什么位置开始打。
题目描述
解题报告
第一印象里，这道题应该是标准的打表题了。
小伙伴们以后感觉题目中有查询的味道的时候，假如是数字类型的，就可以向着哈希和二分靠近了;
假如是本题这种字符型的，就可以考虑造一个表观察出规律之后，直接查询喔~
本题的坑：
可能有小伙伴看到国赛就兴奋了，一看是可以直接枚举的签到题，直接就从"jia"、"yi"的开始枚举，样例一跑，呀，不对~
因为这十天干十二地支具体怎么排列，究竟是甲乙丙丁先放了？还是庚辛壬癸先放了，是没有敲定下来的，因此需要结合题目中所给的案例1900、1960、2020来确定的。
参考代码(C++版本)
#include <cstring> #include <iostream> #include <algorithm> #include <string.h> using namespace std; int main() { int year; cin >> year; //先通过2020,1900,1960模拟一下，它们模10可以取整，此时是geng。模12是余4，此时是zi。 //先把十天干和十二地支枚举出来，就像打表，待会直接查 string s[10] = {"geng","xin","ren","gui","jia","yi","bing","ding","wu","ji"}; string e[12] = {"shen","you","xu","hai","zi","chou","yin","mao","chen","si","wu","wei"}; //直接通过取模看当前这年份是在哪个天干地支 cout << s[year % 10] << e[year%12] << endl; }
第八话、 第十一届蓝桥杯省赛C++A/B组 成绩分析
关于四舍五入的细节
题目描述
解题报告
就乖乖用循环遍历输入的数据，逐个进行比较找出最大值，最小值，同时统计出总和，因为答案要的是一个两位的小数，最后记得把结果强转成double类型。建议比赛都转double，float可能个别时候因为精度问题，导致结果有偏差。
另想提一下四舍五入的事儿：
假如类似这道题，保留几位小数的四舍五入可以直接使用浮点型实现。
倘若是套把1.5四舍五入为2，那么在导入头文件之后，使用C++ 中的round函数
参考代码(C++版本)
#include <cstring> #include <iostream> #include <algorithm> #include <string.h> using namespace std; const int N = 10010,INF = 999999999; int a[N]; int n,sum; int main() { scanf("%d",&n); //输入 for(int i = 0; i < n;i++) scanf("%d",&a[i]); int minv = INF,maxv = -INF; //去老老实实遍历这些输入的数据，也就是所谓的枚举 for(int i = 0; i < n;i++) { minv = min(a[i],minv); maxv = max(a[i],maxv); sum += a[i]; } //输出 printf("%d\n%d\n%.2lf\n",maxv,minv,(double)sum/n); return 0; }
第九话、 第十届蓝桥杯省赛C++A/C组 外卖店优先级
处理离散数据的思想
题目描述
解题报告
处理离散数据的思想——因为对于一个店铺而言，可能一段时间有订单，一段时间又没有订单了。
因此数据是离散的。处理的方式可以把连续没有订单的时刻先忽略了，放到有订单之后来处理。
解题思想：
这个模拟题稍微有点复杂，假如小伙伴有写伪代码的习惯，那么在解决较为复杂的模拟题时，可以更舒服一些
1、将所有订单按照时间排序
2、然后从前向后枚举每个订单
在循环中，每次处理的是一批相同的订单了（可以理解为，只要这个时间点和其对应的店铺Id是相同的，就把它们看做一个整体，实现每次处理一批订单）
记录此时t和id，计算id的优先权，有两部分需要处理
因为相同的订单已经处理过了，就不需要再计算了，直接到j这个出现下一批订单的位置开始新的一轮循环。
for(int i = 0; i < m;) ...... i = j;
循环到最后，将上一次拿到订单的时间l a s t [ i d ] last[id]last[id]更新为t tt
3、最后的处理
如果最后一个订单的时刻为T，那么倒是不用处理了。
如果不是T，那么最后一个订单到T时刻这部分扣除优先级的减法需要我们补上。
即，减去最后一个订单时刻与T的差值。因为T时刻也没有订单，所有这里不用减一了。
判断优先级，假如小于等于3，清除出优先缓存中。最后遍历优先缓存，得到的数量就是题目的答案
参考代码(C++版本)
#include <iostream> #include <cstring> #include <iostream> #include <algorithm> #define x first #define y second using namespace std; typedef pair<int,int> PII; const int N = 100010; int n,m,T; int score[N];//表示第i个店铺的优先级 int last[N];//表示第i个店铺上次没有订单的时刻 bool st[N];//表示第i个店铺当前是否处于优先缓存中 PII order[N]; int main() { scanf("%d%d%d",&n,&m,&T); //因为订单信息是一个二元组，所有这里使用pair来读入一个二元组 for(int i = 0; i < m;i++) scanf("%d %d",&order[i].x,&order[i].y); //进行一步排序：pair是自带比较函数的，按照第一关键字first进行，倘若第一关键字相同，考虑第二关键字 sort(order,order+m); //枚举每个订单 for(int i = 0; i < m;) { int j = i; //找到m个订单中，相同的订单 while(j < m && order[j] == order[i]) j++; int t = order[i].x;//获取订单时间 int id = order[i].y;//获取订单id int cnt = j-i; //获取数量 i = j;//将j赋值给i,处理下一批订单 score[id] -= t - last[id] - 1;//扣除掉t时刻内，没有订单时候的优先级 if(score[id] < 0) score[id] = 0;//如果优先级扣成负数了，重置为0 if(score[id] <= 3) st[id] = false;//将这个店铺从优先缓存中抽出来 //以上是t时刻之前的信息 score[id] += cnt * 2; if(score[id] > 5) st[id] = true; //更新last[id] last[id] = t; } //枚举每一个店铺 for(int i = 1; i <= n;i++) if(last[i] < T) //如果到最后的这段时间中，确实没有订单了，就扣除相应的 { score[i] -= T - last[i]; if(score[i] <= 3) st[i] = false; } int res = 0; //最后统计有多少个店铺在优先缓存中 for(int i = 1;i <= n;i++) res += st[i]; //输出结果 printf("%d\n",res); return 0; }
第十话、 2021年 模拟赛 灌溉
多种解法，主要想介绍：使用偏移量处理方位的一个小技巧+递归的复习
题目描述
解题报告
一、题目样例的分析
按照题目的位置设置花园和水管的位置，进行模拟，就可以清楚的知道为什么是9个方格了
二、解决如何改变上下左右四个位置的状态
常规的玩法可能是搞四个if判断出来，这种也是可以的，只是稍微麻烦一点，所有这里介绍一个使用偏移量的方式来解决。
int new_x = x + dx[i] , new_y = y + dy[i];
此时，对于上下左右四个方向只需要进行四次枚举就没有获得它们的坐标。
例如，现在的i是2，那么此时，new_x = x + 1，new_y = y + 0。倘若x = 3，y = 3。那么新的坐标就是(4,3)。同理，其他位置的坐标也是可以通过这个方式表示出来。
假如题目变得复杂了，是八个方向，也是可以使用相似的方式进行表示的
三、对于本题的枚举
那么本题只需要简单的枚举一遍初始情况的花园，倘若是有水管的地方，就进入递归的d f s dfsdfs函数，将它周围的方格灌溉上。最后遍历统计被灌溉的方格数量就是答案了
唯一需要注意的是使用递归的时候，不要忘记设置递归结束的条件。
参考代码(C++版本)
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 110; int g[N][N]; int re[N][N]; int n,m,k; int dx[] = {-1,0,1,0} , dy[] = {0,-1,0,1}; //补全dfs 函数 void dfs(int x,int y,int lim) //灌溉过的位置，和当前的分钟 { //递归的边界条件 if(lim >= k) return; //使用偏移量，枚举四个方向 for(int i = 0; i < 4;i++) { int a = x + dx[i] , b = y + dy[i]; //判断边界+更新状态 if((a >= 1 && a <= n) && (b >=1 && b <= m)) re[a][b] ++; //递归到下一个位置 dfs(a,b,lim+1); } } int main() { cin >> n >> m; int t; cin >> t; //录入t个水管的位置 while(t--) { int a,b; cin >> a >> b; g[a][b] = 1; re[a][b] = 1;//用于记录灌溉后的结果 } cin >>k; //枚举每个位置，找到有水管的地方，递归进去处理 for(int i = 1; i <= n;i++) { for(int j = 1; j <= m;j++ ) if(g[i][j] == 1) dfs(i,j,0); } //统计答案 int res = 0; for(int i = 1;i <= n;i++) for(int j = 1; j <= m;j++) { if(re[i][j] >= 1) res++; } cout << res << endl; return 0; }
