第十五届蓝桥杯省赛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 记录 i
		int 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;
}

再总结及后续规划

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

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/544654.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【8086汇编】汇编语言基础入门

文章目录 一、汇编简介1. 汇编语言的组成2. CPU、寄存器、内存3. CPU对存储器的读写4. 拓展5. 检测6. 解析 二、寄存器1. mov、add命令2. 物理地址3. CS:IP 装段地址和偏移地址3.1 如何改变CS:IP的值 4. 数据段DS:[address]4.1 前置知识&#xff1a;字与字节4.2 DS:[address] 5…

串口RS485

1.原理 全双工&#xff1a;在同一时刻可以同时进行数据的接收和数据的发送&#xff0c;两者互不影响 半双工&#xff1a;在同一时刻只能进行数据的接收或者数据的发送&#xff0c;两者不能同时进行 差分信号幅值相同&#xff0c;相位相反&#xff0c;有更强的抗干扰能力。 干…

【C语言】N子棋小游戏♔

目录 前言 一、何为N子棋游戏&#xff1f; 二、游戏思路 三、游戏实现 3.1 模块化 3.2 游戏棋盘 3.3 下棋操作 3.3.1 玩家下棋 3.3.2 电脑下棋 3.4 判断输赢 总结 前言 三子棋小游戏相信大家都玩过吧&#xff0c;类似的5子琪等等&#xff0c;这篇文章将带着大家从0到…

【leetcode面试经典150题】28.盛最多水的容器(C++)

【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主&#xff0c;题解使用C语言。&#xff08;若有使用其他语言的同学也可了解题解思路&#xff0c;本质上语法内容一致&…

分享一些有趣的 Linux 命令

1、sl 会显示一辆火车穿过你的终端屏幕 2、cmatrix 在终端中显示类似于《黑客帝国》电影中的绿色数字雨效果 3、fortune 显示一个随机的名人名言或者笑话 4、cowsay 让一头牛说出你输入的话 5、toilet 在终端中将输入的文本以艺术字体的形式呈现 6、figlet 类似于 toile…

回溯算法初识

文章目录 回溯算法初识什么是回溯算法回溯算法的步骤回溯算模版例题 回溯算法初识 什么是回溯算法 ​ 回溯算法是一种通过不断尝试可能的解决方案来解决问题的算法。它通常用于解决组合优化问题&#xff0c;如排列组合问题、子集和问题等。该算法通过尝试所有可能的候选解&am…

【热门话题】常见分类算法解析

&#x1f308;个人主页: 鑫宝Code &#x1f525;热门专栏: 闲话杂谈&#xff5c; 炫酷HTML | JavaScript基础 ​&#x1f4ab;个人格言: "如无必要&#xff0c;勿增实体" 文章目录 常见分类算法解析1. 逻辑回归&#xff08;Logistic Regression&#xff09;2. 朴…

【设计模式】聊聊观察者设计模式原理及应用

原理 观察者模式属于行为模式&#xff0c;行为模式主要解决类和对象之间交互问题。 含义&#xff1a;在对象之间定义一个一对多的依赖&#xff0c;当一个对象状态改变时&#xff0c;所有依赖的对象会自动通知。 被依赖的对象被观察者(Observable) &#xff0c;依赖的对象观察…

移动Web学习06-移动端适配Less预处理器项目案例

项目目标&#xff1a;实现在不同宽度设备中等比缩放的网页效果 Less代码 import ./base; import ./normalize;// 变量: 存储37.5 rootSize: 37.5rem; *{margin: 0;padding: 0; } body {background-color: #F0F0F0; }// 主体内容 .main {// padding-bottom: (50 / 37.5rem);pa…

缺失msvcr110.dll要怎么处理?快捷的修复msvcr110.dll方法

当你在使用电脑进行工作或娱乐时&#xff0c;可能会突然遇到一个错误提示&#xff1a;“程序无法启动&#xff0c;因为电脑中缺失msvcr110.dll”。这样的情况不仅会打断你的活动&#xff0c;还可能带来一定程度的不便。面对这个在Windows操作系统中相对常见的问题&#xff0c;其…

IDEA2023 开发环境配置

目录 1. 关闭IDEA自动更新1.2 IDEA 新版样式切换 2. Maven配置2.1本地仓库优先加载2.2 maven.config配置文件中 3. 全局配置JDK4. 配置文件编码:UTF-85. 开启自动编译&#xff08;全局配置&#xff09;6. 开启自动导包7. 开启鼠标悬浮&#xff08;提示文档信息&#xff09;8. 设…

7 个适用于 Windows 的最佳电脑分区数据恢复软件

磁盘分区对于正确存储数据以便从硬盘驱动器快速轻松地访问非常有帮助。但是&#xff0c;如果分区损坏&#xff0c;存储在其中的所有数据都会突然变得无法访问。磁盘分区损坏的原因可能有很多&#xff0c;其中最突出的是病毒攻击、突然断电、物理损坏或由于创建坏扇区。 但是&a…

gzip,bzip2,xz,tar-读书笔记(九)

gzip 将文件进行压缩 在Linux系统中&#xff0c;gzip 是一个压缩和解压文件的命令工具。它使用LZ77压缩算法及霍夫曼编码&#xff08;Huffman Coding&#xff09;来压缩文件&#xff0c;通常用来减少文件的大小&#xff0c;以节约磁盘空间或减少网络传输的时间。 gzip 命令的…

Linux gcc 6

本章开始学习工具 什么是工具&#xff1f; 本质也是指令 yum 命令 小火车 sudo yum install sl&#xff08;安装sl&#xff09; sudo yum install -y sl //直接yes就不提示了 yum list //将yum源上的软件都穷举出来 yum search sl //结果不友好&#xff0c;不推荐 yum lis…

Python-GEE遥感云大数据分析、管理与可视化及多领域案例实践应用

随着航空、航天、近地空间遥感平台的持续发展&#xff0c;遥感技术近年来取得显著进步。遥感数据的空间、时间、光谱分辨率及数据量均大幅提升&#xff0c;呈现出大数据特征。这为相关研究带来了新机遇&#xff0c;但同时也带来巨大挑战。传统的工作站和服务器已无法满足大区域…

【数据结构】泛型(分享重点)

什么是泛型&#xff1f; 泛型就是适用于许多许多类型&#xff0c;对类型参数化。 怎么创建一个泛型呢 class 泛型类名称<类型形参列表> { // 这里可以使用类型参数 } class ClassName<T1, T2, ..., Tn> { } class 泛型类名称<类型形参列表> extends 继承类…

Hadoop 3.1.3

第1章 Hadoop概述 1.1 Hadoop是什么 1.2 Hadoop发展历史&#xff08;了解&#xff09; 1.3 Hadoop三大发行版本&#xff08;了解&#xff09; Hadoop三大发行版本&#xff1a;Apache、Cloudera、Hortonworks。 Apache版本最原始&#xff08;最基础&#xff09;的版本&#x…

AI大模型探索之路-提升篇2:一文掌握AI大模型的核心-注意力机制

目录 前言 一、注意力机制简介 二、注意力机制的工作原理 三、注意力机制的变体 1、自注意力&#xff08;Self-Attention&#xff09; 2、双向注意力&#xff08;Bidirectional Attention&#xff09; 3、多头注意力&#xff08;Multi-Head Attention&#xff09; ​4、…

卫星影像联合无人机实现农业保险全生命周期监管监测

随着科技的进步&#xff0c;农业保险监管系统的发展日新月异。特别是近年来&#xff0c;随着卫星技术与无人机技术的结合&#xff0c;为农业保险监管系统带来了前所未有的革新。本文将深入探讨如何利用卫星与无人机方案构建高效的农业保险监管系统&#xff0c;并结合实例进行说…

网络篇06 | 应用层 自定义协议

网络篇06 | 应用层 自定义协议 01 固定协议设计&#xff08;简化版&#xff09;1&#xff09;总体设计2&#xff09;值设计 02 可变协议设计&#xff08;进阶版&#xff09;1&#xff09;固定头&#xff08;Fixed Header&#xff09;2&#xff09;可变头&#xff08;Variable H…