第十三届蓝桥杯模拟赛（第三期）试题与题解

1、试题A

【问题描述】

​ 请问十六进制数 2021ABCD 对应的十进制是多少？

题解：数制转换

十六进制中 A ~ F 表示 10 ~ 15，最后可用 %x 占位符输出十六进制验算一下

//答案 539077581
#include <iostream>
using namespace std;int main() {string s = "2021ABCD";int bac = 1, ans = 0, tmp;for (int i = s.length() - 1; i >= 0; i--) {if (s[i] >= '0' && s[i] <= '9') {tmp = s[i] - '0';}else tmp = 10 + s[i] - 'A';ans += tmp * bac;bac *= 16;}cout << ans << endl;printf("%x\n", ans);	//输出十六进制验算return 0;
}

//答案 539077581
#include <iostream>
#include <cmath>
using namespace std;int main() {int ans = 0;ans +=  13;ans +=  12 * 16;ans +=  11 * pow(16, 2);ans +=  10 * pow(16, 3);ans +=  1 * pow(16, 4);ans +=  2 * pow(16, 5);ans +=  2 * pow(16, 7);cout << ans << endl;printf("%x\n", ans);return 0;
}

2、试题B

【问题描述】

​ 如果一个整数 M 同时是整数 A 和 B 的倍数，则称 M 是 A 和 B 的公倍数，公倍数中最小的一个正整数称为最小公倍数。

例如：2021 和 86 的最小公倍数是 4042。

请问在 1（含） 到 2021（含） 中，有多少个数与 2021 的最小公倍数是 4042。

题解：枚举

//答案 89
#include <iostream>
using namespace std;int gcd(int a, int b) {return (a % b == 0) ? b : gcd(b, a % b);
} 
int lcm(int a, int b) {return a / gcd(a, b) * b;
}int main() {int ans = 0;for (int i = 1; i <= 2021; i++) {if (lcm(i, 2021) == 4042) {ans++;}}cout << ans << endl;return 0;
}

3、试题C

【问题描述】

​ 10 是一个非常特殊的数，它可以表示成两个非负整数的平方和，10 = 3 * 3 + 1 * 1。

​ 9 也是同样特殊的数，它可以表示成 9 = 3 * 3 + 0 * 0。

请问，在 1 到 2021 中有多少个这样的数？

请注意，有的数有多种表示方法，例如 25 = 5 * 5 + 0 * 0 = 3 * 3 + 4 * 4，在算答案时只算一次。

题解：枚举

//答案 624
#include <iostream>
using namespace std;int main() {int a[2022] = {0};int ans = 0;for (int i = 0; i <= 200; i++) {for (int j = 0; j <= i; j++) {int tmp = i * i + j * j;if (tmp <= 2021) a[tmp] = 1;}}for (int i = 1; i <= 2021; i++) {ans += a[i];}cout << ans << endl;return 0;
}

4、试题D

【问题描述】

​ 下面是一个8个结点的无向图的邻接矩阵表示，其中第 i 行第 j 列表示结点 i 到结点 j 的边长度。当长度为 0 时表示不存在边。

0 9 3 0 0 0 0 9
9 0 8 1 4 0 0 0
3 8 0 9 0 0 0 0
0 1 9 0 3 0 0 5
0 4 0 3 0 7 0 6
0 0 0 0 7 0 5 2
0 0 0 0 0 5 0 4
9 0 0 5 6 2 4 0

​ 请问，这个图的最小生成树大小的多少？

题解：最小生成树

将所有的边长按从小到大排列，每次取最小的边连接两节点，若两节点已经处于连通状态，则不连接

循环上面的步骤，知道所有节点都已经连通，所有边之和就是答案

联通结果如下：(节点编号从 0 开始，在纸上画画更清楚)

1 → 3 (边长 1 )，5 → 7 (边长 2 )，0 → 2 (边长 3 )，3 → 4 (边长 3 )，6 → 7 (边长 4 )，3 → 7 (边长 5 )，1 → 2 (边长 8 )，

答案为：1 + 2 + 3 + 3 + 4 + 5 + 8 = 26

可以得出答案的程序如下：（用并查集查找两节点是否已经连通）

//将题中邻接矩阵作为输入可得到答案
#include <bits/stdc++.h>
using namespace std;
const int n = 8;
int f[n], ans = 0;
vector<pair<int, int> > a;int findf(int idx) {if (f[idx] == idx) return idx;f[idx] = findf(f[idx]);return f[idx];
}int main() {for (int i = 0; i < n; i++) {f[i] = i;}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {int len;cin >> len;if (len) {	//这里将i和j压缩成一个数了a.push_back(make_pair(len, i * 100 + j));}}}sort(a.begin(), a.end());for (int i = 0; i < a.size(); i++) {int len = a[i].first;int x = a[i].second / 100;int y = a[i].second % 100;if (findf(x) != findf(y)) {f[f[x]] = f[y];ans += len;printf("%d --> %d (%d)\n", x, y, len);}}cout << ans << endl;return 0;
}

5、试题E

【问题描述】

​ 下面是一个20*20的矩阵，矩阵中的每个数字是一个1到9之间的数字，请注意显示时去除了分隔符号。

69859241839387868941
17615876963131759284
37347348326627483485
53671256556167864743
16121686927432329479
13547413349962773447
27979945929848824687
53776983346838791379
56493421365365717745
21924379293872611382
93919353216243561277
54296144763969257788
96233972513794732933
81443494533129939975
61171882988877593499
61216868895721348522
55485345959294726896
32124963318242554922
13593647191934272696
56436895944919899246

​ 矩阵中一个子矩阵的值是指子矩阵中所有数值的和。

​ 请问，矩阵中值最大的一个 5 * 5 的子矩阵的值是多少？

方法一：暴力求和

数据范围不大可以暴力

//将题中矩阵作为输入可得到答案
//答案 154
#include <bits/stdc++.h>
using namespace std;
const int n = 20;
int a[n][n], ans = 0;
int get_sum(int x, int y) {	//求和复杂度O(n^2) int sum = 0;for (int i = x - 4; i <= x; i++) {for (int j = y - 4; j <= y; j++) {sum += a[i][j];}}return sum;
}
int main() {for (int i = 0; i < n; i++) {string s;cin >> s;for (int j = 0; j < n; j++) {a[i][j] = s[j] - '0';}}for (int i = 4; i < n; i++) {for (int j = 4; j < n; j++) {ans = max(ans, get_sum(i, j));}}cout << ans << endl;return 0;
}

方法二：一维前缀和

//纵坐标偏移1
//答案 154
#include <bits/stdc++.h>
using namespace std;
const int n = 20;
int a[n][n + 1], ans = 0;int get_sum(int x, int y) {	//求和复杂度O(n) int sum = 0;for (int i = x - 4; i <= x; i++) {sum += a[i][y] - a[i][y - 5];}return sum;
}int main() {for (int i = 0; i < n; i++) {string s;cin >> s;for (int j = 0; j < n; j++) {a[i][j + 1] = s[j] - '0';a[i][j + 1] += a[i][j];}}for (int i = 4; i < n; i++) {for (int j = 5; j <= n; j++) {ans = max(ans, get_sum(i, j));}}cout << ans << endl;return 0;
}

方法二：二维前缀和

//横纵坐标均偏移1
//答案 154
#include <bits/stdc++.h>
using namespace std;
const int n = 20;
int a[n + 1][n + 1], ans = 0;int get_sum(int x, int y) {	//求和复杂度O(1) return a[x][y] - a[x - 5][y] - a[x][y - 5] + a[x - 5][y - 5];
}int main() {for (int i = 0; i < n; i++) {string s;cin >> s;for (int j = 0; j < n; j++) {a[i + 1][j + 1] = s[j] - '0';a[i + 1][j + 1] += a[i + 1][j] + a[i][j + 1] - a[i][j];}}for (int i = 5; i < n; i++) {for (int j = 5; j <= n; j++) {ans = max(ans, get_sum(i, j));}}cout << ans << endl;return 0;
}

6、试题F

【问题描述】

​ 小蓝要写一个网页显示一些商品。

​ 商品总共有 t 个，按顺序由 1 到 t 编号，每页显示 a 个，请问第 p 页显示的最小和最大编号是多少？

【输入格式】

​ 输入一行包含三个整数 t、a、p，相邻整数之间用一个空格分隔。

【输出格式】

​ 输出一行包含两个整数，分别表示最小和最大编号。

【样例输入】

31 10 3

【样例输出】

21 30

【样例输入】

31 10 4

【样例输出】

31 31

【评测用例规模与约定】

​ 对于所有评测用例，1 <= t <= 1000，1 <= a <= 100，1 <= p。保证第 p 页至少显示一个商品

题解

最小编号是 a * (p - 1) + 1，最大编号是 min(t, a * p)

#include <iostream>
using namespace std;int main() {int t, a, p;cin >> t >> a >> p; cout << a * (p - 1) + 1 << " " << min(t, a * p) << endl;return 0;
}

7、试题G

【问题描述】

​ 给定一个正整数 n，请判断 n 的所有数位上的值是否从左到右是严格递增的。

​ 例如：1589 是严格递增的 。

​ 再如：1336 不是严格递增的，中间有相同的 3。

​ 再如：1598 不是严格递增的。

【输入格式】

​ 输入一行包含一个正整数 n。

【输出格式】

​ 如果是严格递增的，输出“YES”（全大写），否则输出“NO”（全大写）。

【样例输入】

1589

【样例输出】

YES

【样例输入】

1336

【样例输出】

NO

【评测用例规模与约定】

​ 对于所有评测用例，1 <= n <= 1000000000。

题解：数字拆分

#include <iostream>
using namespace std;bool check(int x) {int last = 10;while (x) {int tmp = x % 10;if (tmp >= last) return false;last = tmp;x /= 10;}return true;
}
int main() {int n, last = 10;cin >> n;if (check(n)) cout << "YES" << endl;else cout << "NO" << endl;	return 0;
}

8、试题H

【问题描述】

​ 小蓝将自己的车停在路边，在同一天将车开走。给定停车时间和开走时间，请问小蓝停了多长时间？

【输入格式】

​ 输入两行，第一行包含停车时间，第二行包含开走时间。

​ 每个时间的格式为 HH:MM:SS，其中 HH 表示时，值为 0 到 23 的整数，如果小于 10 用 0 补齐两位；MM 和 SS 分别表示分和秒，值为 0 到 59 的整数，小于 10 时用 0 补齐两位。

【输出格式】

​ 输出总共停车的时间，格式为 HH:MM:SS。

【样例输入】

08:58:10
17:20:31

【样例输出】

08:22:21

题解

用C语言中的占位符控制输出更方便

#include <cstdio>int main() {int begin, end, ans;int hh, mm, ss;scanf("%d:%d:%d", &hh, &mm, &ss);begin = hh * 3600 + mm * 60 + ss;scanf("%d:%d:%d", &hh, &mm, &ss);end = hh * 3600 + mm * 60 + ss;ans = end - begin;printf("%02d:%02d:%02d\n", ans / 3600, (ans / 60) % 60, ans % 60);return 0;
}

9、试题 I

【问题描述】

​ n 个运动员参加一个由 m 项运动组成的运动会，要求每个运动员参加每个项目。

​ 每个运动员在每个项目都有一个成绩，成绩越大排名越靠前。每个项目，不同运功员的成绩不会相同，因此排名不会相同。（但是不同项目可能成绩会相同）

​ 每个项目的前 k 名分别获得 k 到 1 分，第 i 名获得 max(k+1-i, 0) 分。

​ 每个运动员的总分就是他在每个项目上获得的分数之和。

​ 请计算每个运动员的总分。

【输入格式】

​ 输入的第一行包含两个整数 n, m, k，用一个空格分隔。

​ 接下来 n 行，每行包含 m 个整数，第 i 行第 j 个整数表示第 i 个运动员在第 j 项比赛的成绩。

【输出格式】

​ 输出一行包含 n 个整数，依次表示每个运动员的总分，相邻的整数之间用一个空格分隔。

【样例输入】

3 5 2
5 3 1 5 12
2 4 2 34 1
8 6 3 2 2

【样例输出】

4 4 7

【样例说明】

​ 第 1 个运动员得分为：1+0+0+1+2=4
​ 第 2 个运动员得分为：0+1+1+2+0=4
​ 第 3 个运动员得分为：2+2+2+0+1=7

【评测用例规模与约定】

​ 对于 50% 的评测用例，2 <= n, m, k <= 20，0 <= 成绩 <= 1000。
​ 对于所有评测用例，2 <= n, m, k <= 100，0 <= 成绩 <= 10000。

题解：状压排序

由于运动员个数不超过 100 名，可以将成绩乘以 107 再加上运动员的编号，进行状态压缩，当然也可以用 pair

用矩阵竖着放，每行存某项运动每名运动员的成绩与编号，然后对每行降序排序

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
int a[MAXN][MAXN];
int ans[MAXN];bool cmp(int x, int y) {return x > y;
}int main() {int n, m, k;cin >> n >> m >> k;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> a[j][i];a[j][i] = a[j][i] * 107 + i;}}for (int i = 0; i < m; i++) {sort(a[i], a[i] + n, cmp);for (int j = 0; j < k && j < n; j++) {int idx = a[i][j] % 107;ans[idx] += k - j;}}for (int i = 0; i < n; i++) {cout << ans[i];if (i != n - 1) cout << " ";}cout << endl;return 0;
}

10、试题J

【问题描述】

​ 给定 n 个整数 a[1], a[2], …, a[n]，小蓝希望在中间选出一部分，满足以下两个条件：

​ 1、对于某个下标集合 S，选出的数中有至少 k 个下标在集合 S 中；

​ 2、选出的数按照原来的顺序排列，是严格单调上升的，即选出的是一个上升子序列。

​ 请问小蓝最多能选出多少个数。

【输入格式】

​ 输入的第一行包含两个整数 n, k，用一个空格分隔。

​ 第二行包含 n 个整数 a[1], a[2], …, a[n]，相邻的整数间用空格分隔。

​ 第三行包含一个长度为 n 的01串，依次表示每个下标是否在集合 S 中，为 0 表示不在 S 中，为 1 表示在 S 中。

【输出格式】

​ 输出一行包含一个整数，表示答案。如果没有满足条件的选法，输出-1。

【样例输入】

8 2
8 1 2 3 9 4 7 10
10001010

【样例输出】

3

【样例说明】

​ 由于 8、9、7 三个数中至少要选 2 个，只能选 8 和 9，剩下的数只能选最后一个数 10。

【样例输入】

8 3
8 1 2 3 9 4 7 10
10001010

【样例输出】

-1

【 评测用例规模与约定】

​ 对于 30% 的评测用例，2 <= n <= 100，0 <= a[i] <= 100, 0 <= k <= 3。
​ 对于所有评测用例，2 <= n <= 1000，0 <= a[i] <= 100000, 0 <= k <= 20。

暴力深搜

连 30% 的样例都过不了…

希望有大佬能够指点一二

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;int a[MAXN];
string s;
int n, k, ans = -1;
void dfs(int cnt, int len, int idx) {if (s[idx] == '1') cnt++;len++;if (idx == n - 1 && cnt >= k) {ans = max(ans, len);}for (int i = idx + 1; i < n; i++) {if (a[i] > a[idx]) {dfs(cnt, len, i);}}
}int main() {
//	freopen("input.txt", "r", stdin);cin >> n >> k;for (int i = 0; i < n; i++) {cin >> a[i];}cin >> s;for (int i = 0; i < n; i++) {dfs(0, 0, i);}cout << ans << endl;return 0;
}