【蓝桥杯】每日四道编程题（两道真题+两道模拟）| 第四天

专栏： 蓝桥杯——每日四道编程题（两道真题+两道模拟）
“蓝桥杯就要开始了，这些题刷到就是赚到”
₍ᐢ..ᐢ₎♡
另一个专栏： 蓝桥杯——每日四道填空题（两道真题+两道模拟题）

目录

专栏： 蓝桥杯——每日四道编程题（两道真题+两道模拟）

另一个专栏： 蓝桥杯——每日四道填空题（两道真题+两道模拟题）

第一道真题（2022年省赛）：数位排序

第二道真题（2018年省赛）：全球变暖

第三道模拟题（acwing）: 不同路径数

第四道模拟题（2022年第三次模拟赛）：清理水草

---

第一道真题（2022年省赛）：数位排序

问题描述
小蓝对一个数的数位之和很感兴趣, 今天他要按照数位之和给数排序。当 两个数各个数位之和不同时, 将数位和较小的排在前面, 当数位之和相等时, 将数值小的排在前面。

例如, 2022 排在 409 前面, 因为 2022 的数位之和是 6, 小于 409 的数位 之和 13 。

又如, 6 排在 2022 前面, 因为它们的数位之和相同, 而 6 小于 2022 。

给定正整数 n, m 请问对 1 到 n 采用这种方法排序时, 排在第 m 个的元 素是多少?

输入格式
输入第一行包含一个正整数 n 。

第二行包含一个正整数 m 。

输出格式
输出一行包含一个整数, 表示答案。

样例输入
 

13
5

样例输出
 

3

样例说明
1 到 13 的排序为: 1,10,2,11,3,12,4,13,5,6,7,8,91,10,2,11,3,12,4,13,5,6,7,8,9 。第 5 个数为 3 。

这题首先要建立其原数和其数位和的联系 ，并要根据数位和排序。 

这题重点是sort函数的使用。

Sort(start,end,排序方法)：

第三个参数是排序的方法，可以是从小到大【less<数据类型>( )】也可是从大到小【greater<数据类型>()】，还可以不写第三个参数，此时默认的排序方法是从小到大排序，而且这个排序方法可以自己找参照物写 。这里就可以选择数位和为参照物进行排序，具体操作看代码！

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int a[N] , b[N] , n , m ; //a[]储存原数 ， b[]存储数位和
int sum(int num)  //求数位和
{int h = 0;while(num){h += num % 10;num /= 10;}return h;
}
bool cmp(int x , int y)  //x 和 y是比较的值。
{if(b[x] != b[y]) return b[x] < b[y]; //按数位小的排在前面return x < y; //按原数小的排在前面
}
int main()
{scanf("%d%d", &n , &m);for (int i =  1 ; i <= n ; ++i ){a[i] = i;b[i] = sum(i);}sort(a + 1 , a + n + 1 , cmp);printf("%d", a[m]);return 0;
}

这题也可以用结构体写，复习一下结构体吧：

#include <iostream>
#include <algorithm>
using namespace std;
struct sw
{int a; //原数int b; //数位和
}a[1000100];
bool cmp(sw x, sw y)
{if(x.b != y.b) return x.b < y.b;return x.a < y.a;
}
int main()
{int n, m;cin >> n >> m;for (int i = 1; i <= n; i ++){a[i].a = i;int t = a[i].a;a[i].b = 0;while (t){a[i].b += t % 10;t /= 10;}}sort(a + 1 , a + n + 1 , cmp);cout << a[m].a;return 0;
}

第二道真题（2018年省赛）：全球变暖

题目描述
你有一张某海域 NxNNxN 像素的照片，"."表示海洋、"#"表示陆地，如下所示：

.......

.##....

.##....

....##.

..####.

...###.

.......

其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。

例如上图中的海域未来会变成如下样子：

.......

.......

.......

.......

....#..

.......

.......

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

输入描述
第一行包含一个整数 N (1≤N≤1000)。

以下 N 行 N 列代表一张海域照片。

照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。、

输出一个整数表示答案。

输入样例

7
.......
.##....
.##....
....##.
..####.
...###.
.......

输出样例

1

运行限制
最大运行时间：1s
最大运行内存: 256M

算法：DFS

这题和之前我们刷的【蓝桥杯】每日四道填空题（两道真题+两道模拟题|第二天 中2022年第三次模拟赛的最大连通块这题简直不要太像，这些一个个的岛屿可以看出一个个不同的连通块，把题目的意思还原出来就是找岛屿中是否存在一个上下左右全是的陆地（关键岛）。存在则不会完全淹没，不存在则会被完全淹没。

#include <bits/stdc++.h>using namespace std;const int N=1010;int n,ans=0;
char g[N][N];
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
bool FLAG;//表示这座岛屿有没有被完全淹没，true表示被完全淹没，false表示没有被完全淹没void dfs(int x,int y)
{if(x<0||x>=n||y<0||y>=n||g[x][y]!='#')return ;g[x][y]='X'; //把找了的陆地，排除掉，千万别用'.'啊，不然会影响下面的判断的。bool flag=true;for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];if(g[nx][ny]=='.')flag=false; dfs(nx,ny);}//只要出现一个上下左右全是‘#’的陆地（关键岛），就将FLAG=false;就可以判断这个岛屿是不会被完全淹没了。//但这里还不能退出递归，需要把这个连通的岛屿搜索完，即全变成’X‘。if(flag)  FLAG=false;//FLAG=false,这座岛屿不会被完全淹没，如果最后递归完此岛屿，没有出现关键岛，那他一定会被淹没的。
}int main()
{cin>>n;for(int i=0;i<n;i++)cin>>g[i];for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(g[i][j]=='#') {FLAG=true;//默认这座岛屿被完全淹没dfs(i,j);if(FLAG) ans++;}  cout<<ans<<endl;return 0;
}

第三道模拟题（acwing）: 不同路径数

我们好像做DFS的题，一般查找了的点不需要再查找了，因此我就去找了一道需要重复查找的题~

这题要对查找的（k+1）位的数去重，首先想到的就是哈希表实现的unordered_map。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;const int N =  10;int n , m , k;
char g[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
unordered_map<string, int> h;void dfs(int a, int b, int u,string path)
{if(u == k){h[path] = 1;return;}for(int i = 0; i < 4; i++){int x = a + dx[i], y = b + dy[i];if(x >= 0 && x < n && y >= 0 && y < m){dfs(x, y, u + 1, path + g[x][y]);}}
}int main()
{cin >> n >> m >> k;k++;string path;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++)cin >> g[i][j];}for(int i = 0; i < n; i++){for(int j = 0; j < m; j++)dfs(i, j, 0, path);}cout << h.size(); //直接统计有多少个不同的键值对就行了return 0;
}

第四道模拟题（2022年第三次模拟赛）：清理水草

问题描述

小蓝有一个 n * m 大小的矩形水域，小蓝将这个水域划分为 n 行 m 列，行数从 1 到 n 标号，列数从 1 到 m 标号。每行和每列的宽度都是单位 1 。
现在，这个水域长满了水草，小蓝要清理水草。
每次，小蓝可以清理一块矩形的区域，从第 r1 行（含）到第 r2 行（含）的第 c1 列（含）到 c2 列（含）。
经过一段时间清理后，请问还有多少地方没有被清理过。

输入格式

输入第一行包含两个整数 n, m，用一个空格分隔。
第二行包含一个整数 t ，表示清理的次数。
接下来 t 行，每行四个整数 r1, c1, r2, c2，相邻整数之间用一个空格分隔，表示一次清理。请注意输入的顺序。

输出格式

输出一行包含一个整数，表示没有被清理过的面积。

样例输入1

2 3
2
1 1 1 3
1 2 2 2

样例输出1

2

样例输入2

30 20
2
5 5 10 15
6 7 15 9

样例输出2

519

评测用例规模与约定

对于所有评测用例，1 <= r1 <= r2 <= n <= 100, 1 <= c1 <= c2 <= m <= 100, 0 <= t <= 100。

这题看着其实很简单，但关键是如何优化算法，减少时耗。

这题看到子矩阵 ，我们应该马上想到二维前缀和二维差分来优化。

不熟悉一、二维前缀和一二维差分的友友，看我总结的这篇文章（点这），非常详细哦！

#include <iostream>
using namespace std;
int n, m;
int g[105][105]; //没被清理的地方都设成 0 。 
void insert(int x1, int y1, int x2, int y2) {   g[x1][y1] += 1;g[x2 + 1][y1] -= 1;g[x1][y2 + 1] -= 1;g[x2 + 1][y2 + 1] += 1;
}
int main() {int t;cin >> n >> m >> t;int x1, x2, y1, y2;for(int i = 0; i < t; i ++) {scanf("%d%d%d%d", &x1, &y1, &x2, &y2);insert(x1, y1, x2, y2);  //全是0的二维数组，它本身也是自己的二维差分数组。 }for(int i = 1; i <= n; i ++)for(int j = 1; j <= m; j ++)g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];  //清理掉的地方前缀和是1，没有清理的地方，前缀和是0 int res = 0;for(int i = 1; i <= n; i ++)for(int j = 1; j <= m; j ++)if(!g[i][j]) res ++;cout << res << endl;return 0;
}