第十二届蓝桥杯大赛软件类省赛C++研究生组

2023-10-10 05:40
文章标签 c++ 软件 蓝桥 研究生 大赛 第十二届 类省赛

本文主要是介绍第十二届蓝桥杯大赛软件类省赛C++研究生组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

  • A 卡片（5分，√）
  • B 直线（5分，√）
  • C 货物摆放（10分，√）
  • D 路径（10分，√）
  • E 回路计数（15分，√）
  • F时间显示（15分，√）
  • G砝码称重（20分，√）
  • H 异或数列（20分）
  • I 双向排序（25分）
  • J 分果果（25分）

题目是全的，但是由于能力有限，后面有题目没做，分值和完成情况在题目后说明

A 卡片（5分，√）

题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小蓝有很多数字卡片，每张卡片上都是数字 0 到 9。 小蓝准备用这些卡片来拼一些数，他想从 1 开始拼出正整数，每拼一个， 就保存起来，卡片就不能用来拼其它数了。 小蓝想知道自己能从 1 拼到多少。 例如，当小蓝有 30 张卡片，其中 0 到 9 各 3张，则小蓝可以拼出 1 到 10， 但是拼 11 时卡片 1 已经只有一张了，不够拼出 11。 现在小蓝手里有 0 到 9 的卡片各 2021 张，共 20210 张，请问小蓝可以从 1 拼到多少？ 提示：建议使用计算机编程解决问题

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;int main()
{int arr[10] = {0};for(int i = 0; i < 10; i ++){arr[i] = 2021;}int minx = 2021;int n = 1;int flag;while(minx > 0){int m = n;while(m > 0 ){if(minx == 0){n --;break;}int tmp = m % 10;arr[tmp] -= 1;minx = min(minx, arr[tmp]);m /= 10;}n ++;}printf("%d\n", n);return 0;
}

B 直线（5分，√）

题目描述
在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上， 那么这些点中任意两点确定的直线是同一条。

给定平面上2×3个整点{(x,y)|0 ≤ x < 2, 0 ≤ y < 3, x ∈ Z, y ∈ Z}，即横坐标 是0到1 (包含0和1)之间的整数、纵坐标是0到2 (包含0和2)之间的整数 的点。这些点一共确定了 11 条不同的直线。

给定平面上20×21个整点{(x,y)|0 ≤ x < 20,0 ≤ y < 21,x ∈ Z,y ∈ Z}，即横 坐标是0到19 (包含0和19)之间的整数、纵坐标是0到20 (包含0和20)之 间的整数的点。请问这些点一共确定了多少条不同的直线。

利用两点式方程：(y - y1) / (x - x1) = (y2 - y1) / (x2 - x1)，化简后得：
y = [(y2 - y1) / (x2 - x1)] *x + (x1 * y2 - x2 * y1) / (x2 - x1),
从而得到斜率和截距。
注意：不能用y = kx + b，如：先用两点求出斜率k，再将斜率k和任一点带入求得b，这样会因为精度不准而导致结果错误。
int a = 6;
double b = 1.99;
double c = 1.999999999999;
double d = a * 1.0 / b;
double e = a * 1.0 / c;
cout << "a / b = " << d << “\n”; //3.01508
cout << "(a / b) * 3 = " << d * 3 << “\n”; // 9.04523
cout << "a / c = " << e << “\n”; //3
cout << "(a / c) * 3 = " << e * 3 << “\n”; //9

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;vector<pair<int, int>> all; //存放所有的点
set<pair<double, double>> res; //存放所有直线的斜率和截距int main()
{//获得所有的点for(int i = 0; i < 20; i ++){for(int j = 0; j < 21; j ++){all.push_back(make_pair(i, j));}}//每两个点组成一条直线for(int i = 0; i < all.size(); i ++){int x1 = all[i].first;int y1 = all[i].second;for(int j = 0; j < all.size(); j ++){int x2 = all[j].first;int y2 = all[j].second;if(x1 != x2){//确保分母不为0，即两点的x值不同double k = (y2 - y1) * 1.0 / (x2 - x1); //斜率double b = (x1 * y2 - x2 * y1) * 1.0 / (x2 - x1); //截距res.insert(make_pair(k, b));}}}//40257printf("%d\n", res.size() + 20); // 两点的x值相同的直线有20条（0<=x<20）return 0;
}

C 货物摆放（10分，√）

题目描述
小蓝有一个超大的仓库，可以摆放很多货物。

现在，小蓝有 nn 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。

小蓝希望所有的货物最终摆成一个大的长方体。即在长、宽、高的方向上分别堆 L、W、H 的货物,满足 n=L×W×H。

给定 n，请问有多少种堆放货物的方案满足要求。

例如，当 n = 4 时，有以下 6 种方案：1×1×4、1×2×2、1×4×1、2×1×2、2 × 2 × 1、4 × 1 × 1。

请问，当 n = 2021041820210418 （注意有 16 位数字）时，总共有多少种方案？

提示：建议使用计算机编程解决问题。

答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;int main()
{long long n = 2021041820210418;int nn = int(pow(n, 1.0 / 2));long long arr[3000] = {0};int nums = 0;for(int i = 1; i <= nn; i ++){if(n % i == 0){arr[nums ++] = i;if(i != nn){arr[nums ++] = n / i;}}}int countn = 0;for(int i = 0; i < nums ;i ++){for(int j = 0; j < nums; j ++){for(int k = 0; k < nums; k ++){if(arr[i] * arr[j] * arr[k] == n){countn ++;}}}}printf("%d\n", countn);return 0;
}

D 路径（10分，√）

题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图 中的最短路径。

小蓝的图由 2021 个结点组成，依次编号 1 至 2021。

对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。

例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。

请计算，结点 1 和结点 2021 之间的最短路径长度是多少。

提示：建议使用计算机编程解决问题。

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
int main()
{int arr[2025] = {0};memset(arr, 0x3f, sizeof(arr));arr[1] = 0;for(int i = 1; i <= 2021; i ++){for(int j = i + 1; j - i <= 21 && j <= 2021; j ++){arr[j] = min(arr[j], arr[i] + (i * j) / __gcd(i , j));}}printf("%d\n", arr[2021]);return 0;
}

E 回路计数（15分，√）

题目描述：
蓝桥学院由 2121​​​ 栋教学楼组成，教学楼编号 11​​ 到 2121​​。对于两栋教学楼 aa​​ 和 bb​，当 aa​ 和 bb​ 互质时，aa 和 bb 之间有一条走廊直接相连，两个方向皆可通行，否则没有直接连接的走廊。

小蓝现在在第一栋教学楼，他想要访问每栋教学楼正好一次，最终回到第一栋教学楼（即走一条哈密尔顿回路），请问他有多少种不同的访问方案？

两个访问方案不同是指存在某个 ii，小蓝在两个访问方法中访问完教学楼 ii 后访问了不同的教学楼。

提示：建议使用计算机编程解决问题。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int all = 1 << 21;int arr[25][25] = {0};
ll dp[all][21] = {0};  //dp[x][i]:在x状态时，到达i栋楼的路径数int main()
{//若i, j最小公因数为1即两栋楼之间有通路，arr[i][j] = arr[j][i] = 1for(int i = 0; i < 21; i ++){for(int j = i + 1; j < 21; j ++){if( __gcd(i + 1, j + 1) == 1){arr[i][j] = arr[j][i] = 1;}}}dp[1][0] = 1;for(int x = 1; x < all; x ++){ //遍历所有情况//该情况下包括第0栋楼if(x & 1){for(int i = 0; i < 21; i ++){//某情况下包括第i栋楼if((x >> i) & 1){//与第i栋楼相连的楼for(int j = 0; j < 21; j ++){int tmp = x ^ (1 << i);//第i栋楼不在x状态下且j栋楼在x状态下，同时i与j之间有通路if((tmp >> j) & 1 & arr[i][j]){//到达i楼的路径数加经过j栋楼到达i的路径数dp[x][i] += dp[tmp][j];}}}}}}ll countn = 0;for(int i = 1; i < 21; i ++){if(arr[0][i]){countn += dp[all - 1][i];}}printf("%lld\n", countn);return 0;
}

F时间显示（15分，√）

题目描述
小蓝要和朋友合作开发一个时间显示的网站。

在服务器上，朋友已经获取了当前的时间，用一个整数表示，值为从 19701970 年 11 月 11 日 00:00:0000:00:00 到当前时刻经过的毫秒数。

现在，小蓝要在客户端显示出这个时间。小蓝不用显示出年月日，只需要显示出时分秒即可，毫秒也不用显示，直接舍去即可。

给定一个用整数表示的时间，请将这个时间对应的时分秒输出。
输入
输入一行包含一个整数，表示时间。
输出
输出时分秒表示的当前时间，格式形如 HH:MM:SS，其中 HH 表示时，值为 00​​​​ 到 2323​​​​，MM 表示分，值为 00​​​​ 到 5959​​​，SS 表示秒，值为 00​​ 到 5959​。时、分、秒 不足两位时补前导 00。
样例：
输入1

46800999

输出1

13:00:00

输入2

1618708103123

输出2

01:08:23

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;int main()
{long long times;cin >> times;times /= 1000;times %= (24 * 60 * 60);int hh = times / (60 * 60);times %= (60 * 60);int mm = times / 60;int ss = times % 60;printf("%02d:%02d:%02d\n", hh, mm, ss);return 0;
}

G砝码称重（20分，√）

题目描述
你有一架天平和 N 个砝码，这 N 个砝码重量依次是W1、W2……Wn。请你计算一共可以称出多少种不同的重量？ 注意砝码可以放在天平两边。
输入
输入的第一行包含一个整数 NN。
第二行包含 N 个整数：W1,W2,W3……，Wn
输出
输出一个整数代表答案。
样例
输入：

3
1 4 6

输出

10

解释：
能称出的 10 种重量是：1、2、3、4、5、6、7、9、10、11。

1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；​
3 = 4 − 1；
4 = 4；
5 = 6 − 1；
6 = 6；
7 = 1 + 6；
9 = 4 + 6 − 1；
10 = 4 + 6；
11 = 1 + 4 + 6。

前i个砝码能组成的j重量的方案数，其实大于1即可，分三种情况：
1、前i-1个就可以达到重量j；
2、第i个才能达到重量j，则前i-1个只能达到重量j-arr[i];
3、前i-1个可达到j+arr[j];

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;int arr[105] = {0};
int dp[105][100005] = {0};int main()
{int n;scanf("%d", &n);int sumn = 0;for(int i = 1; i <= n; i ++){scanf("%d", &arr[i]);sumn += arr[i];}dp[0][0] = 1;for(int i = 1; i <= n; i ++){for(int j = 0; j <= sumn; j ++){dp[i][j] = dp[i - 1][j] + dp[i - 1][ j + arr[i]] + dp[i - 1][abs(j - arr[i])];}}int countn = 0;for(int i = 1; i <= sumn; i ++){if(dp[n][i]){countn ++;}}printf("%d\n", countn);return 0;
}

H 异或数列（20分）

题目描述
Alice 和 Bob 正在玩一个异或数列的游戏。初始时，Alice 和 Bob 分别有一个整数 a 和 b，初始值均为 0。

有一个给定的长度为 nn​​的公共数列 X1,X2,……，Xn​​。Alice 和 Bob 轮流操作，Alice 先手，每步可以在以下两种选项中选一种：

选项 1：从数列中选一个Xi给 Alice 的数异或上，或者说令 a⊕Xi ​​。（其中⊕​​ 表示按位异或）;
选项 2：从数列中选一个Xi给 Bob 的数异或上，或者说令 b​​ 变为 b ⊕Xi​​。

每个数 Xi都只能用一次，当所有 Xi均被使用后（n​​ 轮后）游戏结束。游戏结束时，拥有的数比较大的一方获胜，如果双方数值相同，即为平手。 现在双方都足够聪明，都采用最优策略，请问谁能获胜？
输入描述
每个评测用例包含多组询问。询问之间彼此独立。
输入的第一行包含一个整数 T，表示询问数。
接下来 T​ 行每行包含一组询问。其中第 i​ 行的第一个整数 ni表示数列长度，随后 ni个整数 X1, X2, …… , Xni表示数列中的每个数。
输出描述
输出 T​​ 行，依次对应每组询问的答案。每行包含一个整数 1​​、0​ 或−1 分别表示 Alice 胜、平局或败。
样例
输入

4
1 1
1 0
2 2 1
7 992438 1006399 781139 985280 4729 872779 563580

输出

1
0
1
1

在这里插入图片描述

I 双向排序（25分）

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

J 分果果（25分）

题目描述
小蓝要在自己的生日宴会上将 n​​​​ 包糖果分给 m​​​​ 个小朋友。每包糖果都要分出去，每个小朋友至少要分一包，也可以分多包。

小蓝已经提前将糖果准备好了，为了在宴会当天能把糖果分得更平均一些，小蓝要先计算好分配方案。 小蓝将糖果从 1​​​ 到 nn​编号，第 i​ 包糖果重 wi。小朋友从 1 到 m​​ 编号。每个小朋友只能分到编号连续的糖果。小蓝想了很久没想出合适的分配方案使得每个小朋友分到的糖果差不多重。因此需要你帮他一起想办法。为了更好的分配糖果，他可以再买一些糖果，让某一些编号的糖果有两份。当某个编号的糖果有两份时，一个小朋友最多只能分其中的一份。

请找一个方案，使得小朋友分到的糖果的最大重量和最小重量的差最小，请输出这个差。

例如，小蓝现在有 5​​​​ 包糖果，重量分别为 6, 1, 2, 7, 9，如果小蓝要分给两个小朋友，则他可以将所有糖果再买一份，两个小朋友都分到 11​​​ 至 55​​ 包糖果，重量都是 25​，差为 0。

再如，小蓝现在有 55​​​​​​​ 包糖果，重量分别为 6, 1, 2, 7, 9，如果小蓝要分给三个小朋友，则他可以将第 3 包糖果再买一份，第一个小朋友分 1​​​​​​ 至 33​​​​ 包，第二个小朋友分 3​​​​ 至 4​​​ 包，第三个小朋友分第 5​​ 包，每个小朋友分到的重量都是 9​，差为 0。

再如，小蓝现在有 5​ 包糖果，重量分别为 6, 1, 2, 7, 9，如果小蓝要分给四个小朋友，则他可以将第 3 包和第 5 包糖果再买一份，仍然可以每个小朋友分到的重量都是 9，差为 0。

再如，小蓝现在有 5​​​​​​​​​​​​​ 包糖果，重量分别为 6, 1, 2, 7, 9​​​​​​​​​​​​，如果小蓝要分给五个小朋友，则他可以将第 4 包和第 5​​​​​​​​​​​ 包糖果再买一份，第一个小朋友分第 1​​​​​​​​​​ 至 2​​​​​​​​​ 包重量为 7​​​​​​​​，第二个小朋友分第 3​​​​​​​ 至 4​​​​​​ 包重量为 9​​​​​，第三个小朋友分第 4​​​​ 包重量为 7​​​，第四个和第五个小朋友都分第 5​​ 包重量为 9​。差为 2。
输入描述
输入第一行包含两个整数 n 和 m，分别表示糖果包数和小朋友数量。
第二行包含 n 个整数 w1, w2, · · · , wn ，表示每包糖果的重量。
输出描述
输出一个整数，表示在最优情况下小朋友分到的糖果的最大重量和最小重量的差。
样例
输入1：

5 2
6 1 2 7 9

输出1

0

输入2：

5 5
6 1 2 7 9

输出2

2

在这里插入图片描述

这篇关于第十二届蓝桥杯大赛软件类省赛C++研究生组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/178332。

相关文章

【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
06 C++Lambda表达式

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获：包含零个或者多个捕获符的逗号分隔列表 模板形参：用于泛型lambda提供个模板形参的名
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
软件设计师备考——计算机系统

软件设计师备考——计算机系统

学习内容源自「软件设计师」 上午题 #1 计算机系统_哔哩哔哩_bilibili 目录 1.1.1 计算机系统硬件基本组成 1.1.2 中央处理单元 1.CPU 的功能 1)运算器 2)控制器 RISC && CISC 流水线控制 存储器  Cache 中断 输入输出IO控制方式 程序查询方式 中断驱动方式 直接存储器方式（DMA)  ​编辑 总线 ​编辑
阅读更多...
【C++高阶】C++类型转换全攻略：深入理解并高效应用

【C++高阶】C++类型转换全攻略：深入理解并高效应用

📝个人主页🌹：Eternity._ ⏩收录专栏⏪：C++ “ 登神长阶 ” 🤡往期回顾🤡：C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝
阅读更多...
C++——stack、queue的实现及deque的介绍

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现
阅读更多...
【STM32】SPI通信-软件与硬件读写SPI

【STM32】SPI通信-软件与硬件读写SPI

SPI通信-软件与硬件读写SPI 软件SPI一、SPI通信协议1、SPI通信2、硬件电路3、移位示意图4、SPI时序基本单元(1)开始通信和结束通信(2)模式0---用的最多(3)模式1(4)模式2(5)模式3 5、SPI时序(1)写使能(2)指定地址写(3)指定地址读 二、W25Q64模块介绍１、W25Q64简介２、硬件电路３、W25Q64框图４、Flash操作注意事项软件SPI读写W2
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2