C/C++教程
第十三届蓝桥杯模拟赛（第三期）试题与题解 C++
第十三届蓝桥杯模拟赛（第三期）试题与题解
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;
}
-
怎么切换 Git 项目的远程仓库地址？-icode9专业技术文章分享12-24
-
怎么更改 Git 远程仓库的名称？-icode9专业技术文章分享12-24
-
更改 Git 本地分支关联的远程分支是什么命令？-icode9专业技术文章分享12-24
-
uniapp 连接之后会被立马断开是什么原因？-icode9专业技术文章分享12-24
-
cdn 路径可以指定规则映射吗？-icode9专业技术文章分享12-24
-
CAP：Serverless?+AI?让应用开发更简单12-24
-
新能源车企如何通过CRM工具优化客户关系管理，增强客户忠诚度与品牌影响力12-23
-
原创tauri2.1+vite6.0+rust+arco客户端os平台系统|tauri2+rust桌面os管理12-23
-
DevExpress 怎么实现右键菜单（Context Menu）显示中文？-icode9专业技术文章分享12-23
-
怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享12-22
-
el-tabs 组件只被引用了一次，但有时会渲染两次是什么原因？-icode9专业技术文章分享12-22
-
wordpress有哪些好的安全插件？-icode9专业技术文章分享12-22
-
wordpress如何查看系统有哪些cron任务？-icode9专业技术文章分享12-22
-
Svg Sprite Icon教程：轻松入门与应用指南12-21
-
Excel数据导出实战：新手必学的简单教程12-20
