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

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

Easy 字符串字符匹配

简要题意

给定字符串 ，问所有 中出现字母是否都在 中出现。

Solution

记录一下每个字母是否在 中出现，若在 中出现再消去标记，最后看有无标记剩余就好。

Code

void R()
{
	string s,t;
	cin>>s>>t;
	vector<int> vis(26);
	for (char c:s)
		vis[c-'a']=1;
	for (char c:t)
		vis[c-'a']=0;
	if (count(vis.begin(),vis.end(),1))
		cout<<"false";
	else cout<<"true";
	return;
}

Medium 小红的区间构造

简要题意

构造区间 ，使得 ，且区间内恰有 个 的倍数，或报告无解。

Solution

先构造 和长度都最小，且区间内恰有 个 的倍数的区间 。

之后 最多向左延伸 ， 最多向右延伸 。

当 时尝试延伸，若延伸后仍有 或 越界则无解。

Code

void R()
{
	i64 n,k,x;
	cin>>n>>k>>x;
	i64 l=x,r=n*x;
	k-=r-l+1;
	i64 t=min(k,x-1);
	l-=t,k-=t;
	t=min(k,x-1);
	r+=t,k-=t;
	if (k||r>=2e9) cout<<-1;
	else cout<<l<<' '<<r;
	return;
}

Hard 最长公共子序列(一)

简要题意

给定两个字符串，求它们的最长公共子序列。

Solution

感觉空间复杂度 并不现实，因为你存字符串也是要空间的。

存第一个串在线处理第二个还好说，如果 ，意味着你得到完整的第二个串时前面第一个串只能保留 的信息，就很困难了。

下面给一个 空间复杂度的做法：

先把第一个串读入，一边读入第二个串的字母一边 dp 。

记 为第一个串的 前缀与当前第二个串已读入部分的最长公共子序列长度。

在读入字符 时有转移：

数组中最大值就是答案。

Code

void R()
{
	int n,m;
	string s;
	cin>>n>>m>>s;
	vector<int> dp(n);
	for (int i=0;i<m;i++)
	{
		char c;
		cin>>c;
		int mx=0;
		for (int j=0;j<n;j++)
		{
			int t=mx;
			mx=max(mx,dp[j]);
			if (s[j]==c)
				dp[j]=max(dp[j],t+1);
		}
	}
	cout<<*max_element(dp.begin(),dp.end());
	return;
}