比赛 CSP2022普及组 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 逻辑表达式 最终得分 100
用户昵称 CCF_NOI 运行时间 0.105 s
代码语言 C++ 内存使用 9.55 MiB
提交时间 2022-10-29 16:39:39
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=1000000+5;
bool opt[130][130];
int n,len=0;
char s[N],ex[N]; 
int st[N],tp=0;
int pos[N],w[N];
void init(){
	opt['&']['&']=1;opt['&']['|']=0;opt['&']['(']=0;
	opt['|']['&']=1;opt['|']['|']=1;opt['|']['(']=0;
	return ;
}
int main(){
	freopen ("csp2022pj_expr.in","r",stdin);
	freopen ("csp2022pj_expr.out","w",stdout);
	scanf("%s",s+1);
	n=strlen(s+1);
	init();
	for (int i=1;i<=n;i++){
		if (isdigit(s[i]))ex[++len]=s[i];
		else{
			if (s[i]=='(')st[++tp]=s[i];
			else if (s[i]==')'){
				while(tp>=0&&st[tp]!='('){
					ex[++len]=st[tp--];
				}
				tp--;
			}
			else{
				while(tp>=0&&opt[s[i]][st[tp]]){
					ex[++len]=st[tp--];
				}
				st[++tp]=s[i];
			}
		}
		
	}
	while(tp>=0){
		ex[++len]=st[tp--];
	}
	for (int i=1;i<=len;i++){
		if (isdigit(ex[i]))st[++tp]=i;
		else{
			pos[st[tp-1]]=i;
			tp-=2;
			st[++tp]=i;
		}
	}
	tp=0;
	int ans1=0,ans2=0;
	for (int i=1;i<=len;i++){
		if (isdigit(ex[i]))st[++tp]=i,w[i]=ex[i]-'0';
		else{
			int now=0;
			if (ex[i]=='&')now=w[st[tp]]&w[st[tp-1]];
			else now=w[st[tp]]|w[st[tp-1]];
			tp-=2;
			st[++tp]=i;w[i]=now;
		}
		while(true){
			if (w[i]==1&&ex[pos[i]]=='|'){
				ans2++;i=pos[i];w[i]=1;
			}
			else if (w[i]==0&&ex[pos[i]]=='&'){
				ans1++;i=pos[i];w[i]=0;
			}
			else break;
		}
	}
	printf("%d\n%d %d\n",w[len],ans1,ans2);
	return 0;
}