社区讨论
WA19个点,求助大佬,已写注释,悬关
P5658[CSP-S 2019] 括号树参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mhk7dy4l
- 此快照首次捕获于
- 2025/11/04 14:44 4 个月前
- 此快照最后确认于
- 2025/11/04 14:44 4 个月前
CPP
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
#define maxn 500010
inline int read(){
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int n;
int wym=0;//记录答案
//"^"
vector<int>t[maxn];
struct node{
int val,cntl,cnty,ans;
};//记录该节点左右括号以及路径上左右括号数量
node ch[maxn];
void solve(int id){
wym=wym^(id*ch[id].ans);//异或一下并记录
cout<<wym<<endl;//调试
for(int i=0;i<t[id].size();++i){
int j=t[id][i];//遍历子节点
if(ch[j].val==1){
ch[j].cnty=ch[id].cnty+1;//路径上左括号加一
ch[j].cntl=ch[id].cntl;
ch[j].ans=ch[id].ans;
//如果是左括号,不闭合,答案等于它的父节点
}
else{
ch[j].cnty=ch[id].cnty;
ch[j].cntl=ch[id].cntl+1;
ch[j].ans=ch[id].ans+ch[id].cnty;
//若是右括号,那么答案还需要多可以闭合的新增数量
}
cout<<j<<" "<<ch[j].cnty<<" "<<ch[j].cntl<<" "<<ch[j].ans<<endl;//调试
solve(j);//走子节点
}
return;
}
/*
8
)())((()
1 2 3 4 5 6 7
19
*/
int main(){
n=read();
string s;
cin>>s;
ch[1].cnty=0;ch[1].cntl=0;ch[1].ans=0;
if(s[0]==')') ch[1].val=0,ch[1].cntl++;
else ch[1].val=1,ch[1].cntl++;
//初始化
for(int i=2;i<=n;++i){
int a;
a=read();
t[a].push_back(i);
if(s[i-1]==')') ch[i].val=0;
else ch[i].val=1;
//每一个节点初始化
}
solve(1);
cout<<wym<<endl;
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...