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

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

Easy 小红的矩阵

简要题意

数矩阵中个位数是 的数的个数。

Solution

遍历考察 即可。

Code

void R()
{
	int n,m,ans=0;
	cin>>n>>m;
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
		{
			int x;
			cin>>x;
			ans+=(x%10==9);
		}
	cout<<ans;
	return;
}

Medium 游游的最小公倍数

简要题意

求 的条件下的 。

Solution

显然要尽量让 靠近 ，并且若 ，则 更大的 对不可能产生更大的 。

Code

i128 gcd(i128 a,i128 b)
{
	return b?gcd(b,a%b):a;
}

void R()
{
	i64 n,ansa=1,ansb=1;
	cin>>n;
	i128 a=n/2,b=n-a;
	for (;;a--,b++)
	{
		if (a*b/gcd(a,b)>ansa*ansb/gcd(ansa,ansb))
			ansa=a,ansb=b;
		if (gcd(a,b)==1) break;
	}
	cout<<ansa<<' '<<ansb<<'\n';
	return;
}

Hard 【模板】单源最短路Ⅰ ‖ 无权图

简要题意

给定一张有向无权图，求单源最短路。

Solution

BFS 即可。

Code

void R()
{
	int n,m,s;
	cin>>n>>m>>s;
	s--;
	vector<int> d(n,-1);
	vector<vector<int>> adj(n);
	while (m--)
	{
		int u,v;
		cin>>u>>v;
		u--,v--;
		adj[u].push_back(v);
	}

	queue<int> q;
	d[s]=0;
	q.push(s);
	while (!q.empty())
	{
		int u=q.front();
		q.pop();
		for (int v:adj[u])
			if (d[v]==-1)
			{
				d[v]=d[u]+1;
				q.push(v);
			}
	}
	for (int i=0;i<n;i++)
		cout<<d[i]<<" \n"[i+1==n];
	return;
}