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

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

Easy 小红结账

简要题意

有一个长度为 ，初始值均为 的数组。

对其进行 次操作，每次选取 个位置，令这些位置上的数增加 ，求操作后的数组。

Solution

直接模拟简要题意中的操作即可。

Code

void R()
{
	int n,m;
	cin>>n>>m;
	vector<i64> ans(m);
	for (int i=0;i<n;i++)
	{
		int k,c;
		cin>>k>>c;
		for (int j=1;j<k;j++)
		{
			int x;
			cin>>x;
			ans[x-1]+=(c+k-1)/k;
		}
	}
	for (int i=0;i<m;i++)
		cout<<ans[i]<<" \n"[i+1==m];
	return;
}

Medium 跳跃游戏(一)

简要题意

给一个数组 ，到达位置 时，你可以向后跳至多 格，确定能否从第 格跳到最后一格。

Solution

如果能跳到某一格，一定能跳到后面的所有格。

从前到后遍历每一格，并维护当前能跳到的最远格 ，如果遍历到的格子超过 就不再遍历。

如果能遍历完 格就代表能跳到最后一格。

Code

void R()
{
	int n,mx=0;
	cin>>n;
	vector<int> a(n);
	for (int &x:a) cin>>x;
	for (int i=0;i<=min(mx,n-1);i++)
		mx=max(mx,i+a[i]);
	cout<<(mx>=n-1?"true":"false");
	return;
}

Hard 郊区春游

简要题意

给一个 点 边带权无向图，钦定 个必经点。任选起点，求经过所有必经点的最小花费。

Solution

注意 很小，我们二进制状压已经过的点，记 表示状压状态为 ，当前在第 个必经点的最小花费。

先 Floyd 预处理两点间最短路，然后依次枚举状态、当前节点、目标节点转移即可。

即为答案。

Code

void R()
{
	constexpr int inf=1e9;
	int n,m,R;
	cin>>n>>m>>R;
	vector<int> key(R);
	vector<vector<int>> d(n,vector<int>(n,inf)),dp(1<<R,vector<int>(R,inf));
	for (int &x:key) cin>>x,x--;
	for (int i=0;i<m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		u--,v--;
		d[u][v]=d[v][u]=w;
	}

	for (int k=0;k<n;k++)
		for (int i=0;i<n;i++)
			for (int j=0;j<n;j++)
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

	for (int i=0;i<R;i++) dp[1<<i][i]=0;
	for (int S=0;S<(1<<R);S++)
		for (int i=0;i<R;i++)
			for (int j=0;j<R;j++)
				if ((S>>i&1)&&!(S>>j&1))
					dp[S|(1<<j)][j]=min(dp[S|(1<<j)][j],dp[S][i]+d[key[i]][key[j]]);

	cout<<*min_element(dp[(1<<R)-1].begin(),dp[(1<<R)-1].end());
	return;
}