活動(dòng)地址：?？痛赫兴㈩}訓(xùn)練營(yíng) - 編程打卡活動(dòng)

Easy 【模板】棧

簡(jiǎn)要題意

要求實(shí)現(xiàn)棧支持的操作。

Solution

棧，即先進(jìn)后出 (FILO) 表。支持 插入， 彈出。

STL 中的 stack 實(shí)現(xiàn)了棧的功能。但我個(gè)人的習(xí)慣是將 vector 看成一個(gè)倒過(guò)來(lái)的棧。

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 點(diǎn)擊消除

簡(jiǎn)要題意

對(duì)一個(gè)字符串反復(fù)消去相鄰相同字母，求該字符串最終形態(tài)。

Solution

用一個(gè)棧維護(hù)答案，如果將要插入一個(gè)與棧頂相同的字母就不進(jìn)行插入，而是將棧頂彈出。

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 小紅取數(shù)

簡(jiǎn)要題意

給定一個(gè)數(shù)組，問(wèn)從中選取一些數(shù)，使得它們之和為 的倍數(shù)的前提下，它們之和最大是多少。

Solution

要判斷某個(gè)數(shù)是否為 的倍數(shù)，我們只需要判斷它對(duì) 取余是否為 ，所以記 表示對(duì) 取余為 前提下的最大和，然后做 背包即可。

下面代碼的 dp 數(shù)組中維護(hù)的是 ，不失正確性。

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;
}