蓝桥杯十大常见天阶功法——音之呼吸.肆之型.模拟

花街四人组邂逅小梅兄妹

• • 💓关于蓝桥，关于专栏，关于建议，关于您🌹
  • 💓对模拟和枚举的认识
  • 💓一触即发
  • • 🌟第一话、第十届蓝桥杯省赛C++B组 特别数的和
    • • 🌱题目描述
      • 🌴解题报告
      • 🌵参考代码(C++版本)
    • 🌟第二话、第四届蓝桥杯省赛C++A/B组 错误票据
    • • 🌱题目描述
      • 🌴解题报告
      • 🌵参考代码(C++版本)
    • 🌟第三话、第六届蓝桥杯省赛C++B组 移动距离
    • • 🌱题目描述
      • 🌴解题报告
      • 🌵参考代码(C++报告)
    • 🌟第四话、第八届蓝桥杯省赛C++B组 日期问题
    • • 🌱题目描述
      • 🌴解题报告
      • 🌵参考代码(C++版本）
    • 🌟第五话、第十一届蓝桥杯省赛C++A\B组 回文日期
    • • 🌱题目描述
      • 🌴解题报告
      • 🌵参考代码(C++版本)
    • 🌟第六话、第九届蓝桥杯省赛C++A组 航班时间
    • • 🌱题目描述
      • 🌴解题报告
      • 🌵参考代码(C++版本)
    • 🌟第七话、 第十一届蓝桥杯决赛C++A组 天干地支
    • • 🌱题目描述
      • 🌴解题报告
      • 🌵参考代码(C++版本)
    • 🌟第八话、 第十一届蓝桥杯省赛C++A/B组 成绩分析
    • • 🌱题目描述
      • 🌴解题报告
      • 🌵参考代码(C++版本)
    • 🌟第九话、 第十届蓝桥杯省赛C++A/C组 外卖店优先级
    • • 🌱题目描述
      • 🌴解题报告
      • 🌵参考代码(C++版本)
    • 🌟第十话、 2021年 模拟赛 灌溉
    • • 🌱题目描述
      • 🌴解题报告
      • 🌵参考代码(C++版本)
  • 💓 总结

友友们好(^-^)🌹🌹🌹，我是杨枝，一枚在算法领域迈步的呆萌的博主呀~
目前还是一只纯纯的菜汪🐶。 典型的又菜又爱闹那种👀，做不好很多事，说不好很多话，写题还总不Ac😅,还在努力还在前进👣。
因为了，你们对我来说都是是独一无二的呀💓。在点开这篇文章的那一刻，我相信，我们之间相互需要彼此啦🌹🌹
时刻谨记：认真写算法，用心去分享。不负算法，不误卿。 感谢相遇（＾㉨＾）。

---

蓝桥杯的十种呼吸法是笔者结合自己的学习筛选出来的十个知识点。本着像看漫画一样了解算法原理。当日后自己确实遇到相关的习题了，可以再回头结合着我的题解报告来加深理解喔。

---

往期精彩
🔖蓝桥杯十大常见天阶功法——水之呼吸.壹之型.递归

🔖蓝桥杯十大常见天阶功法——虫之呼吸.贰之型.二分

---

💓关于蓝桥，关于专栏，关于建议，关于您🌹

最近和执梗博主一起运营了蓝桥杯31日冲刺打卡群（因为陆陆续续的加入不便于管理，现在闭群啦，hh~）。 说一下自己的主观感受吧，从小伙伴在群里的提问中，是可以感觉，存在一部分小伙伴对蓝桥竞赛、对如何系统的学习算法、对一些基础算法的概念以及oj是怎么测评的等等，是不太清楚的。 因为我自己也还是菜狗，思考问题的方式可能也不全面，思维也还在逐渐完善。这里了，结合自身情况，浅谈自己的拙见吧🌹🌹🌹

这里是我看到的一小部分现象，作为我不是乱说的支撑吧~

一、关于蓝桥

蓝桥是可爱的OI赛制，填空题是只要一个答案，可以本地编译器把跑结果了，然后直接输出这个结果就好，对了就得分。 对于编程题就是过样例，依据样例得分，出题人设置的样例都过了，那就满分。需要注意的是：你可以调试，一旦确认提交之后，是无法再次进行修改的

我感觉比较重要的就是这些了，其他的，可以在参赛注意事项中了解到，我就不唠唠叨叨的赘述了

二、关于专栏

我自己在写的这个呼吸之法专栏是趁着看完鬼灭之刃漫画的劲儿，顺势将自己在acwing学算法，备赛蓝桥中看到常见知识点总结出来。 计划的是: 水之呼吸-壹之型-递归； 虫值呼吸-贰之型-二分； 炎之呼吸-叁之型-动态规划； 音之呼吸-肆之型-模拟； 霞之呼吸-伍之型-数论； 恋之呼吸-陆之型-双指针； 雷之呼吸-柒之型-搜索； 风之呼吸-捌之型-图论； 岩之呼吸-玖之型-贪心； 火之神乐-拾之型-高级数据结构。 初步是这种敲定的，可能存在微调，这些年蓝桥也不再是那么简单暴力了，要掌握的也就逐渐增加了。 至于写作风格，与壹之型的递归；贰之型的二分差不多，知识点加上历届真题中有代表性的。文章中真题的数量就取决于漫画吧，比如郭游篇有11集， 我这里就放了11道。 比较活泼，多图，自己也还在不断优化排版，最基本最基本来说，自己看了以后，我知道为什么要记录这个真题，可以很快的获取到它的考点是什么，需要掌握的技巧是哪些。 同时也想看我文章的小伙伴以及我自己，看着是舒服的，是没有视觉疲劳。

三、关于建议

假如您对蓝桥要考的算法有大致的知识框架了，自己也是练真题了，那我更建议您订阅我好兄弟执梗的文章。他更的每篇文章是一套蓝桥真题，对您更有帮助。

我把它主页放这里了：

执 梗 — 个人简介：生与夜叉，忠于桔梗，意为执梗。记录学习历程，分享心中所爱

假如您对蓝桥、对算法竞赛大致的考点不太熟悉，你可以跟着我这个博客学习，我自己用通俗易懂的话把知识点总结出来，同时放上一系列十分具有代表性的例题。 我自己的建议是先大致看一遍文章，心中有个印象就可以了，心中知道：有篇博客讲过这个知识点，还有很多真题。我今天刚好遇到这个真题了，结合着这位博主的题解和总结再理解一下这个知识点。

四、关于您

假如您在冲刺群了，希望跟着小伙伴们一起打卡，里面的讨论氛围真的很好了。倘若自己应该还有额外的练习，那么这个月150+ 的刷题量应该是有的，根据我了解的，省赛拿奖怎么都没有问题的啦~ 假如您有自己的集训队，这是最好的啦~，好好跟着训练😜 假如都没有，那就得对自己严格一些了，记住为学日进，相信乾坤未定🌹🌹🌹

---

好啦~正式进去花街，开始游郭篇的历练了

💓对模拟和枚举的认识

模拟其实是一个比较宽泛的概念了，一般来说，不是常规的最短路问题，比如它不是用动归规划解决的最优解，不是贪心，也不是最短路问题的时候，就可以考虑能否用模拟结合枚举进行解题。

枚举这个理念的出现倒是比较直接简单了，在认知中，就是循环嘛。
简单来说，也就是暴力嘛。这个了，确实是这么一回事儿。

可能人人都会写枚举，但不一定写出来的枚举就可以Ac。正是因为枚举的思想是挺直接简单的，所以枚举的考点放在了细节的处理上。

待会就系统结合的枚举的历年真题，切实的感受一下它的玩法，以及总结一些枚举中经常用到的小技巧和思考方向

枚举首先要考虑的是如何在遍历的途中，把咱们需要的答案查找出来。

既然是可以直接暴力获得部分的分，那么就可以通过题目中隐藏的信息进行优化的。

还有一个比较重要的知识是，如何通过给定的数据范围确定自己最多可以进行几重循环。这个我在壹之型中总结了。

因为没有模板，模拟的题了，要么都会，此时需要注意的是细节；要么都不会。

不像其他算法，比如，我忘记SPFA的模板怎么写了，执梗记得，那么我就没有这个分了。模拟说直白点了，确实就是循环，但是怎么循环也是一门学问了，看能不能get到题目中的隐藏的信息，以及处理好一些小技巧。模拟的题，细节是真的多。

---

💓一触即发

🌟第一话、第十届蓝桥杯省赛C++B组 特别数的和

这道题是热身的，就不存在特别需要注意的点啦~

进入题目描述环节

🌱题目描述

原题传送门

🌴解题报告

这个题算是枚举中相当乖的一道题了，读完题目以后，脑海中确实很难把它归纳到某一类专门的算法中，此时就乖乖的拿出我们的枚举大法吧。

解题思路：

枚举输入的范围内的中每一个数，然后将这个数，比如是39，用取模运算符和整除运算符将39中的每一位都取出来。
最后用语句$if$来判断是否含有$2、0、1、9$这几个数字。

🌵参考代码(C++版本)

#include #include #include 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$行数据进行排序之后，再逐一枚举这$n$个数。

如果相邻的两个数的数值相同，就是重号；如果相邻的两个数，数值只差大于等于2，比如$3$和$5$。那么就是断号

比较棘手同时也是需要掌握的是这道题的输入技巧。【重点】

1、掌握cin的读取原理：

当 cin读取数据时，它会传递并忽略任何前导白色空格字符（空格、制表符或换行符）。

一旦它接触到第一个非空格字符即开始读取，当它读取到下一个空白字符时，它将停止读取。
因为咱们要读取的这串数据中有太多空格，而且数量也是未知，所以cin和scanf都劝退

2、getline函数

为了解决这个问题，可以使用 getline 这个函数。它可读取整行，包括前导和嵌入的空格，并将其存储在字符串对象中。

使用的语法如下：

getline(cin, inputLine);//其中 cin 是正在读取的输入流，而 inputLine 是 string 类型的变量，用于接收输入的字符串//题目中的使用代码 getline(cin,line);

3、stringstream快速实现string类型和int类型之间的转换

定义了三个类：istringstream、ostringstream 和 stringstream，分别用来进行流的输入、流的输出和流的输入输出操作。

🌵参考代码(C++版本)

#include #include #include #include #include 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 = a[i-1]+2) res1 = a[i]-1;//断号 cout <<  res1 << ' ' << res2 << endl; return 0;}

🌟第三话、第六届蓝桥杯省赛C++B组 移动距离

移动距离主要想让大家了解曼哈顿距离，其次是再次熟悉一下映射的思想。

🌱题目描述

原题传送门

🌴解题报告

这道题应该是可以用宽搜来做的，一题可以多解，但是打比赛的时候，找到一个对于自己而言，选择一个写起来简单，也不容易错的算法就好。

对于折线求最短路径，可以使用几何学中的曼哈顿距离进行求解。结合公式，只要知道两个位置的坐标，就可以快速算出距离。

曼哈顿距离概述：

曼哈顿距离的命名原因是从规划为方型建筑区块的城市（如曼哈顿）间，最短的行车路径而来。

曼哈顿距离的计算：

在平面上，坐标 （ x 1, y 1） （x_1, y_1） （x1​,y1​）的点 P 1P_1 P1​与坐标 （ x 2, y 2） （x_2, y_2） （x2​,y2​）的点 P 2P_2 P2​的曼哈顿距离为：
$d(x,y)$ = | x 1− x 2x_1-x_2 x1​−x2​| + | y 1− y 2y_1-y_2 y1​−y2​|

咱们生活中零零散散的还有其他距离的定义，感兴趣的小伙伴可以了解一下呀~
其他距离的拓展

映射思想：

现在咱们的目标是出楼号$m$和楼号$n$的坐标，然后带入公式中就可以顺利求解

通过映射，我们让所有数都减1，在总数量不变的情况下，行号和列号都是从0开始的时候，回到咱们熟悉的二维数组的形式，那么可能更好发现规律，作图一看，确实是的

从一般到特殊的思考方向：

好啦，这道题最主要的是掌握住曼哈顿距离和映射的思想，咱们学的应该是思想。

🌵参考代码(C++报告)

//考察的是曼哈顿距离加上一些映射思想#include #include #include 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 #include #include #include 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 #include #include 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  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;

同时也记住，时间进行比较时，统一算成和当天0时0分0秒相差的秒数

4、碎碎念

可能有小伙伴觉得，天呀，好多要记得嗷~这是学习算法吗，感觉像学语文了 在acwing求学的时候，y总说过一句，大概是这种的(记不得原话了，可恶)： 所有存在时间限制的事儿，比如考试，都不是让我们去创造，而是回忆自己的所学，再类推到当前问题。包括学习也是这么一回事，我们是理解并记忆前人留下的知识。 我高中数学老师，平时喊他阳哥，他喜欢吐槽我们不记忆题型，经常说的一句话是我清楚的记得这个题，在哪一年真题的第几题，不信你去翻，不是的话，我今天操场luo 奔。这可能就是中国数学协会会员的底气吧~ 所以不要这么抗拒记忆喔~

🌵参考代码(C++版本)

#include #include #include #include #include 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 #include #include #include 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 #include #include #include 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、然后从前向后枚举每个订单

纯暴力是枚举的每一个时刻，时间复杂度是 O ( N 2) O(N^2) O(N2)，会超时的。
在循环中，每次处理的是一批相同的订单了（可以理解为，只要这个时间点和其对应的店铺Id是相同的，就把它们看做一个整体，实现每次处理一批订单）

假设当前订单为第$i$个，利用循环判断后面有没有相同的订单(也就是在相同的订单时间$t$，店铺的编号$id$相同)。

当到第$j$个订单时，订单不相同了，那么此时这批订单的数量应该是$cnt=j-i$

下次$for$循环从j从开始处理下一批订单

记录此时t和id，计算id的优先权，有两部分需要处理

第一部分：

计算上一个拿到订单的时间$last[id]$和$t$之间，因为没有订单，所有都要减1，那么没有订单的数量是$t-last[id]-1$（最后要补一个-1是因为，$t$和$last[id]$都有订单，比如2和5，第2时刻和第3时刻都有订单，那么没有订单的时刻就是3，4）

计算优先权，如果此时为负值，那么将优先权重置为0。

如果优先权小于等于3了，将这个店铺从优先缓存中剔除，即 ：$st[id]=false$

第二部分：
$t$时刻拿到订单，并且数量为$cnt$,这个店铺的优先权要加上$2\ast cnt$。

计算优先权，如果大于5，放入优先缓存中 ，即：$st[id]=true$;

因为相同的订单已经处理过了，就不需要再计算了，直接到j这个出现下一批订单的位置开始新的一轮循环。

for(int i = 0; i < m;)......i = j;

循环到最后，将上一次拿到订单的时间$last[id]$更新为$t$

3、最后的处理

如果最后一个订单的时刻为T，那么倒是不用处理了。
如果不是T，那么最后一个订单到T时刻这部分扣除优先级的减法需要我们补上。

即，减去最后一个订单时刻与T的差值。因为T时刻也没有订单，所有这里不用减一了。

判断优先级，假如小于等于3，清除出优先缓存中。最后遍历优先缓存，得到的数量就是题目的答案

🌵参考代码(C++版本)

#include #include #include #include #define x first#define y secondusing namespace std;typedef pair 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]   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)。同理，其他位置的坐标也是可以通过这个方式表示出来。

假如题目变得复杂了，是八个方向，也是可以使用相似的方式进行表示的

三、对于本题的枚举

那么本题只需要简单的枚举一遍初始情况的花园，倘若是有水管的地方，就进入递归的$dfs$函数，将它周围的方格灌溉上。最后遍历统计被灌溉的方格数量就是答案了

唯一需要注意的是使用递归的时候，不要忘记设置递归结束的条件。

🌵参考代码(C++版本)

#include #include #include #include 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 m) //灌溉过的位置，和当前的分钟{    //递归的边界条件    if(m >= k) return; //使用偏移量，枚举四个方向    for(int i = 0; i = 1 || b >= 1 || a <= n || b > 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 = 1) res++;     }    cout << res << endl;    return 0;}

好像打不够十一话了…

暂时没有物色到比较有亮点又适合拿来讲解的模拟题了，就定11话吧，假如后续我发现不错的真题了，我会补充上来的喔~ 壹之型和贰之型的排版我最近也会重新调整一下，就包括整个专栏的文章，我都是会一直维护、优化、纠正的的🌹🌹🌹。

💓 总结

花街的游历到此就结束了，有辛苦的时刻，也有轻松的时刻叭~。 打个小总结了，模拟的题，注意细节。时间日期问题注意中日期是否合法，统计数量的题，是否少考虑了等于这种情况。平时多积累一点小技巧和套路。在考场上就很开心啦~

准备向锻刀村出发啦，解锁炭炭新装备——缘一先生的赫刀