P2131 彩球树 题解

· · 题解

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

考虑如何让一个应该有 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);
}