牛客春招刷题训练营 - 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;
}