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

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

Easy 小红的合数寻找

简要题意

找区间 内的合数，或报告无解。

Solution

数据范围很小，枚举后暴力判断是否为合数即可。

Code

void R()
{
	auto isp=[&](int x)->bool
	{
		for (int i=2;i<x;i++)
			if (x%i==0)
				return 0;
		return 1;
	};

	int x;
	cin>>x;
	for (int i=x;i<=2*x;i++)
		if (!isp(i))
		{
			cout<<i;
			return;
		}
	cout<<-1;
	return;
}

Medium 走迷宫

简要题意

给一个 的网格图，右部分格子为障碍格，求从 移动到 的最小步数，或报告无解。

Solution

因为每次移动都会产生 的步数，所以从起点跑 BFS 即可。

Code

void R()
{
	constexpr int inf=1e9;
	int n,m,xs,ys,xt,yt;
	queue<pair<int,int>> q;
	cin>>n>>m>>xs>>ys>>xt>>yt;
	xs--,ys--,xt--,yt--;
	vector<string> G(n);
	vector<vector<int>> d(n,vector<int>(m,inf));
	d[xs][ys]=0;
	q.push({xs,ys});
	for (auto &x:G) cin>>x;

	while (!q.empty())
	{
		int xu=q.front().first;
		int yu=q.front().second;
		q.pop();

		auto extend=[&](int xv,int yv)->void
		{
			if (xv<0||yv<0||xv>=n||yv>=m) return;
			if (G[xv][yv]=='*') return;
			if (d[xu][yu]+1>=d[xv][yv]) return;
			d[xv][yv]=d[xu][yu]+1;
			q.push({xv,yv});
		};

		extend(xu-1,yu);
		extend(xu+1,yu);
		extend(xu,yu-1);
		extend(xu,yu+1);
	}

	if (d[xt][yt]==inf) cout<<-1;
	else cout<<d[xt][yt];
	return;
}

Hard 字母收集

简要题意

给定 的字母矩阵，规定字母 l,o,v,e 的权值分别为 ，其余字母权值均为 ，求左上到右下的非降路径的最大权值和。

Solution

记 表示从 走过一条非降路径到达 的最大权值和，有转移：

即为答案。

Code

void R()
{
	int n,m;
	cin>>n>>m;
	vector<string> G(n);
	vector<vector<int>> dp(n,vector<int>(m));
	for (auto &x:G) cin>>x;

	auto calc=[&](int i,int j)->int
	{
		char c=G[i][j];
		if (c=='l') return 4;
		if (c=='o') return 3;
		if (c=='v') return 2;
		if (c=='e') return 1;
		return 0;
	};

	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
		{
			if (i) dp[i][j]=max(dp[i][j],dp[i-1][j]);
			if (j) dp[i][j]=max(dp[i][j],dp[i][j-1]);
			dp[i][j]+=calc(i,j);
		}
	cout<<dp[n-1][m-1];
	return;
}