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

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

Easy 查找输入整数二进制中1的个数

简要题意

如题。

Solution

使用 __builtin_popcount() 即可。

Code

void R()
{
	int n,m;
	cin>>n>>m;
	cout<<__builtin_popcount(n)<<'\n'<<__builtin_popcount(m);
	return;
}

Medium 宝石手串

简要题意

给一个环形数组，问两个相同元素间最小距离。

Solution

我们把数组复制一遍，统计距离时忽略超过 的就好。

这也是破环成链的一个常用技巧。

Code

void R()
{
	int n,ans=1e9;
	string s;
	cin>>n>>s;
	s+=s;
	map<char,int> lst;
	for (int i=0;i<n*2;i++)
	{
		if (lst.count(s[i])&&i-lst[s[i]]<n)
			ans=min(ans,i-lst[s[i]]-1);
		lst[s[i]]=i;
	}
	if (ans==1e9) cout<<"-1\n";
	else cout<<ans<<'\n';
	return;
}

Hard 最长上升子序列(一)

简要题意

给定一个整数数组，求其最长上升子序列。

Solution

动态规划。

设 为以位置 结尾的最长上升子序列长度，有转移：

数组中最大值就是答案。

Code

void R()
{
	int n;
	cin>>n;
	vector<int> a(n),dp(n);
	for (int &x:a) cin>>x;
	for (int i=0;i<n;i++)
	{
		dp[i]=1;
		for (int j=0;j<i;j++)
			if (a[i]>a[j])
				dp[i]=max(dp[i],dp[j]+1);
	}
	cout<<*max_element(dp.begin(),dp.end());
	return;
}