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

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

Easy 字符串分隔

简要题意

把给定字符串拆成 8 位一行输出，末行不足位补零。

Solution

读入字符串后，将输出所需的后导零补齐，再每八位输出一个换行即可，C++ 玩家也可以用 substr() 偷懒。

Code

void R()
{
	string s;
	cin>>s;
	int n=s.size();
	for (int i=0;i<(8-n%8)%8;i++)
		s+='0';
	for (int i=0;i<s.size();i+=8)
		cout<<s.substr(i,8)<<'\n';
	return;
}

Medium 质数因子

简要题意

对一个规模上界在 的数进行质因数分解。

Solution

如果 不是质数，它至少存在一对因子 ，两者中小的那个不大于 。

而一个数最小的非 因子一定是质因子，所以我们枚举 以内的数，若它是因子就将其除去并输出。最后判断剩下的是不是 即可。

Code

void R()
{
	int n;
	cin>>n;
	for (int i=2;i*i<=n;i++)
		while (n%i==0)
		{
			cout<<i<<' ';
			n/=i;
		}
	if (n>1) cout<<n;
	return;
}

Hard 合唱队

简要题意

踢出队列中尽量少的元素，使得队列先增后减。

Solution

不难看出答案对应的队列一定是某个位置前面的最长上升子序列+后面的最长下降子序列。

如果能得到每个位置前面的最长上升子序列和后面的最长下降子序列，我们枚举每个位置，取最优答案即可。

上升跟下降是同理的，我们讨论上升。

最长上升子序列是一个经典问题，一个 的做法是 dp（动态规划）：

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

其实这个问题还有一个常用的 的做法（也有人认为这种做法是二分优化 dp 转移）：

在满足最长的前提下，我们维护一个尽量容易插入元素的最长上升子序列。

什么意思呢，就是要让靠后的数尽可能小，或者最小化这个序列反转后的字典序。

怎么做呢？

如果插入的元素比序列的最大元素大，我们直接插。

否则我们在序列里找到第一个比插入元素大的位置，把这个位置上的数换成插入元素。

这样做是不违背上升前提下的最优解。

而找位置这一步是可以二分解决的，所以复杂度就是 的了。

Code

void R()
{
	int n,ans=1e9;
	cin>>n;
	vector<int> h(n),up(n),down(n),tmp;
	for (int &x:h) cin>>x;

	auto solve=[&](int i)->int
	{	
		if (tmp.empty()||tmp.back()<h[i])
			tmp.push_back(h[i]);
		else
			*lower_bound(tmp.begin(),tmp.end(),h[i])=h[i];
		return tmp.size();
	};

	for (int i=0;i<n;i++)
		up[i]=solve(i);
	tmp.clear();
	for (int i=n-1;i>=0;i--)
		down[i]=solve(i);
	for (int i=0;i+1<n;i++)
		ans=min(ans,n-(up[i]+down[i+1]));
	cout<<ans<<'\n';
	return;
}