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

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

Easy 小红的好数组

简要题意

问至少需要多少次元素修改，才能使给定数组不含长度为 的非降子数组。

Solution

从前往后扫，每遇到一个长度为 的非降子数组，就从中间破坏即可。

Code

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

Medium 压缩二维码

简要题意

给一个 的黑白网格，将其每 4 位压缩为一个十进制数。

Solution

不妨把网格看成一长串黑白条，对其模拟每 位压缩一次即可。

Code

void R()
{
	int n;
	string s;
	cin>>n;
	for (int i=0;i<(1<<n);i++)
	{
		string t;
		cin>>t;
		s+=t;
	}
	for (int i=0;i<s.size();i+=4)
	{
		int tmp=0;
		for (int j=0;j<4;j++)
		{
			tmp<<=1;
			if (s[i+j]=='#')
				tmp|=1;
		}
		cout<<tmp<<" \n"[i+4==s.size()];
	}
	return;
}

Hard 分割等和子集

简要题意

给定一些正整数，问能否选出一部分，使得选出的数之和与剩下的数之和相同。

Solution

判断一下元素和奇偶，奇数必然无解，偶数 背包判断即可。

Code

void R()
{
	int n,sum=0;
	cin>>n;
	vector<int> a(n);
	for (int &x:a) cin>>x,sum+=x;
	if (sum&1)
	{
		cout<<"false";
		return;
	}

	vector<int> dp(sum/2+1);
	dp[0]=1;
	for (int x:a)
		for (int i=sum/2+1-x;i>=0;i--)
			dp[i+x]|=dp[i];
	if (dp.back()) cout<<"true";
	else cout<<"false";
	return;
}