2023.3.12 模拟赛题解

天黑黑

题意

大致：给出含 \(\max\) 和 \(+\) 的表达式以及其中的 \(n\) 个数，求其最大值。

用前缀表达式的形式给出，X 表示一个要填的数，B 表示 \(\max\)，A 表示 \(+\)。

题解

我们考虑把式子转移到树上。然后尝试找一找结论。

看了很久，发现其实我们只要最大化最终选的数个数就行，总有方案可以满足。证明不会，反正感觉很对。

具体实现也不难，首先一种是真的建树跑 dfs，节点是 \(\max\) 则为 \(V\gets\max(V_{lc},V_{rc})\)；为 \(+\) 则是 \(V\gets V_{lc}+V_{rc}\)。

发现完全没必要，直接用栈实现一下就行。把原字符串倒过来搞成后缀表达式直接莽。

最后贪心一下，选最大的那些数。

小样例对的啊？写了个小数据对拍，没错就干脆不管了。

#include <stdio.h>
#include <assert.h>
#include <string.h>
template<class T=int,size_t maxn=10000>
class restack
{
private:
	size_t cnt;
	T q[maxn];
public:
	restack()
	{
		cnt=0;
	}
	inline T top()
	{
		if(cnt<1)
			assert(0);
		return q[cnt];
	}
	inline void push(const T &x)
	{
		if(cnt>=maxn)
			assert(0);
		q[++cnt]=x;
		return ;
	}
	inline T end()
	{
		return q[1];
	}
	inline void pop()
	{
		if(cnt<1)
			assert(0);
		--cnt;
		return ;
	}
	inline const bool empty()
	{
		return cnt==0;
	}
};
restack<int,200005> st;
char str[200005];
inline int max(int x,int y)
{
	return x>y?x:y;
}
#include <algorithm>
int len,i,ret,x,y,cntx,go;
int v[200005];
int main()
{
	scanf("%s",str+1);len=strlen(str+1);
	for(i=len;i>=1;--i)
	{
		if(str[i]=='X')
		{
			st.push(1);
			++cntx;
		}
		else if(str[i]=='A')
		{
			x=st.top();st.pop();
			y=st.top();st.pop();
			st.push(x+y);
		}else
		{
			x=st.top();st.pop();
			y=st.top();st.pop();
			st.push(max(x,y));
		}
	}
	for(i=1;i<=cntx;++i)
	{
		scanf("%d",v+i);
	}
	std::sort(v+1,v+cntx+1);
	go=st.end();
	for(i=cntx-go+1;i<=cntx;++i)
	{
		ret+=v[i];
	}
	printf("%lld",ret);
	return 0;
}