50分求调
查看原帖
50分求调
481337
Pratty楼主2023/9/29 20:52
#include <bits/stdc++.h>
using namespace std;
const int N = 1100000;
stack<int> st;
stack<char> op;
stack<pair<int, int> > ans;
char s[N];
bool prior(char a, char b) {
	if (b == '|') return a != '(';
	else return a == '&';
}
int calc(int a, int b, char c) {
	if (c == '|') {
		return a | b;
	} else {
		return a & b;
	}
}
void slove(int a, int b, char c) {
	pair<int, int> a2 = ans.top();
	ans.pop();
	pair<int, int> a1 = ans.top();
	ans.pop();
	if (c == '|') {
		if (a == 0) {
			pair<int, int> sum = make_pair(a1.first + a2.first, a1.second + a2.second);
			ans.push(sum);
		} else {
			pair<int, int> sum = make_pair(a1.first, a1.second + 1);
			ans.push(sum);
		}
	} else {
		if (a == 1) {
			pair<int, int> sum = make_pair(a1.first + a2.first, a1.second + a2.second);
			ans.push(sum);
		} else {
			pair<int, int> sum = make_pair(a1.first + 1, a1.second);
			ans.push(sum);
		}
	}
}
void go() {
	while (!op.empty() && op.top() != '(') {
		int t1 = st.top();
		st.pop();
		int t2 = st.top();
		st.pop();
		char ch = op.top();
		op.pop();
		st.push(calc(t2, t1, ch));
		slove(t2, t1, ch);
	}
	if (!op.empty()) op.pop();
}
int main() {
	scanf("%s", s + 1);
	for (int i = 1; i <= strlen(s + 1); i++) {
		if (s[i] >= '0' && s[i] <= '9') {
			st.push(s[i] - '0');
			ans.push(make_pair(0, 0));
		} else if (s[i] == '|' || s[i] == '&') {
			while (!op.empty() && prior(op.top(), s[i])) {
				int t1 = st.top();
				st.pop();
				int t2 = st.top();
				st.pop();
				char ch = op.top();
				op.pop();
				st.push(calc(t2, t1, ch));
				slove(t2, t1, ch);
			}
			op.push(s[i]);
		} else if (s[i] == '(') {
			op.push(s[i]);
		} else {
			go();
		}
	}
	go();
	printf("%d\n%d %d", st.top(), ans.top().first, ans.top().second);
	return 0;
}

AC\texttt{AC} 一半,TLE\texttt{TLE} 一半。

2023/9/29 20:52
加载中...