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

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

Easy 求最大连续bit数

简要题意

给一个整数，求其二进制表示下最长连续 1 的长度。

Solution

反复右移逐位判断即可。

Code

void R()
{
	int n,len=0,ans=0;
	cin>>n;
	while (n)
	{
		if (n&1) len++,ans=max(ans,len);
		else len=0;
		n>>=1;
	}
	cout<<ans;
	return;
}

Medium 小红的排列构造

简要题意

给定 串 ，构造排列 使得：

当 时， 不构成排列；

当 时， 构成排列。

无解则输出 。

Solution

贪婪地，如果 我们在位置 放置前面未出现的最小的数，否则放第二小的。

当至少有两个数未放置时，一定符合题意。

问题在于如果 ， 一定是一个排列，此时报告无解。

Code

void R()
{
	int n;
	string s;
	cin>>n>>s;
	set<int> st;
	if (s.back()=='0')
	{
		cout<<-1;
		return;
	}
	for (int i=1;i<=n;i++)
		st.insert(i);
	for (char c:s)
	{
		auto it=st.begin();
		if (c=='0') it++;
		cout<<*it<<' ';
		st.erase(it);
	}
	return;
}

Hard [NOIP2001]装箱问题

简要题意

给一个容量为 的背包和 个体积为 的物品，求向包中放入某些物品后，背包剩余空间的最小值。

Solution

很板的背包 dp 。

设 代表背包已占用 空间的方案数。

考虑放入一个体积为 的物品，有转移：

然后找 数组中最大的有值的位置就好。

其实我们只在意有没有方案，不在意方案数是多少，所以直接取或转移也行。

Code

void R()
{
	int V,n;
	cin>>V>>n;
	vector<int> dp(V+1);
	dp[0]=1;
	for (int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		for (int j=V;j>=x;j--)
			dp[j]|=dp[j-x];
	}
	for (int i=V;i>=0;i--)
		if (dp[i])
		{
			cout<<V-i;
			return;
		}
	return;
}