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

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

Easy 小红的顺子

简要题意

给一个由 挖去一位得到的数组，求这一位前后数字个数的 。

Solution

暴力寻找被挖去的位即可。

Code

void R()
{
	int n;
	cin>>n;
	vector<int> a(n-1);
	for (int &x:a) cin>>x;
	for (int i=0;i<n;i++)
		if (a[i]!=i+1)
		{
			cout<<max(i,n-i-1);
			return;
		}
	cout<<n-1;
	return;
}

Medium 小红的字符生成

简要题意

你有 个字母 a，每次可以将两个相同字母合成为字典序大一位的字母，求最后得到的最短字符串。

Solution

字典序第 大的字母相当于 个 a，于是转化为二进制拆分问题。

Code

void R()
{
	int x;
	cin>>x;
	for (char c='a';x;x/=2,c++)
		if (x&1) cout<<c;
	return;
}

Hard 最少的完全平方数

简要题意

求最少需要多少个完全平方数，使得它们的和可以表示正整数 。

Solution

记 表示 的答案，有转移：

Code

void R()
{
	constexpr int inf=1e9;
	int n;
	cin>>n;
	vector<int> dp(n+1,inf);
	dp[0]=0;
	for (int i=1;i<=n;i++)
		for (int j=1;j*j<=i;j++)
			dp[i]=min(dp[i],dp[i-j*j]+1);
	cout<<dp[n];
	return;
}