202603-1 山之谷
题目描述
现有一片山地,可以视为一个 行 列的网格图,第 行 列的海拔为 。
如果一个单元格的海拔不高于其所有相邻单元格(相邻包括上、下、左、右、左上、右上、左下、右下,最多 个方向)的海拔,则称该单元格为山谷。
请你数一数该片山地中有多少山谷。
输入格式
第一行包含 个整数 ,表示山地的大小。
之后 行,每行包含 个整数 ,表示海拔。
输出格式
输出 行,包含 个整数 ,表示山谷的数量。
样例输入 1
3 57 6 6 7 96 5 6 7 66 5 7 8 9样例输出 1
3提示
【样例解释】
样例 1 如图所示,绿色单元格代表山谷:

【数据范围】
保证 ,。
代码解析
这是一道经典的矩阵内枚举题目,我们可以枚举每个单元格,如果单元格周围的八个格子都大于单元格,则为山谷,答案加一。
为了避免枚举时越界,我们从 开始枚举,到 结束(越界则为 0),同时我们使用偏移数组 dx, dy 数组来表示八个方向,简化代码。
#include<bits/stdc++.h>using namespace std;int n, m, cnt, a[105][105];
bool check(int i, int j) { int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1}; for (int x = 0; x < 8; x++) for (int y = 0; y < 8; y++) if (a[i+dx[x]][j+dy[y]] < a[i][j] && a[i+dx[x]][j+dy[y]] != 0) return false; return true;}
int main() {
cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j]; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (check(i, j)) cnt++; cout << cnt;
return 0;}202603-2 礼盒排序
题目描述
商店推出了许多礼盒,每个礼盒中包含 件商品,每件商品都有一个价格。
现在需要对这些礼盒进行排序,排序规则如下:
- 先按礼盒总价格从小到大排序;
- 如果总价格相同,按礼盒中最贵商品的价格从小到大排序;
- 如果仍然相同,按礼盒中最便宜商品的价格从小到大排序;
- 如果仍然相同,按礼盒编号从小到大排序。
请输出排序后的礼盒编号。 输入格式
第一行包含两个整数 和 ,分别表示礼盒数量和每个礼盒中商品的数量。
接下来 行,每行包含 个整数,第 行表示第 个礼盒中各商品的价格。
输出格式
输出一行,包含排序后的礼盒编号(编号从 开始),用空格分隔。
样例输入 1
4 33 5 24 1 52 2 43 4 3样例输出 1
3 4 2 1提示
【样例解释】
| 编号 | 商品价格 | 总价 | 最大值 | 最小值 |
|---|---|---|---|---|
排序过程:
- 按总价排序, 号礼盒总价最小;
- 其余总价均为 ,再按最大值排序, 号最大值更小;
- 号和 号最大值相同,再按最小值排序, 号更小。
最终顺序为:
【数据范围】
保证 ,, 商品价格 。
代码解析
也是一道经典的四级常考结构体排序题目,但是注意不要陷入题目误区而去存储礼盒中所有商品的价格,对于每一个礼盒,我们只需要记录礼盒编号、礼盒总价格、礼盒中最贵商品价格、礼盒中最便宜商品价格即可。
#include<bits/stdc++.h>using namespace std;struct box { int idx, total = 0; int mi = 10005, ma = 0;};bool cmp(box a, box b) { if (a.total != b.total) return a.total < b.total; else if (a.ma != b. ma) return a.ma < b.ma; else if (a.mi != b.mi) return a.mi < b.mi; else return a.idx < b.idx;}int main() {
int n, k, p; box a[1005]; cin >> n >> k; for (int i = 0; i < n; i++) { for (int j = 0; j < k; j++) { cin >> p; // 输入商品价格时,更新礼盒总价格、最大值、最小值 a[i].idx = i+1; a[i].total += p; a[i].mi = min(a[i].mi, p); a[i].ma = max(a[i].ma, p); } } sort(a, a+n, cmp); for (int i = 0; i < n; i++) cout << a[i].idx << ' ';
return 0;}202606-1 扫雷
题目描述
小杨同学正在游玩经典游戏「扫雷」,他想自己生成一个「扫雷」的地图。
小杨同学希望生成的地图大小为 行 列,一共 个区块。区块行号为 ,列号为 。其中一些区块为雷区,其它区块不为雷区。
小杨同学指定了 个区块为雷区,而其它区块均不为雷区。小杨同学希望你帮忙计算非雷区的区块,每个区块与多少个雷区相邻?
我们定义区块相邻,当且仅当两个区块至少有一个公共顶点(也就是说对于不在地图边缘的区块,周围 个区块均与其相邻)。
输入格式
输入包含 行。
第一行,三个正整数 , 和 ,分别表示地图行数和列数,以及雷区数量。
接下来的 行,每行有 个整数,分别表示第 个雷区的行号和列号。
保证输入的雷区不重复。
输出格式
输出 行,每行 个字符(使用空格分割),对于第 行第 列,输出地图对应区块的信息:
- 如果为雷区,输出
*; - 如果不是雷区,输出其相邻雷区数量(输出 到 中的一个数字)。
样例输入 1
3 4 41 11 32 43 2样例输出 1
* 2 * 22 3 3 *1 * 2 1提示
【输出解释 1】
根据输入,在 的地图上有 个雷区,分别是 ,, 和 ,如输出样例中 * 所示,其它非雷区区块的相邻雷区数量可以直观看出。
【数据范围】
, 。
输入的雷区必定在地图内且不重复,注意行号和列号均从 开始。
代码解析
这道题比较简单,我们定义一个 bool 数组 , 表示第 行第 列是否为雷。再用一个 int 数组 来表示地图中每个格子周围相邻格子中雷的数量。
在输入数据的同时我们使用偏移数组 和 来遍历周围的 8 个方向,更新周围相邻格子中雷的数量即可,不需要输入结束后再去重新统计。
#include <bits/stdc++.h>using namespace std;int main() {
bool a[1005][1005] = {0}; int b[1005][1005] = {0}; int dx[] = {1, -1, 0, 0, 1, 1, -1, -1}; int dy[] = {0, 0, 1, -1, 1, -1, 1, -1}; int n, m, p; cin >> n >> m >> p; while (p--) { int r, c; cin >> r >> c; a[r][c] = 1; for (int i = 0; i < 8; i++) b[r+dx[i]][c+dy[i]]++; }
for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) if (a[i][j]) cout << "* "; else cout << b[i][j] << ' '; cout << endl; }
return 0;}202606-2 身高体重指数
题目描述
一个人的身高体重指数(BMI)等于其体重(千克为单位)除以其身高(米为单位)的平方。
例如,一个体重为 ,身高为 的人的身高体重指数为 。
现在有 个小朋友,第 个小朋友的编号为 ,体重为 ,身高为 。
请按照身高体重指数从高到低为小朋友们排序,数据保证不存在两个小朋友的身高体重指数完全相同。输出排序后小朋友的编号。
输入格式
输入 行,
第一行为一个正整数 ,表示小朋友的个数;
第二行为 个整数 表示小朋友们的体重,单位为 ;
第三行为 个浮点数 表示小朋友们的身高,单位为 。
输出格式
输出一行 个数,表示按照身高体重指数从高到低排序后的编号。
样例输入 1
345 33 391.55 1.33 1.44样例输出 1
3 1 2提示
【样例解释】
三个小朋友(编号依次为 ,,)的身高体重指数分别为(保留两位小数的结果):,,,故排序后输出的编号为 。
【数据范围】
,,, 均恰有两位小数。
代码解析
这是一道结构体数组的基础题,根据题意,需要对结构体数组按照
bmi排序之后,输出排序后的编号,所以我们在结构体中添加一个成员变量idx来表示原始的编号,在输入数据的过程中完成初始化,最后排序输出即可,注意编号从 开始。
#include <bits/stdc++.h>using namespace std;
struct stu { double w, h, bmi; int idx;} a[1005];
bool cmp(stu a, stu b) { return a.bmi > b.bmi;}
int main() {
int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i].w; a[i].idx = i; } for (int i = 1; i <= n; i++) { cin >> a[i].h; a[i].bmi = a[i].w / (a[i].h * a[i].h); }
sort(a+1, a+n+1, cmp); for (int i = 1; i <= n; i++) cout << a[i].idx << ' ';
return 0;}202609-1 新汉诺塔
题目描述
汉诺塔问题是最经典的递推问题之一:
有三个可以放圆盘柱子,编号为 、 和 。
开始时柱子 上套着 个圆盘,它们从上到下按照从小到大的顺序排列。
我们的任务是要把这 个圆盘移到柱子 上,并保持它们的原有顺序不变。
在移动圆盘的过程中,需要遵守以下规则:
- 圆盘只能从一根柱子顶部拿出,从另一根柱子顶部放入。
- 每次只能移动一个圆盘。
- 小圆盘必须时刻位于大圆盘之上。
小杨在学习了汉诺塔问题后,决定添加一个新规则:
- 每一次移动,圆盘只能从 移动到 ,从 移动到 ,或者从 移动到 ;其它移动是不允许的。
在新规则下,给定圆盘数量 ,试问最少移动步数是多少?
输入格式
输入一个正整数 ,表示圆盘的数量。
输出格式
输出一个整数,表示在新规则下将 个圆盘从 移动到 所需的最少移动步数。
样例输入 1
2样例输出 1
7样例输入 2
3样例输出 2
21提示
【样例解释 1】
以下步骤是最佳的(编号为 1 的是小盘,为 2 的是大盘):
- 将 1 从 移动到 ;
- 将 1 从 移动到 ;
- 将 2 从 移动到 ;
- 将 1 从 移动到 ;
- 将 2 从 移动到 ;
- 将 1 从 移动到 ;
- 将 1 从 移动到 。
可以证明没有更少步骤可以完成这个任务。
【数据范围】
对于所有数据,。
代码解析
读题可知,一个圆盘只能从 移动到 ,从 移动到 ,或者从 移动到 ,所以课上的汉诺塔解法不管用了;
这道题中,需要将汉诺塔的移动分成两种类型:
- 将
n个圆盘从当前柱子移动到下下个柱子,比如 A->B->C、B->C->A、C->A->B,用g[n]来表示步数。- 将
n个圆盘从当前柱子移动到下个柱子,比如 A->B、B->C、C->A,用f[n]来表示步数。如果我们要将
n个圆盘从 移动到 (移动到下下个柱子),那么我们需要分如下几步:
- 先将上面的
n-1个圆盘从 A->B->C,步数用g[n-1]表示;- 将
1个圆盘从 A->B,步数为1;- 将
n-1个圆盘从 C->A,步数用f[n-1]表示;- 将
1个圆盘从 B->C,步数为1;- 将
n-1个圆盘从 A->B->C,步数用g[n-1]表示;所以
g[n] = g[n-1] + 1 + f[n-1] + 1 + g[n-1]。如果我们要将
n个圆盘从 移动到 (移动到下个柱子),那么我们需要分如下几步:
- 先将上面的
n-1个圆盘从 A->B->C,步数用g[n-1]表示;- 将
1个圆盘从 A->B,步数为1;- 将
n-1个圆盘从 C->A->B,步数用g[n-1]表示;所以
f[n] = g[n-1] + 1 + g[n-1]。
#include <bits/stdc++.h>using namespace std;int main() {
int n, g[25], f[25];
cin >> n; g[1] = 2; f[1] = 1;
for (int i = 2; i <= n; i++) { f[i] = g[i-1] * 2 + 1; g[i] = g[i-1] * 2 + f[i-1] + 2; }
cout << g[n];
return 0;}202609-2 有序网格
题目描述
小 A 有一个 行 列格子组成的二维网格,从上到下依次是第 行到第 行,从左到右依次是第 列到第 列。每个格子里有一个数字,第 行第 列的格子里的数字是 。
小 A 想让二维网格变得有序,因此他先对每一行从左到右按升序排序,再对每一列从上到下按升序排序。以下是一个先完成行排序再完成列排序的例子:
小 A 想知道二维网格经过以上排序后的结果。你能编写程序帮助他吗?
输入格式
第一行,两个正整数 ,分别表示二维网格的行数与列数。
接下来 行,每行 个整数 ,表示二维网格中的数字。
输出格式
输出 行,每行 个整数,表示二维网格先完成行排序再完成列排序后的结果。
样例输入 1
3 26 54 32 1样例输出 1
1 23 45 6样例输入 2
3 41 3 2 56 2 4 45 4 1 3样例输出 2
1 2 3 51 3 4 52 4 4 6提示
【数据范围】
对于所有测试点,保证 ,,。
代码解析
这道题虽然是 T2,但是相比 T1 反而做起来更快一些,不过还是需要同学们对于二维数组有更深的理解才不容易出错;
根据题意,我们需要先对二维数组的每一行进行排序,再对每一列进行排序。数据范围较小,直接分别使用最简单的冒泡排序即可,因为每一行的元素内存地址是连续的,也可以每行用 sort。
#include <bits/stdc++.h>using namespace std;int main() {
int n, m, a[15][15]; cin >> n >> m;
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
// 对每行进行排序(如冒泡) // for (int i = 1; i <= n; i++) // for (int x = 1; x <= m-1; x++) // for (int y = 1; y <= m-x; y++) // if (a[i][y] > a[i][y+1]) // swap(a[i][y], a[i][y+1]); // 每行的元素内存地址是连续的,也可以每行用 sort for (int i = 1; i <= n; i++) sort(a[i]+1, a[i]+1+m);
// 对每列进行排序(如冒泡) for (int j = 1; j <= m; j++) for (int x = 1; x <= n-1; x++) for (int y = 1; y <= n-x; y++) if (a[y][j] > a[y+1][j]) swap(a[y][j], a[y+1][j]);
for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) cout << a[i][j] << ' '; cout << endl; }
return 0;}
陕公网安备61010302001363号