【题解】北化2021年“蓝桥杯”研究生组校内选拔训练赛三

2023-11-10 13:10
文章标签 蓝桥 校内 2021 题解 研究生 训练赛 选拔 北化

本文主要是介绍【题解】北化2021年“蓝桥杯”研究生组校内选拔训练赛三，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A 分数拆分

题目大意

       输入多组正整数k，找到所有的正整数x>=y，使得1/k=1/y+1/x，并按照y从大到小的顺序输出所有成立的分数式。

解题思路

       由于 k k k 的范围 1 ≤ k ≤ 100000 1≤k≤100000 1≤k≤100000，如果直接循环 [ 1 , 1 e 5 ] [1, 1e^5] [1,1e5] 遍历寻找符合条件的 x x x, y y y，会超过时限，所以要先对式子进行处理，过程如下：
1 k = 1 x + 1 y \frac 1k=\frac 1x+\frac 1y\\ k1​=x1​+y1​
1 k = x + y x y \frac 1k=\frac {x+y}{xy}\\ k1​=xyx+y​
k = x y x + y ( x + y ) k = x y k x = ( x − k ) y k=\frac {xy}{x+y}\\ (x+y)k=xy\\ kx=(x-k)y\\ k=x+yxy​(x+y)k=xykx=(x−k)y

       处理好式子后，再确定 x x x 的可选范围， x , y x, y x,y 为正整数，所以 x x x 最小时 ( x − k ) > 0 (x-k)>0 (x−k)>0 ；当 x = y x=y x=y 时达到 x x x 可取的最大值，所以 x x x 可选范围 [ k + 1 , 2 k ] [k+1,2k] [k+1,2k]，遍历此范围寻找符合上式的正整数 y y y 即可。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;int main()
{LL k;while(scanf("%lld", &k) != EOF) {LL y;for(LL x = k + 1LL; x <= 2LL * k; x = x + 1LL) {LL res1 = k * x, res2 = x - k;if(res1 % res2 != 0LL) continue;y = res1 / res2;printf("1/%lld=1/%lld+1/%lld\n", k, y, x);}}return 0;
}

B 最大乘积

题目大意

       输入包括多组数据，每组数据第一行为正整数n，第二行为n个元素组成的序列S，你需要对每组数据找出一个乘积最大的连续子序列，如果这个最大的乘积不是正数，则输出-1。

解题思路

       数据范围小，暴力枚举题，复杂度 O ( n 2 ) O(n^2) O(n2)，值得注意的是乘积结果可能会超过 int 范围，记得开 long long。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
LL a[50];int main()
{int n;while(scanf("%d", &n) != EOF) {for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);LL Max = a[1];for(int i = 1; i <= n; i++) {LL res = 1LL;for(int j = i; j <= n; j++) {res = res * a[j];Max = max(Max, res);}}if(Max <= 0LL) printf("-1\n");else printf("%lld\n", Max);}return 0;
}

C 求和

题目大意

       多组输入，每组给一个长度为n的序列，你需要求出其中连续m个数的和的最大值是多少。

解题思路

        前缀和问题。 n , m ∈ ( 0 , 1 e 5 ] n, m∈(0,1e^5] n,m∈(0,1e5]，如果直接进行暴力枚举的话会时间超限。维护一个前缀和数组，那么从第 i i i 个数开始的连续 m m m 个数的和用 p r e [ i + m − 1 ] − p r e [ i − 1 ] pre[i + m - 1] - pre[i - 1] pre[i+m−1]−pre[i−1] 即可解决，时间复杂度控制在了 O ( n ) O(n) O(n) 范围内。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int MaxN = 1e5;
LL a[MaxN + 5], pre[MaxN + 5];int main()
{int T; scanf("%d", &T);while(T--){int n, m; scanf("%d %d", &n, &m);for(int i = 0; i <= MaxN; i++) pre[i] = 0;for(int i = 1; i <= n; i++) {scanf("%lld", &a[i]);if(i == 1) pre[i] = a[i];else pre[i] = pre[i - 1] + a[i];}LL Max = 0LL;for(int i = 1; i <= (n - m + 1); i++) {LL res = pre[i + m - 1] - pre[i - 1];Max = max(Max, res);}printf("%lld\n", Max);}return 0;
}

D 神奇炸弹

题目大意

       在一个二维空间中有 n 个点，已知每个点的 ( x , y ) (x,y) (x,y) 坐标和权值。现给定一个边长为 R 的正方形，其边与 x y 轴平行，任意放置正方形，求在正方形内能包含的最大权值是多少。

解题思路

       二维前缀和问题。前缀和数组 p r e [ i ] [ j ] pre[i][j] pre[i][j] 表示的是从 ( 0 , 0 ) (0, 0) (0,0) 到 ( i , j ) (i, j) (i,j) 为顶点的矩形中的包含的权值和，那么如果求从 ( x x , y y ) (xx, yy) (xx,yy) 到 ( i , j ) (i, j) (i,j) 为顶点的矩形中包含的权值和为：
p r e [ i ] [ j ] − p r e [ x x ] [ j ] − p r e [ i ] [ y y ] + p r e [ x x ] [ y y ] pre[i][j]-pre[xx][j]-pre[i][yy]+pre[xx][yy] pre[i][j]−pre[xx][j]−pre[i][yy]+pre[xx][yy] 如图所示，紫色区域的权值等于 黄色 - 红色 - 绿色 + 蓝色。
在这里插入图片描述

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int MaxN = 5e3;
int n, r;
int a[MaxN + 5][MaxN + 5], pre[MaxN + 5][MaxN + 5];int main()
{scanf("%d %d", &n, &r);int l = 5000;for(int i = 1; i <= n; i++) {int x, y, v; scanf("%d %d %d", &x, &y,&v);a[x][y] = v;pre[x + 1][y + 1] = v;}for(int i = 1; i <= l; i++) {for(int j = 0; j <= l; j++) {pre[i][j] = pre[i - 1][j] + pre[i][j];}}for(int i = 0; i <= l; i++) {for(int j = 1; j <= l; j++) {pre[i][j] = pre[i][j - 1] + pre[i][j];}}
/*for(int i = 0; i <= 10; i++) {for(int j = 0; j<= 10; j++){printf("%d ", pre[i][j]);}printf("\n");}
*/if(r >= l) printf("%d\n", pre[l][l]);else {int Max = 0;for(int i = r; i <= l; i++) {for(int j = r; j <= l; j++) {int xx = max(0, i - r), yy = max(0, j - r);int res = pre[i][j] - pre[xx][j] - pre[i][yy] + pre[xx][yy];Max = max(Max, res);}}printf("%d\n", Max);}return 0;
}

E 全排列问题

题目大意

       计算从1到N的N个整数所能构成的所有排列，并按照字典顺序依次输出。

解题思路

       灵活运用 n e x t _ p e r m u t a t i o n ( ) next\_permutation() next_permutation() 函数即可。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
int p[20];int main()
{int n; while(1) {scanf("%d", &n);if(n == 0) break;for(int i = 0; i < n; i++) p[i] = i + 1;do {for(int i = 0; i < n; i++) {printf("%d", p[i]);if(i == n - 1) printf("\n");else printf(" ");}}while(next_permutation(p, p + n));}return 0;
}

F 24点游戏

题目大意

       给出4个正整数操作数，你的任务是使用运算符（+，-，*，/）和括号对操作数进行计算，分析是否能得到24，每个操作数只能使用1次，运算符和括号可以多次使用，注意所有的中间结果都必须是整数。

解题思路

       模拟题。a_b_c_d 四个数进行运算，不考虑运算符到底是什么，首先确定括号可能出现的位置，也就是运算顺序：
       ① 先进行ab运算，再与c进行运算，最后与d进行运算：[(a_b)_c]_d
       ② 先进行ab运算，再进行cd运算，最后进行ab与cd运算：(a_b)_(c_d)
       ③ 先进行bc运算，再与a进行运算，最后与d进行运算：[a_(b_c)]_d
       ④ 先进行bc运算，再与d进行运算，最后与a进行运算：a_[(b_c)_d]
       ⑤ 先进行cd运算，再与b进行运算，最后与a进行运算：a_[b_(c_d)]
       运算顺序确定后，通过暴力枚举每个下划线位置可能出现的运算符以及abcd四个数的顺序，确定最终是否可以式子得到24。注意： 除法时要考虑到除数不能为 0 。
此外，递归方法同样可以解决这一问题。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
double a, b, c, d;
char op[] = {'+','-','*','/'};
double p[10];double jisuan(double x, double y, char to) {if(to == '+') return x + y;if(to == '-') return x - y;if(to == '*') return x * y;if(to == '/') {if(y == 0) return INF;return x / y;}
}int main()
{while(scanf("%lf %lf %lf %lf", &p[0], &p[1], &p[2], &p[3]) != EOF) {a = p[0], b = p[1], c = p[2], d = p[3];if(a == 0 && b == 0 && c == 0 && d == 0) break;int flag = 0;do{ a = p[0], b = p[1], c = p[2], d = p[3];// [(a_b)_c]_dfor(int i = 0; i < 4; i++) {for(int j = 0; j < 4; j++) {for(int k = 0; k < 4; k++) {double ans;ans = jisuan(a, b, op[i]);if(ans == INF) continue;ans = jisuan(ans, c, op[j]);if(ans == INF) continue;ans = jisuan(ans, d, op[k]);if(ans == INF) continue;if(ans == 24) {flag = 1;break;}}if(flag == 1) break;}if(flag == 1) break;}if(flag == 1) {printf("Yes\n");break;}// [a_(b_c)]_dfor(int i = 0; i < 4; i++) {for(int j = 0; j < 4; j++) {for(int k = 0; k < 4; k++) {double ans;ans = jisuan(b, c, op[j]);if(ans == INF) continue;ans = jisuan(a, ans, op[i]);if(ans == INF) continue;ans = jisuan(ans, d, op[k]);if(ans == INF) continue;if(ans == 24) {flag = 1;break;}}if(flag == 1) break;}if(flag == 1) break;}if(flag == 1) {printf("Yes\n");break;}// a_[(b_c)_d]for(int i = 0; i < 4; i++) {for(int j = 0; j < 4; j++) {for(int k = 0; k < 4; k++) {double ans;ans = jisuan(b, c, op[j]);if(ans == INF) continue;ans = jisuan(ans, d, op[k]);if(ans == INF) continue;ans = jisuan(a, ans, op[i]);if(ans == INF) continue;if(ans == 24) {flag = 1;break;}}if(flag == 1) break;}if(flag == 1) break;}if(flag == 1) {printf("Yes\n");break;}// a_[b_(c_d)]for(int i = 0; i < 4; i++) {for(int j = 0; j < 4; j++) {for(int k = 0; k < 4; k++) {double ans;ans = jisuan(c, d, op[k]);if(ans == INF) continue;ans = jisuan(b, ans, op[j]);if(ans == INF) continue;ans = jisuan(a, ans, op[i]);if(ans == INF) continue;if(ans == 24) {flag = 1;break;}}if(flag == 1) break;}if(flag == 1) break;}if(flag == 1) {printf("Yes\n");break;}// (a_b)_(c_d)for(int i = 0; i < 4; i++) {for(int j = 0; j < 4; j++) {for(int k = 0; k < 4; k++) {double ans1 = jisuan(a, b, op[i]);if(ans1 == INF) continue;double ans2 = jisuan(c, d, op[k]);if(ans2 == INF) continue;double ans = jisuan(ans1, ans2, op[j]);if(ans == INF) continue;if(ans == 24) {flag = 1;break;}}if(flag == 1) break;}if(flag == 1) break;}if(flag == 1) {printf("Yes\n");break;}}while(next_permutation(p, p + 4)); if(flag == 0) printf("No\n");}return 0;
}

G 数数

题目大意

       给出一个数量为n的数列，你需要对每一个查询，回答出查询数在数列中的数量。

解题思路

       查询次数不超过 4 e 5 4e^5 4e5，数组长度不超过 1 e 5 1e^5 1e5 ，如果每次查询都遍历一遍数组会时间超限，所以在读入数组是预处理一个 map 存放当前值出现过几次，在每次查询的时候直接访问 map[x] 中的值即为 x 出现的次数。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int MaxN = 1e5;
int a[MaxN + 5];
map<int, int>vis;int main()
{int n; scanf("%d", &n);for(int i = 1; i <= n; i++) {scanf("%d", &a[i]);vis[a[i]]++;}int q; scanf("%d", &q);while(q--) {int x; scanf("%d", &x);printf("%d\n", vis[x]);}return 0;
}

H 销售排行榜

题目大意

       输入每行数据包括4个信息，分别是商品名称、销售数量、单价、成交日期，输出包括多行数据，将所有在输入中出现的商品按销售数量降序排列，每行数据包括3个信息，分别是商品名称、销售数量、销售额,如果两种商品销售数量一样，则按商品的字母顺序升序排列。

解题思路

       结构体排序经典问题。结构体中定义一个商品名，一个销售数量，一个总销售额和一个日期。创建一个以商品名为下标的 map ，当前商品在 map 中值为 0 时说明当前商品之前还没存在结构体中，此时添加当前商品信息到结构体中，并将当前商品在 map 中的值修改为在结构体中的下标；如果当前商品在 map 中的值非 0，则表示商品已经存在结构体中，调用 map 中的值并将该商品的相关信息更新。最后排序输出即可。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int MaxN = 1e5;
map<string, int>vis;
struct node {string s;LL sum;LL cnt;string date;
}a[MaxN + 5];bool cmp(node x, node y) {if(x.cnt == y.cnt) return x.s < y.s;return x.cnt > y.cnt;
}int main()
{string ss, dd;LL cc, pp;int pos = 1;while(cin >> ss) {cin >> cc >> pp >> dd;if(vis[ss] == 0) {LL res = cc * pp;a[pos].s = ss, a[pos].cnt = cc, a[pos].sum = res, a[pos].date = dd;vis[ss] = pos;pos++;}else {int xx = vis[ss];LL res = cc * pp;a[xx].cnt += cc, a[xx].sum += res;}}sort(a + 1, a + pos, cmp);for(int i = 1; i < pos; i++) {cout << a[i].s << " " << a[i].cnt << " " << a[i].sum << " " << endl;}return 0;
}

I 有向图是否存在环

题目大意

       写程序判断有向图是否存在环。有向图的输入n个节点，m条边用m个二元组表示(u,v)，表示从u到v有一条有向边，起点是u，终点是v。如果该有向图存在环，输出YES，否则输出NO。

解题思路

       经典图 dfs 问题。首先维护一个邻接矩阵 w [ i ] [ j ] = 1 w[i][j]=1 w[i][j]=1 表示从 i i i 到 j j j 有一条有向边。接下来对每个点进行一次 dfs ，如果在 dfs 过程中某个点重复出现，则表示出现了环，否则继续对下一个节点进行 dfs。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int MaxN = 100;
int w[MaxN + 5][MaxN + 5];
int s = 1, cnt = 0;
int n, m;
bool flag;
bool vis[MaxN + 5];void dfs(int x) {cnt++;
//  printf("%d ", x);if(cnt != 1 && vis[x]) {flag = true;return;}vis[x] = 1;for(int i = 1; i <= n; i++) {if(w[x][i]) dfs(i);}return;
}int main()
{while(scanf("%d %d", &n, &m) != EOF) {if(n == 0 && m == 0) break;for(int i = 0; i <= MaxN; i++) {vis[i] = 0;for(int j = 0; j <= MaxN; j++) w[i][j] = 0;}for(int i = 1; i <= m; i++) {int u, v; scanf("%d %d", &u, &v);w[u][v] = 1;}flag = false;for(int i = 1; i <= n; i++) {s = i, cnt = 0;dfs(i);
//          cout << "-----------------" << endl;if(flag == true) break;for(int i = 1; i <= n; i++) vis[i] = 0;}if(flag == true) printf("YES\n");else printf("NO\n");}return 0;
}

J Maximum value

题目大意

       输入三个数a, b, c，输出最大的数是多少。

解题思路

       简单题。直接判断即可。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;int main()
{int a, b, c; scanf("%d %d %d", &a, &b, &c);int Max = a;Max = max(Max, b);Max = max(Max, c);printf("%d\n", Max);return 0;
}

END

以上仅代表个人想法，如有错误，请及时沟通指正，谢谢！

这篇关于【题解】北化2021年“蓝桥杯”研究生组校内选拔训练赛三的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

C++ | Leetcode C++题解之第393题UTF-8编码验证

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目： 题解： class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &
阅读更多...
C语言 | Leetcode C语言题解之第393题UTF-8编码验证

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目： 题解： static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return
阅读更多...
C - Word Ladder题解

C - Word Ladder题解

C - Word Ladder 题解 解题思路： 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数（也就是需要变换多少次） 开始替换时： tips: 字符串下标以0开始 我们定义两个变量a和b，用于记录当前遍历到的字符 首先是判断：如果这时a已经==b了，那么就跳过，不用管； 如果a大于b的话：那么我们就让s中的第i项替换成b，接着就直接输出S就行了。 这样
阅读更多...
【秋招笔试】9.07米哈游秋招改编题-三语言题解

【秋招笔试】9.07米哈游秋招改编题-三语言题解

🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收集 100+ 套笔试题，笔试真题 会在第一时间跟新 🍄 题面描述等均已改编，如果和你笔试题看到的题面描述
阅读更多...
LeetCode 第414场周赛个人题解

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析
阅读更多...
C语言蓝桥杯

C语言蓝桥杯

一、语言基础 竞赛常用库函数 最值查询 min_element和max_element在vector(迭代器的使用) nth_element函数的使用 例题lanqiao OJ 497成绩分析 第一种用min_element和max_element函数的写法 第二种用min和max的写法 二分查找 二分查找只能对数组操作 binary_s
阅读更多...
GPU 计算 CMPS224 2021 学习笔记 02

GPU 计算 CMPS224 2021 学习笔记 02

并行类型 （1）任务并行 （2）数据并行 CPU & GPU CPU和GPU拥有相互独立的内存空间，需要在两者之间相互传输数据。 （1）分配GPU内存 （2）将CPU上的数据复制到GPU上 （3）在GPU上对数据进行计算操作 （4）将计算结果从GPU复制到CPU上 （5）释放GPU内存 CUDA内存管理API （1）分配内存 cudaErro
阅读更多...
2021-8-14 react笔记-2 创建组件 基本用法

2021-8-14 react笔记-2 创建组件 基本用法

1、目录解析 public中的index.html为入口文件 src目录中文件很乱，先整理文件夹。 新建components 放组件 新建assets放资源   ->/images      ->/css 把乱的文件放进去  修改App.js 根组件和index.js入口文件中的引入路径 2、新建组件 在components文件夹中新建[Name].js文件 //组件名首字母大写
阅读更多...
2021-08-14 react笔记-1 安装、环境搭建、创建项目

2021-08-14 react笔记-1 安装、环境搭建、创建项目

1、环境 1、安装nodejs 2.安装react脚手架工具 //  cnpm install -g create-react-app 全局安装 2、创建项目 create-react-app [项目名称] 3、运行项目 npm strat  //cd到项目文件夹    进入这个页面  代表运行成功  4、打包 npm run build
阅读更多...
牛客小白月赛100部分题解

牛客小白月赛100部分题解

比赛地址：牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2