P8997 题解

P8997

思路

按题意模拟，用栈建出二叉树，叶子节点是要填的值，非叶子是运算符。

判断一个叶子能贡献能填哪些数并最终成为答案，即 dp 计算要使该叶子的值 \(ans\) 成为答案最少要填 \(num0\) 个 \(<=ans\) 和 \(num1\) 个 \(>ans\) 的数。发现 dp 只与 \(\le ans\) 和 \(>ans\) 的数的个数有关，可以统一计算。

设 \(dp_{u,0/1,0/1}\) 表示 \(u\) 子树内，\(u\) 处的值 \(\le ans\) 或 \(>ans\)，\(num0\) 或 \(num1\) 最少为多少。根据 \(u\) 处的运算符分类讨论转移。如果 \(u\) 处运算符为 \(<\)，如果 \(u\) 的值 \(\le ans\)，那 \(ls\) 和 \(rs\) 的值有一个 \(\le ans\) 即可；否则两个都有 \(>ans\)。运算符为 \(>\) 同理。

对于每个叶子算限制，只与从根到 \(u\) 的 dp 值有关。因为叶子的值为 \(ans\)，所以在路径上如果 \(u\) 点运算符为 \(<\)，要进入左儿子，那么右儿子的值 \(>ans\)，左儿子的值 \(\le ans\)，\(num0\) 加上 \(dp_{rs,1,0}\)，\(num1\) 加上 \(dp_{rs,1,1}\)。其他同理。

可以发现放在一个叶子的答案是一个区间 \([num0+1,n-num1]\)，差分维护区间加，最后计算大于 \(0\) 的位置数。

code

int n,m,ans;
char s[maxn<<2];
int st[maxn],tp;
int ls[maxn],rs[maxn],op[maxn],dp[maxn][2][2],idx;
void dfs(int u){
	if(op[u]==3){
		dp[u][0][0]=1,dp[u][1][1]=1;
		return ;
	}
	dfs(ls[u]),dfs(rs[u]);
	if(op[u]==1){
		dp[u][0][0]=min({dp[ls[u]][0][0]+dp[rs[u]][0][0],dp[ls[u]][0][0]+dp[rs[u]][1][0],dp[ls[u]][1][0]+dp[rs[u]][0][0]});
		dp[u][0][1]=min({dp[ls[u]][0][1]+dp[rs[u]][0][1],dp[ls[u]][0][1]+dp[rs[u]][1][1],dp[ls[u]][1][1]+dp[rs[u]][0][1]});
		dp[u][1][0]=dp[ls[u]][1][0]+dp[rs[u]][1][0];
		dp[u][1][1]=dp[ls[u]][1][1]+dp[rs[u]][1][1];
	}
	else{
		dp[u][0][0]=dp[ls[u]][0][0]+dp[rs[u]][0][0];
		dp[u][0][1]=dp[ls[u]][0][1]+dp[rs[u]][0][1];
		dp[u][1][0]=min({dp[ls[u]][1][0]+dp[rs[u]][1][0],dp[ls[u]][1][0]+dp[rs[u]][0][0],dp[ls[u]][0][0]+dp[rs[u]][1][0]});
		dp[u][1][1]=min({dp[ls[u]][1][1]+dp[rs[u]][1][1],dp[ls[u]][1][1]+dp[rs[u]][0][1],dp[ls[u]][0][1]+dp[rs[u]][1][1]});
	}
}
int f[maxn];
void calc(int u,int l,int r){
	if(op[u]==3){
		f[l+1]++,f[m-r+1]--;
		return ;
	}
	if(op[u]==1){
		calc(ls[u],l+dp[rs[u]][1][0],r+dp[rs[u]][1][1]),calc(rs[u],l+dp[ls[u]][1][0],r+dp[ls[u]][1][1]);
	}
	else{
		calc(ls[u],l+dp[rs[u]][0][0],r+dp[rs[u]][0][1]),calc(rs[u],l+dp[ls[u]][0][0],r+dp[ls[u]][0][1]);
	}
}
void work(){
	scanf("%s",s+1);n=strlen(s+1);
	for(int i=1;i<=n;i++){
		if(s[i]=='m'){
			if(s[i+1]=='i')st[++tp]=++idx,op[idx]=1;
			else st[++tp]=++idx,op[idx]=2;
			if(s[i-1]=='(')ls[st[tp-1]]=st[tp];
			if(s[i-1]==',')rs[st[tp-1]]=st[tp];
		}
		if(s[i]=='?'){
			op[++idx]=3;++m;
			if(s[i-1]=='(')ls[st[tp]]=idx;
			if(s[i-1]==',')rs[st[tp]]=idx;			
		}
		if(s[i]==')')tp--;
	}
	dfs(1);calc(1,0,0);
	for(int i=1;i<=m;i++)f[i]+=f[i-1],ans+=f[i]>0;
	printf("%lld\n",ans);
}