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

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

Easy 变幻莫测

简要题意

给定两个整数 ，可以执行任意次操作，操作有下面两种：

• 交换

• 记 ，

求使 的最小操作次数，或报告无解。

Solution

状态数很少，BFS 即可。

需要注意的是，允许运算中间有数超出读入数据范围。

Code

void R()
{
	map<pair<int,int>,bool> vis;
	int X,Y,ans=-1;
	cin>>X>>Y;
	queue<tuple<int,int,int>> q;
	vis[{X,Y}]=1;
	q.push({X,Y,0});
	while (!q.empty())
	{
		auto [x,y,d]=q.front();
		q.pop();
		if (x==y)
		{
			ans=d;
			break;
		}
		if (!vis.count({y,x}))
			vis[{y,x}]=1,q.push({y,x,d+1});
		if (!vis.count({x+y,x-y})&&abs(x+y)<=1000&&abs(x-y)<=1000)
			vis[{x+y,x-y}]=1,q.push({x+y,x-y,d+1});
	}
	cout<<ans;
	return;
}

Medium 平均数为k的最长连续子数组

简要题意

给定一个数组，求平均数为k的最长连续子数组。

Solution

将所有数减去 ，问题转化为求前缀和相同的两个位置的最远距离。

Code

void R()
{
	int n,k,ans=-1;
	cin>>n>>k;
	vector<i64> a(n+1);
	map<i64,vector<int>> pos;
	for (int i=1;i<=n;i++)
		cin>>a[i],a[i]-=k;
	partial_sum(a.begin(),a.end(),a.begin());
	for (int i=0;i<=n;i++)
		pos[a[i]].push_back(i);
	for (auto &[t,v]:pos)
		if (v.size()>1)
			ans=max(ans,v.back()-v[0]);
	cout<<ans;
	return;
}

Hard 最大子矩阵

简要题意

给定一个矩阵，求其权值最大的非空子矩阵。

Solution

一个简单的想法是 枚举子矩阵，但是时限比较紧张。

考虑先只枚举子矩阵的上下是哪行，中间做一次前缀和，就变成求最大子段和，可以 处理。

Code

void R()
{
	int n,ans=-1e9;
	cin>>n;
	vector<vector<int>> a(n+1,vector<int>(n+1));
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
		{
			cin>>a[i][j];
			a[i][j]+=a[i-1][j];
		}

	for (int l=1;l<=n;l++)
		for (int r=l;r<=n;r++)
		{
			vector<int> tmp(n+1);
			for (int i=1;i<=n;i++)
			{
				tmp[i]=a[r][i]-a[l-1][i];
				tmp[i]+=max(tmp[i-1],0);
				ans=max(ans,tmp[i]);
			}
		}
	cout<<ans;
	return;
}