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

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

Easy 小红的校招笔试

简要题意

现给出 个人的分数，其中成绩前 （下取整）的人可以过线，同分者同时过线，求第一个人能否过线。

Solution

记录第一个人的分数，对分数降序排序，与第 的分数比较即可。

Code

void R()
{
	int n,x;
	cin>>n;
	vector<int> a(n);
	for (int &x:a) cin>>x;

	x=a[0];
	sort(a.begin(),a.end());
	reverse(a.begin(),a.end());
	cout<<(a[n/2-1]<=x?"Yes":"No");
	return;
}

Medium 小红的区间查询

简要题意

给定一个数组与若干次操作，每次操作为下面二者之一：

• 修改某个位置的数

• 查询某段前缀中某个数的出现次数

Solution

数据范围很小，暴力修改查询即可。

Code

void R()
{
	int n,q;
	cin>>n>>q;
	vector<int> a(n);
	for (int &x:a) cin>>x;
	while (q--)
	{
		int op,i,x;
		cin>>op>>i>>x;
		if (op==1) a[i-1]=x;
		else
		{
			int ans=0;
			for (int j=0;j<i;j++)
				ans+=(a[j]==x);
			cout<<ans<<'\n';
		}
	}
	return;
}

Hard 最长回文子序列

简要题意

求一个字符串的最长回文子序列。

Solution

区间 dp ，记 为区间 上的最长回文子序列长度：

如果 ，答案从 转移而来；

否则答案从 或 转移而来，记忆化搜索转移即可。

Code

void R()
{
	string s;
	cin>>s;
	int n=s.size();
	vector<vector<int>> f(n,vector<int>(n)),vis(f);

	auto dp=[&](auto &self,int l,int r)->int
	{
		if (l>r) return 0;
		if (vis[l][r]) return f[l][r];
		vis[l][r]=1;
		if (s[l]==s[r]) return f[l][r]=self(self,l+1,r-1)+(l!=r)+1;
		return f[l][r]=max(self(self,l+1,r),self(self,l,r-1));
	};

	cout<<dp(dp,0,n-1);
	return;
}