悬赏关注,求助!0 分 WA
查看原帖
悬赏关注,求助!0 分 WA
494699
卷王慢即快楼主2023/5/4 21:02

rt。我很弱,请大佬指教。

感觉应该很好查到错误,但是就是照不出来。

感觉问题出在 tt 数组上,或者是在建表达式树那块。

找出来的人直接给我的关注和我小号的关注。

#include <bits/stdc++.h>
using namespace std;

inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
//读入 √ 
//化简后缀 √ 
//后缀转表达式树 √
//表达式树求值 √ 


struct node { //表达式树的一个节点 
	node *le, *ri;
	int val;
	char op; //是数字,则是 '*',否则正常存入 
	
	node(char _op) {
		if(_op >= '0' && _op <= '1') {
			op = '*';
			val = _op - '0';
		}
		else op = _op;
	}
};

string ori;
int n, q, cnt = 0;
int a[100007];
int t[100007]; //t[i] 记录后缀里第 i 个数字的位置 
vector<char> fin;

inline void simp_suffix() {
	for(int i = 0; i < ori.size(); i++) {
		char ch = ori[i];
		if(ch == ' ') continue;
		
		//下面 ch 只会是变量、|、&、! 
		//如果是变量,则一下搜到是空格为止,并记录数字 
		//如果是 |、! 或者 & 直接加入 
		
		if(ch == '|' || ch == '&' || ch == '!') {
			fin.push_back(ch);
			continue;
		}
		
		int num = 0;
		while(i < ori.size() && ((ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9'))) {
			if(isdigit(ch)) num = num * 10 + (ch - '0');
			ch = ori[++i];
		}
		
		//cout<<num<<" "<<a[num]<<endl;
		fin.push_back(a[num] + '0');
		t[num] = fin.size() - 1;
	}
//	for(auto ch: fin)
//		cout << ch;
//	cout << endl; 
}

inline void init() {
	getline(cin, ori); //读入原来的字符串 
	n = read();
	for(int i = 1; i <= n; i++)
		a[i] = read();
	//cout << ori << endl;
	simp_suffix();
	q = read();
}

node *root;

inline void build_tree() { //通过后缀表达式,转成表达式树 
	stack<node*> ds;
	for(auto ch: fin) {
		//处理后缀表达式 
		if(ch >= '0' && ch <= '1') {
			ds.push(new node(ch));
			continue;
		}
		
		if(ch == '!') {
			node *tmp = new node(ch);
			node *le = ds.top(); ds.pop();
			tmp -> le = le;
			ds.push(tmp);
			continue;
		}
		
		node *tmp = new node(ch);
		node *ri = ds.top(); ds.pop();
		node *le = ds.top(); ds.pop();
		tmp -> le = le;
		tmp -> ri = ri;
		
		ds.push(tmp);
	}
	root = ds.top();
}

inline int etree_count(node *x) {
	if(x -> op == '*') return x -> val;
	int l = etree_count(x -> le);
	if(x -> op == '|' && x -> val == 1) return 1;
	if(x -> op == '&' && x -> val == 0) return 0;
	if(x -> op == '!') return !l;
	int r = etree_count(x -> ri);
	if(x -> op == '|') return l || r;
	else return l && r;
}

inline void work() {
	while(q--) {
		int x = read();
		a[x] = !a[x];
		if(fin[t[x]] == '0') fin[t[x]] = '1';
		else fin[t[x]] = '0'; //临时调换 
		
		//此时后缀表达式已经更新完成 
		//开始建表达式树并求值 
		//主要分为两步: 
		// * 后缀转表达式树 
		// * 表达式树求值 
		
		build_tree();
		cout << etree_count(root) << "\n";
		
		a[x] = !a[x]; //还原 
		if(fin[t[x]] == '0') fin[t[x]] = '1';
		else fin[t[x]] = '0';
	}
}

int main() {
	init();
	work();
	return 0;
}
2023/5/4 21:02
加载中...