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

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

Easy 小红的多彩糖葫芦

简要题意

给一个字符串，问第一对相邻相同字母的出现位置。

Solution

直接模拟即可。

Code

void R()
{
	string s;
	cin>>s;
	int n=s.size(),ans=0;
	char lst=' ';
	for (int i=0;i<n;i++)
		if (s[i]==lst) break;
		else ans++,lst=s[i];
	cout<<ans;
	return;
}

Medium 小红的好数

简要题意

考虑所有 内的整数，补前导 对齐至 位数，若 个数位互不相同则称这个数是好数。

求第 大的好数。

Solution

值域很小，不妨直接枚举 个数位的数判断。

Code

void R()
{
	int k;
	cin>>k;
	for (int a=9;a>=0;a--)
		for (int b=9;b>=0;b--)
			for (int c=9;c>=0;c--)
				for (int d=9;d>=0;d--)
					for (int e=9;e>=0;e--)
					{
						map<int,int> cnt;
						cnt[a]++;
						cnt[b]++;
						cnt[c]++;
						cnt[d]++;
						cnt[e]++;
						if (max({cnt[a],cnt[b],cnt[c],cnt[d],cnt[e]})==1)
						{
							k--;
							if (k==0)
							{
								cout<<a<<b<<c<<d<<e;
								return;
							}
						}
					}
	return;
}

Hard 滑雪

简要题意

给一个 的矩阵，求其中的最长严格单调路径。

Solution

记 为以 结尾的最长严格单调路径长度。

对 个位置按照其上的数排序，按顺序枚举位置，从其上下左右的格子向自身转移，全局 就是答案。

Code

void R()
{
	int n,m,ans=0;
	cin>>n>>m;
	vector<tuple<int,int,int>> v;
	vector<vector<int>> a(n,vector<int>(m)),dp(a);
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
		{
			cin>>a[i][j];
			v.emplace_back(a[i][j],i,j);
		}
	sort(v.begin(),v.end());
	reverse(v.begin(),v.end());
	for (auto [x,i,j]:v)
	{
		dp[i][j]=1;
		if (i&&a[i][j]<a[i-1][j])
			dp[i][j]=max(dp[i][j],dp[i-1][j]+1);
		if (j&&a[i][j]<a[i][j-1])
			dp[i][j]=max(dp[i][j],dp[i][j-1]+1);
		if (i+1<n&&a[i][j]<a[i+1][j])
			dp[i][j]=max(dp[i][j],dp[i+1][j]+1);
		if (j+1<m&&a[i][j]<a[i][j+1])
			dp[i][j]=max(dp[i][j],dp[i][j+1]+1);
		ans=max(ans,dp[i][j]);
	}
	cout<<ans;
	return;
}