P5658 括号树

题解

太菜了啥都不会写只能水5分数据

啥都不会写只能翻题解题解大大我错了

我们手动找一下规律

我们设 w[ i ] 为从根节点到结点 i 对答案的贡献，也就是走到结点 i ，合法括号串又多了几个

sum[ i ] 为从根节点到结点 i 总共合法括号串数

（）（）（）

w[i] 依次为 0 1 0 2 0 3

sum[i] 依次为 0 1 1 3 3 6

（））（）

w[i] 依次为 0 1 0 0 1

sum[i] 依次为 0 1 1 1 2

（）（（））

w[i] 依次为 0 1 0 0 1 2

sum[i] 依次为 0 1 1 1 2 4

然后我们惊奇的发现 sum[i] 是 w[i] 的前缀和

最后要求的其实就是所有的 sum[i]*i 的异或和，所以当务之急只找到求解 w[ i ] 的方法

（1）发现如果 s[i] 是个左括号，那么显然不会有新的贡献出现，也就是w[i]=0

（2）如果 s[i] 是个右括号，那么我们找到他对应上一个右括号，贡献值也就是上一个右括号的贡献值+1：其实也就相当于，对于当前右括号，（如果条件允许）他有左括号与之匹配，对答案贡献为1，然鹅当前右括号对应的前一个右括号，他本就会对答案有一定的贡献，加上当前新匹配的一对括号，就生成新的匹配括号串，那么我们就将它作为当前右括号的贡献存下

举个栗子：（）（）（））（）

w[4]=2

s[5]是左括号，那么w[5]=0，因为考虑了s[5]也没有出现新的匹配括号

s[6]是一个可以匹配的右括号，那么，s[5]与s[6]构成一个新的匹配括号，s[3]~s[6]以及s[1]~s[6]都是新匹配的括号，他们都是原来w[4]的基础上又加了新的s[5]s[6]构成的新括号串

s[7]没有左括号与之匹配，所以w[7]=0

s[9]由于上一个右括号是s[7]，它与时代脱节，所以s[9]只能将自成一家的括号串作为贡献，因为既然中间断开了就不会有在原来基础上+()生成新括号串的可能了

采用dfs递归沿着树更新结点对应的值

代码

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<string>

#include<cstring>

#include<queue>

using namespace std;

typedef long long ll;

inline int read()

{

    int ans=;

    char last=' ',ch=getchar();

    while(ch<''||ch>'') last=ch,ch=getchar();

    while(ch>=''&&ch<='') ans=ans*+ch-'',ch=getchar();

    if(last=='-') ans=-ans;

    return ans;

}

const int maxn=5e5+;

ll n,ans=;

char s[maxn];

ll fa[maxn];

ll pre[maxn],w[maxn];

ll cnt=,head[maxn],to[maxn<<],nxt[maxn<<];

void addedge(int u,int v)

{

    to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;

}

void dfs(int u)

{

    pre[u]=pre[fa[u]];

    if(s[u]=='(') pre[u]=u;

    else if(pre[u]){

        w[u]=w[fa[pre[u]]]+,pre[u]=pre[fa[pre[u]]];

    }

    for(int i=head[u];i;i=nxt[i]) dfs(to[i]);

}

int main()

{

    n=read();

    scanf("%s",s+);

    for(int i=;i<=n;i++){

        fa[i]=read();

        addedge(fa[i],i);

    }

    dfs();

    ans=w[];

    for(int i=;i<=n;i++){

        w[i]+=w[fa[i]];

        ans^=(i*w[i]);

    }

    printf("%lld\n",ans);

    return ;

}

-------------------------

CSP 2019 D1T2

巴特西

P5658 括号树

P5658 括号树

题解

代码

最新文章

热门文章