自动搬运

查看原文

来自洛谷，原作者为

	一只小兔子 只会压行的蒟蒻

搬运于2025-08-24 21:34:20，当前版本为作者最后更新于2022-07-31 08:12:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

因为是树形结构，所以一定有递归。

考虑如何让一个应该有 $K$ 个彩球的（非叶子节点）子树平衡：

• 若 $K$ 为奇数，有两种情况。（左子树或右子树多一个彩球）

• 若 $K$ 为偶数，只有一种情况。（左右子树平分彩球）

向子树传递其应该有多少彩球即可。

对于叶子节点，如果计算下来发现其应有多于一个或少于零个彩球，说明此方法非法，否则记录所需步骤。

因为移动彩球只与叶子节点有关，那么只在叶子节点统计答案就可以了，需要在此叶子节点加球或减球时加步骤。注意这种记录方法会把每次操作记两遍（一次减球一次加球），答案要除以二。

剩下的就是预处理字符串了：给定一棵子树的中序遍历字符串，找到其左子树和右子树。可以用栈预处理也可以直接搜索建树，方法自选。

因为是 256ms 时限，所以数据不会太卡。复杂度 $O(n\epsilon)$ 可过，其中 $n$ 是字符串长度，$\epsilon$ 是一极小常数，主要来自于多解情况。

#include<cstdio>//P2131 ?
#include<cstring>
const int N=5005;
char p[N];int par[N],stk[N],top;
int search(int l,int r,int req){
	if(r-l==1){return req<=1?req:-1;}
	if(r-l==2){return req<=1?(1-req):-1;}
	int rq,t,te=0,tas=9999,ll=l+1,lr=par[l+1],rl=par[r-1],rr=r-1;
	if((req&1)==0){
		rq=req>>1;te=0;
		t=search(ll,lr,rq);if(t==-1)goto impossible;else te+=t;
		t=search(rl,rr,rq);if(t==-1)goto impossible;else te+=t;tas=te;
	}else{
		rq=req>>1;
		right_1:te=0;
		t=search(ll,lr,rq);if(t==-1)goto left_1;else te+=t;
		t=search(rl,rr,rq+1);if(t==-1)goto left_1;else te+=t;if(tas>te)tas=te;
		left_1:te=0;
		t=search(ll,lr,rq+1);if(t==-1)goto impossible;else te+=t;
		t=search(rl,rr,rq);if(t==-1)goto impossible;else te+=t;if(tas>te)tas=te;
	}
	impossible:if(tas==9999)return -1;return tas;
}
int main(){
	scanf("%s",p+1);char* pt=p;int td=0;
	while(*(++pt)){if(*pt=='B')++td;
		else if(*pt=='(')stk[++top]=pt-p;
		else if(*pt==')')par[pt-p]=stk[top],par[stk[top--]]=pt-p;
	}
	int ans=search(1,pt-p-1,td);
	if(ans==-1)printf("impossible");else printf("%d",ans>>1);
}