萌新求助
查看原帖
萌新求助
204705
KiDDOwithTopTree楼主2020/11/8 15:48

谁来看看我的代码哪里错了,0pts(30pts解法)

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
using namespace std;
const int N=1e6+10;
struct Tree{
	int f,lsn,rsn;
	int ky,vl;
	bool fla;
};
Tree tr[N];
int sta[N],w[N];
string s;
int t,tp;
void build(){
	int l=s.size();
	for(int i=0;i<l;i++){
		if(s[i]=='x'){
			i++;
			t++;
			while(s[i]<='9'&&s[i]>='0'){
				tr[t].ky=tr[t].ky*10+int(s[i]-'0');
				i++;
			}
			tr[t].fla=true;
		}
		else{
			t++;
			if(s[i]=='&')
				tr[t].ky=-1;
			else if(s[i]=='|')
				tr[t].ky=-2;
			else
				tr[t].ky=-3;
			i++;
			tr[t].fla=false;
		}
	}
	for(int i=1;i<=t;i++){
		if(tr[i].fla)
			sta[++tp]=i;
		else
			if(tr[i].ky==-1||tr[i].ky==-2){
				tr[i].rsn=sta[tp--];
				tr[i].lsn=sta[tp--];
				tr[i].fla=true;
				sta[++tp]=i;
			}
			else if(tr[i].ky==-3){
				tr[i].lsn=sta[tp--];
				tr[i].fla=true;
				sta[++tp]=i;
			}
		w[tr[i].ky]=i;
	}
}
void Pushup(int p){
	if(tr[p].ky==-1)
		tr[p].vl=tr[tr[p].lsn].vl&tr[tr[p].rsn].vl;
	else if(tr[p].ky==-2)
		tr[p].vl=tr[tr[p].lsn].vl|tr[tr[p].rsn].vl;
	else
		tr[p].vl=!tr[tr[p].lsn].vl;
}
void dfs(int f,int p){
	tr[p].f=f;
	if(!tr[p].lsn&&!tr[p].rsn)
		return ;
	if(tr[p].lsn)
		dfs(p,tr[p].lsn);
	if(tr[p].rsn)
		dfs(p,tr[p].rsn);
	Pushup(p);
}
void Modify(int p){
	while(tr[p].f){
		p=tr[p].f;
		Pushup(p);
	}
}
int main(){
//	freopen("expr.in","r",stdin);
//	freopen("expr.out","w",stdout);
	getline(cin,s);
	build();
	int n;
	cin>>n;
	int x;
	for(int i=1;i<=n;i++){
		cin>>x;
		tr[w[i]].vl=x;
	}
	dfs(0,t);
	int q;
	cin>>q;
	for(int i=1;i<=q;i++){
		cin>>x;
		x=w[x];
		tr[x].vl=!tr[x].vl;
		Modify(x);
		cout<<tr[t].vl<<'\n';
		tr[x].vl=!tr[x].vl;
		Modify(x);
	}
}
2020/11/8 15:48
加载中...