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

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

Easy 小苯的比赛上分

简要题意

给 个数与 次操作，每次将当前 个数中最小的一个增加，并求此时 个数的 。

Solution

用堆维护 个数，边加边维护最大值即可。

Code

void R()
{
	int n,m,mx=0;
	priority_queue<int,vector<int>,greater<int>> q;
	cin>>n>>m;
	while (n--)
	{
		int x;
		cin>>x;
		q.push(x);
		mx=max(mx,x);
	}
	while (m--)
	{
		int x,t=q.top();
		cin>>x;
		q.pop();
		q.push(t+x);
		mx=max(mx,t+x);
		cout<<mx<<'\n';
	}
	return;
}

Medium 小欧安排座位

简要题意

对 ，有的数 希望排在第 位，有的希望不排在第 位。构造一个排列使得满足尽可能多的要求。

Solution

把希望错排的数挑出来做循环移位即可。

Code

void R()
{
	int n;
	string s;
	cin>>n>>s;
	vector<int> a(n),v;
	iota(a.begin(),a.end(),1);
	for (int i=0;i<n;i++)
		if (s[i]=='1')
			v.push_back(i);
	for (int i=0;i+1<v.size();i++)
		swap(a[v[i]],a[v[i+1]]);
	for (int i=0;i<n;i++)
		cout<<a[i]<<" \n"[i+1==n];	
	return;
}

Hard 小苯的数字权值

简要题意

把 分解为若干个非 正整数的乘积，使得分解出来的数的因子个数和最大，你只需要求出这个最大的因子个数和。

Solution

预处理出所有数的因子，然后 dp 即可。

记 为 的答案，有转移：

Code

constexpr int N=2e5+7;
vector<vector<int>> d(N);
vector<int> dp(N);

void R()
{
	int x;
	cin>>x;
	cout<<dp[x]<<'\n';
	return;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	for (int i=1;i<N;i++)
		for (int j=1;i*j<N;j++)
			d[i*j].push_back(i);

	for (int i=1;i<N;i++)
	{
		dp[i]=d[i].size();
		for (int t:d[i])
			if (t!=1&&t!=i)
				dp[i]=max(dp[i],dp[t]+dp[i/t]);
	}

	int T=1;
	cin>>T;
	while (T--) R();
	return 0;
}