洛谷P5658 [CSP-S 2019] 括号树一题的题解

注意到有两个fi=i-1,也就是说他爹必在它前一个位置，即这棵树退化成一条链，直接暴力枚举所有情况再写一个check函数用来检查子串是否合法。
顺带提一嘴，检查方法为：用一个栈从头到脚依次压入字符，当出现“）”时弹出栈顶元素，看是否匹配。

#include<bits/stdc++.h>usingnamespacestd;intn,f[500005],ans=0;intm;string s;boolcheck(inti,intj){stack<char>st;for(intl=i;l<=j;l++){if(s[l]=='(')st.push('(');else{if(st.empty())returnfalse;st.pop();}}returnst.empty();}intmain(){cin>>n;cin>>s;s=" "+s;for(inti=1;i<n;i++){cin>>f[i];//这玩意儿目前还没用}for(inti=1;i<=n;i++){ans=0;for(intl=1;l<=n;l++){for(intr=l;r<=i;r++)if(check(l,r)){ans++;}}m^=(i*ans);}cout<<m;return0;}

但是这个方法只能得20分对我来说足够了，说明超时了，我们应当考虑优化算法。因为树已经退化成了链式结构，我们可以想想用dp。
咋个用呢？如果当前字符是’('，直接将序号入栈；如果当前字符是 ‘)’：
1.栈为空，说明无法匹配，dp[i]=0；
2.栈不为空，弹出匹配的左括号位置 pos，匹配一对 ()，同时 pos 左侧连续的合法括号串可以拼接进来。

#include<bits/stdc++.h>usingnamespacestd;longlongn,f[500005],dp[500005],pos,ans,sum;longlongm;string s;intmain(){cin>>n;cin>>s;s=" "+s;for(longlongi=1;i<n;i++){cin>>f[i];//这玩意儿目前还没用}stack<longlong>st;for(longlongi=1;i<=n;i++){if(s[i]=='('){st.push(i);}else{if(!st.empty()){pos=st.top();st.pop();dp[i]=dp[pos-1]+1;}}}for(longlongi=1;i<=n;i++){sum+=dp[i];ans^=(sum*i);}cout<<ans;return0;}

然而还是只有55分。考虑把第一段和第二段结合一下，满足链式结构时用dp，不满足时用个暴力深搜，能多骗一些是一些。

#include<bits/stdc++.h>usingnamespacestd;intn,m;string s;vector<int>G[100005];charval[100005];boolcheck(string t){stack<int>st;for(intl=0;l<t.size();l++){if(t[l]=='(')st.push('(');else{if(st.empty())returnfalse;st.pop();}}returnst.empty();}longlongxdp(){vector<longlong>dp(n+1,0);vector<int>st;longlongsum=0,ans=0;for(inti=1;i<=n;i++){if(s[i-1]=='('){st.push_back(i);dp[i]=0;}else{if(!st.empty()){intpost=st.back();st.pop_back();dp[i]=dp[post-1]+1;}else{dp[i]=0;}}sum+=dp[i];ans^=(1LL*i*sum);}returnans;}longlongdfs(intu,string path){path.push_back(val[u]);intL=path.size();intk=0;for(intl=0;l<L;l++){for(intr=l;r<L;r++){string sub=path.substr(l,r-l+1);if(check(sub))k++;}}longlongans=1LL*u*k;for(inti=0;i<G[u].size();i++){intv=G[u][i];ans^=dfs(v,path);}returnans;}intmain(){cin>>n;cin>>s;for(inti=0;i<n;i++){val[i+1]=s[i];}boolisf=true;vector<int>f(n+1);for(inti=2;i<=n;i++){intx;cin>>x;f[i]=x;if(f[i]!=i-1)isf=false;G[f[i]].push_back(i);}longlongans;if(isf){ans=xdp();}else{ans=dfs(1,"");}cout<<ans;return0;}

这样就可以再多15分了。
但最后还是得写满分代码不然写这题解没意义。可以把dp迁移到树上，dp[u]=dp[f[m]]+1。

#include<bits/stdc++.h>usingnamespacestd;longlongn,sum=0,ans=0;string s;vector<longlong>G[500005];longlongf[500005];longlongdp[500005];vector<longlong>st;voiddfs(longlongu){longlongoldsum=sum;longlongm=-1;if(s[u-1]=='('){st.push_back(u);dp[u]=0;}else{if(!st.empty()){m=st.back();st.pop_back();dp[u]=dp[f[m]]+1;}else{dp[u]=0;}}sum+=dp[u];ans^=(1LL*u*sum);for(longlongi=0;i<(longlong)G[u].size();i++){dfs(G[u][i]);}sum=oldsum;if(s[u-1]=='('){st.pop_back();}else{if(m!=-1){st.push_back(m);}}}intmain(){cin>>n;cin>>s;f[1]=0;for(inti=2;i<=n;i++){cin>>f[i];G[f[i]].push_back(i);}dfs(1);cout<<ans;return0;}