第十五届蓝桥杯省赛C/C++大学B组真题及赛后总结

2024-04-15 10:36

本文主要是介绍第十五届蓝桥杯省赛C/C++大学B组真题及赛后总结,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

个人总结

C/C++ 组真题

握手问题

小球反弹

好数

R 格式

宝石组合

数字接龙

爬山

拔河

​编辑

再总结及后续规划


个人总结

第一次参加蓝桥杯,大二,以前都在在学技术,没有系统的学过算法。所以,还是花了挺多时间去备战的,因为暑假想找实习,就想拿个奖写简历上。备战了大概一个多月,学了一些基础的算法(dfs bfs 动态规划为主),刷了快200道题吧,但还是因为缺少经验,比赛时有点茫然了,然后大概率是寄了。

C/C++ 组真题

握手问题

这道第一题相对于去年还算是比较简单,排列 + 特殊情况处理即可

(50 * 49) / 2 - (6*7) / 2 = 1204,答案应该是正确的

小球反弹

这个应该是错了哈哈,答案是 1100325199.77,但和这个值挺像的,可惜只看答案。

前两道题都是数学问题,唉,后悔没有静下心来看第二题了。

好数

这道题直接暴力模拟即可,数据量没有很大。

#include <iostream>
using namespace std;
int N;
int main()
{cin >> N;int Count = 0; // 记录总个数for (int i = 1; i <= N; i++){// 判断某一个数是否是 好数int n = i; // 用 n 记录 iint flag = 1; // 1 此时计算的是 i 的奇数位, 0 表示此时计算的是 i 的偶数位int ret = 1; // 记录当前数否为 好数while (n > 0){int end = n % 10;if (flag == 1){if (end % 2 == 0){ret = 0;break;}flag = 0;}else //  flag = 0{if (end % 2 != 0){ret = 0;break;}flag = 1;}n /= 10;}if (ret == 1) Count++;}cout << Count << endl;return 0;
}

R 格式

 

这道题看起来挺简单的,但如果要拿满分的话,需要使用字符串模拟,我直接使用 long long 了,应该能拿 50% 的分。

long long  50%代码

#include <iostream>
using namespace std;
double d;
int n;
long long func(int n)
{long long ret = 1;while (n--){ret *= 2;}return ret;
}
int main()
{cin >> n >> d;cout << (long long)(func(n) * d + 0.5) << endl;return 0;
}

宝石组合

 这道题没有学过网上的那些公式算法,第一个想到的是暴击解法,时间复杂度O(N^3),但思考了一会,发现是可以用哈希表来优化的,时间复杂度可以降到 O(N^2)。不过貌似依然过不了很多数据,第二个比较麻烦的点就是如果 S 相同的情况下要按字典序排顺序。

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
long long N;
long long nums[100010];
long long func(long long a, long long b, long long c = 1)
{long long Max = max(a, max(b, c));long long i = 0;for (i = Max; i >= 0; i += Max){if (i % a == 0 && i % b == 0 && i % c == 0) break;}return i;
}
long long get_S(long long a, long long b, long long c)
{long long tmp = a * b * c * func(a, b ,c);long long ret = tmp / (func(a, b) * func(a, c) * func(b, c));return ret;
}
int main()
{cin >> N;for (long long i = 1; i <= N; i++) cin >> nums[i];unordered_map<long long, pair<long long, long long>> hash;for (long long i = 2; i <= N; i++){for (long long j = i - 1; j >= 1; j--)hash[nums[i] * nums[j]] = { j, i };}long long ret[3] = {100010, 100010, 100010};long long S = 0;for (long long i = 1; i <= N; i++){for (auto& e : hash){if (e.second.first != i && e.second.second != i){long long tmp = get_S(nums[i], nums[e.second.first], nums[e.second.second]);if (tmp > S){S = tmp;ret[0] = nums[i];ret[1] = nums[e.second.first];ret[2] = nums[e.second.second];}else if (tmp == S){if (ret[0] > nums[i]){ret[0] = nums[i];ret[1] = nums[e.second.first];ret[2] = nums[e.second.second];}else if (nums[i] == ret[0] && ret[1] > nums[e.second.first]){ret[0] = nums[i];ret[1] = nums[e.second.first];ret[2] = nums[e.second.second];}else if (nums[i] == ret[0] && ret[1] == nums[e.second.first] && ret[2] > nums[e.second.second]){ret[0] = nums[i];ret[1] = nums[e.second.first];ret[2] = nums[e.second.second];}}}}}cout << ret[0] << " " << ret[1] << " " << ret[2] << endl;return 0;
}

数字接龙

这道题,打眼一看是 dfs ,觉得自己会,就开始做,没想到做到最后,不会判断路径是否交叉,有点懵逼了,就直接将得到的所有可以走完的路径按字典序排序后取了第一个,最后估计还没有直接输出 - 1的人得的分多。还是比赛经验不够,应该先好好看完题再开始写代码的。

这里就不放我的错代码了,唉,看到正确答案就在自己负责调试的 vector 里,却没有办法去除错错误的答案...

知乎正确答案:

#include <iostream>
#include <vector>
using namespace std;
const int N = 11;
int a[N][N];
int dt[8][2] = { {-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1} };
int n, k;
vector<int> path;
vector<int> res;
bool ban[N][N][N][N];
bool vis[N][N];
void dfs(int sx, int sy)
{if (!res.empty()) return;if (sx == n - 1 && sy == n - 1){if (path.size() == n * n - 1) res = path;return;}if (path.size() == n * n - 1) return;for (int i = 0; i < 8; i++){if (!res.empty()) return;int dx = dt[i][0], dy = dt[i][1];int x = sx + dx, y = sy + dy;if (x >= 0 && x < n && y >= 0 && y < n && !vis[x][y] && a[x][y] == (a[sx][sy] + 1) % k){if (dx != 0 && dy != 0 && ban[sx + dx][sy][sx][sy + dy]) continue;ban[sx][sy][x][y] = ban[x][y][sx][sy] = true;vis[x][y] = true;path.push_back(i);dfs(x, y);path.pop_back();vis[x][y] = false;ban[sx][sy][x][y] = ban[x][y][sx][sy] = false;}}
}
int main()
{scanf("%d%d", &n, &k);for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &a[i][j]);vis[0][0] = true;dfs(0, 0);if (!res.empty()){for (auto x : res) printf("%d", x);}else{puts("-1");}return 0;
}

爬山

 由于上一题浪费了太多时间,这道题也没有认真看,想了一下动态规划,感觉有点复杂,凭感觉写了一下...出来后看了答案才发现是 优先级队列 + 贪心

这是知乎上的贪心答案,但这个做法对于有的测试用例也是过不了的,我感觉还是应该用动态规划哈哈。

int main()
{priority_queue<int> heap;scanf("%d%d%d",&n,&P,&Q);for(int i=1;i<=n;i++) scanf("%d",&a[i]),heap.push(a[i]);while(P||Q){auto x=heap.top();heap.pop();if(P&&Q){int yl=_sqrt(x);int y2=x/2;if(y2<=yl){Q--;heap.push(y2);}else{P--;heap.push(yl);}}else if(P){int yl=_sqrt(x);P--;heap.push(yl);}else{int y2=x/2;Q--;heap.push(y2);}}ll res=0;while(!heap.empty()){int x=heap.top();heap.pop();res+=x;}printf("%lld\n",res);return 0;
}

拔河

这道题看都没看,唉,应该先看一下的......,起码得个暴力分

标准答案:指针 + 二分

#include <iostream>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;
const int N = 1003;
int a[N];
int n;
ll s[N];
int main()
{scanf("%d", &n);for (int i = 1; i <= n; i++) scanf("%d", &a[i]), s[i] = s[i - 1] + a[i];multiset<ll> S;for (int l = 1; l <= n; l++){for (int r = l + 1; r <= n; r++){S.insert(s[r] - s[l]);}}ll res = 0x3f3f3f3f;for (int r = 1; r < n; r++){for (int l = 0; l < r; l++){ll val = s[r] - s[l];auto it = S.lower_bound(val);if (it != S.end()){ll ans = abs(*it - val);res = min(res, ans);}if (it != S.begin()){it--;ll ans = abs(*it - val);res = min(res, ans);}}for (int r2 = r + 1; r2 <= n; r2++){S.erase(S.find(s[r2] - s[r]));}}printf("%lld\n", res);return 0;
}

再总结及后续规划

总结:自己算法还是太菜了(毕竟练习时长只有一个月),本次大概率可能是省二 ~ 省三了,省一的概率不大,不知道大三还有没有机会再打蓝桥杯,那时候应该要实习 / 考研吧。

接下来的安排,下周六还有一场天梯赛,打完后就要继续学技术了,冲一下暑假的日常实习,到时候就开始佛系做力扣每日一题了,不再花时间集中学算法了,算法竞赛的帮助,对于找开发的工作,有帮助,但最重要的还是技术得学到手,做项目。

这篇关于第十五届蓝桥杯省赛C/C++大学B组真题及赛后总结的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/905578

相关文章

深入理解C++ 空类大小

《深入理解C++空类大小》本文主要介绍了C++空类大小,规定空类大小为1字节,主要是为了保证对象的唯一性和可区分性,满足数组元素地址连续的要求,下面就来了解一下... 目录1. 保证对象的唯一性和可区分性2. 满足数组元素地址连续的要求3. 与C++的对象模型和内存管理机制相适配查看类对象内存在C++中,规

Android数据库Room的实际使用过程总结

《Android数据库Room的实际使用过程总结》这篇文章主要给大家介绍了关于Android数据库Room的实际使用过程,详细介绍了如何创建实体类、数据访问对象(DAO)和数据库抽象类,需要的朋友可以... 目录前言一、Room的基本使用1.项目配置2.创建实体类(Entity)3.创建数据访问对象(DAO

在 VSCode 中配置 C++ 开发环境的详细教程

《在VSCode中配置C++开发环境的详细教程》本文详细介绍了如何在VisualStudioCode(VSCode)中配置C++开发环境,包括安装必要的工具、配置编译器、设置调试环境等步骤,通... 目录如何在 VSCode 中配置 C++ 开发环境:详细教程1. 什么是 VSCode?2. 安装 VSCo

Java向kettle8.0传递参数的方式总结

《Java向kettle8.0传递参数的方式总结》介绍了如何在Kettle中传递参数到转换和作业中,包括设置全局properties、使用TransMeta和JobMeta的parameterValu... 目录1.传递参数到转换中2.传递参数到作业中总结1.传递参数到转换中1.1. 通过设置Trans的

C# Task Cancellation使用总结

《C#TaskCancellation使用总结》本文主要介绍了在使用CancellationTokenSource取消任务时的行为,以及如何使用Task的ContinueWith方法来处理任务的延... 目录C# Task Cancellation总结1、调用cancellationTokenSource.

C++11的函数包装器std::function使用示例

《C++11的函数包装器std::function使用示例》C++11引入的std::function是最常用的函数包装器,它可以存储任何可调用对象并提供统一的调用接口,以下是关于函数包装器的详细讲解... 目录一、std::function 的基本用法1. 基本语法二、如何使用 std::function

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

【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++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数