社区讨论

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 条回复,欢迎继续交流。

正在加载回复...