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

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

Easy 【模板】栈

简要题意

要求实现栈支持的操作。

Solution

栈，即先进后出 (FILO) 表。支持 插入， 弹出。

STL 中的 stack 实现了栈的功能。但我个人的习惯是将 vector 看成一个倒过来的栈。

Code

void R()
{
	int n;
	cin>>n;
	vector<int> s;
	while (n--)
	{
		string op;
		cin>>op;
		if (op=="push")
		{
			int x;
			cin>>x;
			s.push_back(x);
		}
		else
		{
			if (s.empty()) cout<<"error\n";
			else
			{
				cout<<s.back()<<'\n';
				if (op=="pop") s.pop_back();
			}
		}
	}
	return;
}

Medium 点击消除

简要题意

对一个字符串反复消去相邻相同字母，求该字符串最终形态。

Solution

用一个栈维护答案，如果将要插入一个与栈顶相同的字母就不进行插入，而是将栈顶弹出。

Code

void R()
{
	string s,t;
	cin>>s;
	for (char c:s)
	{
		if (!t.empty()&&t.back()==c)
			t.pop_back();
		else t.push_back(c);
	}
	if (t.empty()) cout<<0;
	else cout<<t;
	return;
}

Hard 小红取数

简要题意

给定一个数组，问从中选取一些数，使得它们之和为 的倍数的前提下，它们之和最大是多少。

Solution

要判断某个数是否为 的倍数，我们只需要判断它对 取余是否为 ，所以记 表示对 取余为 前提下的最大和，然后做 背包即可。

下面代码的 dp 数组中维护的是 ，不失正确性。

Code

void R()
{
	constexpr i64 inf=1e11;
	int n,k;
	cin>>n>>k;
	vector<i64> dp(k,-inf);
	dp[0]=0;
	for (int i=0;i<n;i++)
	{
		i64 x,w,v;
		cin>>x;
		w=x/k,v=x%k;
		vector<i64> ndp(dp);
		for (int j=0;j<k;j++)
		{
			if (j+v<k)
				ndp[j+v]=max(ndp[j+v],dp[j]+w);
			else
				ndp[j+v-k]=max(ndp[j+v-k],dp[j]+w+1);
		}
		swap(dp,ndp);
	}
	if (dp[0]==0) cout<<-1;
	else cout<<dp[0]*k;
	return;
}