20分求助
查看原帖
20分求助
643323
weirdoX楼主2022/10/30 14:22
#include <bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i = (int)l;i <= (int)r;i++)
#define per(i,r,l) for(int i = (int)r;i >= (int)l;i--)
#define pb push_back
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define mp make_pair
#define SZ(a) (int)(a.size())
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef long long ll;
typedef double db;

const int N = 1e6 + 10,INF = 1e9,mod = INF + 7;
struct Tr{
	char c;
	int l, r;
}tr[N];
int n, ans1, ans2;
char s[N];
string h = " ";
stack<char> opt, st;

inline bool dfs(int now){
	if(tr[now].c == '0' || tr[now].c == '1')
		return tr[now].c - '0';
	int l = tr[now].l, r = tr[now].r;
	if(tr[now].c == '&'){
		bool a = dfs(l);
		if(!a){
			ans1++;
			return false;
		}
		bool b = dfs(r);
		return a & b;
	}else{
		bool a = dfs(l);
		if(a){
			ans2++;
			return true;
		}
		bool b = dfs(r);
		return a | b;
	}
}
int main()
{
	// freopen("expr4.in", "r", stdin);
	scanf("%s", s + 1);
	n = strlen(s + 1);
	rep(i,1,n){
		if(s[i] == '0' || s[i] == '1')
			h += s[i];
		else if(s[i] == '&'){
			while(!opt.empty() && opt.top() == '&'){
				h += opt.top();
				opt.pop();
			}
			opt.push(s[i]);
		}else if(s[i] == '|'){
			while(!opt.empty() && (opt.top() == '|' || opt.top() == '&')){
				h += opt.top();
				opt.pop();
			}
			opt.push(s[i]);
		}else if(s[i] == '('){
			opt.push(s[i]);
		}else {
			while(!opt.empty() && opt.top() != '('){
				h += opt.top();
				opt.pop();
			}
			opt.pop();
		}
	}
	while(!opt.empty())
		h += opt.top(), opt.pop();
	n = SZ(h) - 1;
	rep(i,1,n){
		if(h[i] == '0' || h[i] == '1'){
			tr[i] = (Tr){h[i], 0, 0};
			st.push(i);
		}else{
			int b = st.top();st.pop();
			int a = st.top();st.pop();
			tr[i] = (Tr){h[i], a, b};
			st.push(i);
		}
	}
	printf("%d\n", dfs(st.top()));
	printf("%d %d\n", ans1, ans2);
	return 0;
}
2022/10/30 14:22
加载中...