牛客春招刷题训练营 - 2025.5.27 题解

活动地址:牛客春招刷题训练营 - 编程打卡活动

Easy 小红的整数配对

简要题意

给一个正整数数组,初始有 分。每次可以选数组中两个相差不超过 的数,将它们从数组中删去并获得等于它们乘积的分数,求最大分数。

Solution

排序后总取最大的两个尝试配对,不行就把最大那个丢掉。

Code

void R()
{
	int n,k;
	i64 ans=0;
	cin>>n>>k;
	vector<i64> a(n);
	for (i64 &x:a) cin>>x;
	sort(a.begin(),a.end());
	while (a.size()>1)
	{
		if (a.back()-a[a.size()-2]<=k)
		{
			ans+=a.back()*a[a.size()-2];
			a.pop_back();
		}
		a.pop_back();
	}
	cout<<ans;
	return;
}

Medium 小红的取模构造

简要题意

给定非负整数 ,构造正整数 ,使得:

Solution

分类讨论。

时,若 则有解 1 1,否则无解。

时,若 有解 ,否则有解 ,反之同理。

Code

void R()
{
	int a,b;
	cin>>a>>b;
	if (a==b)
	{
		if (a==0) cout<<"1 1\n";
		else cout<<"-1 -1\n";
	}
	else if (a<b)
	{
		if (a==0) cout<<2*b<<' '<<b<<'\n';
		else cout<<a+b<<' '<<b<<'\n';
	}
	else
	{
		if (b==0) cout<<a<<' '<<2*a<<'\n';
		else cout<<a<<' '<<a+b<<'\n';
	}
	return;
}

Hard 【模板】单源最短路Ⅲ ‖ 非负权图

简要题意

给定一个有 个点 条有向边的非负权图,求单源最短路。

Solution

使用堆优化的 Dijkstra 算法,记得开 long long 记录答案。

Code

void R()
{
	using pli=pair<i64,int>;
	int n,m,s;
	cin>>n>>m>>s;
	s--;
	vector<vector<pli>> adj(n);
	for (int i=0;i<m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		u--,v--;
		adj[u].push_back({w,v});
	}

	vector<int> vis(n);
	vector<i64> d(n,-1);
	priority_queue<pli,vector<pli>,greater<pli>> q;
	d[s]=0;
	q.push({0,s});
	while (!q.empty())
	{
		auto [tmp,u]=q.top();
		q.pop();
		if (vis[u]) continue;
		vis[u]=1;
		for (auto [w,v]:adj[u])
			if (d[v]==-1||d[v]>d[u]+w)
			{
				d[v]=d[u]+w;
				q.push({d[v],v});
			}
	}

	for (int i=0;i<n;i++)
		cout<<d[i]<<" \n"[i+1==n];
	return;
}
#牛客春招刷题训练营#
全部评论

相关推荐

昨天 15:37
吉林大学 C++
📍面试公司:DolphinDB智臾科技 💻面试岗位:测开(实习)❓面试问题:1.自我介绍2.介绍一下你做的测试相关的工作--回答的自己的项目3.性能测试除了关注响应时间还关注什么?--这个答得不好,确实也没准备到4.你是如何进行性能测试的?有没有使用到框架?5.除了功能测试,性能测试,还有什么?6.在你模拟并发的时候,你有觉得你的响应时间有变慢吗?7.&nbsp;软件测试的生命周期8.有没有了解过java中写单元测试的框架?比如Junit?9.如何具体的进行性能测试?10.对于数据库的兼容性测试你会怎么考虑?11.对于一个登录场景你会怎么设计测试用例数据库相关:1.数据库的增删改查2.如何添加数据?3.删除数据的三种方式?区别是什么?4.写sql,经典的查学生所有可能的平均分5.给了两个表,写左连接和右连接6.where和and的区别7.主键和唯一的区别Linux相关1.如何查看系统的所有的进程(ps&nbsp;aux)2.如何查看cpu利用率(ps&nbsp;aux&nbsp;--sort=-%cpu/top)3.如何查内存占用率(ps&nbsp;aux&nbsp;--sort=-%mem/top/free&nbsp;-h4.如何杀掉某个进程5.如何根据端口号查询该进程(ps&nbsp;aux&nbsp;|&nbsp;grep&nbsp;8080)6.kill&nbsp;-9&nbsp;PID和kill&nbsp;-15&nbsp;PID的区别是什么?--这个我是真不知道7.如何获取到日志中最后几行?反问:1.如何系统的学习数据库?您能给些建议吗?2.测试人员的主要业务是什么?3.您是如何对数据库进行性能测试的?🙌面试感想:面试官是个小姐姐,很温柔但是我太菜了,sql答得不好,一开始太紧张把增说成add了估计要挂了,人家主做数据库,我数据库答得稀烂下来得猛补数据库了
查看28道真题和解析 面试问题记录
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
06-03 13:57
腾讯 csig腾讯地图后端开发 32k*15 硕士985
备战秋招春招:腾讯总包能比百度高的啊,佬这是不是开发的SSP
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务