为什么 TLE 50pts
查看原帖
为什么 TLE 50pts
872386
Officer楼主2024/9/22 20:24
#include<bits/stdc++.h>
#define int long long
using namespace std;
char s[1000005],a[1000005];
stack<char> op;
stack<int> num;
int cnt,sum,sum1,sum2;
int G[1000005][2];
void work()
{
	a[cnt]=op.top();
	op.pop();
	G[cnt][1]=num.top();
	num.pop();
	G[cnt][0]=num.top();
	num.pop();
	num.push(cnt++);
}
int dfs(int now)
{
	if(a[now]=='1'||a[now]=='0')
	{
		return a[now]-'0';
	}
	if(a[now]=='&')
	{
		if(dfs(G[now][0])==0)
		{
			sum1++;
			return 0;
		}
		return dfs(G[now][1]);
	}
	if(a[now]=='|')
	{
		if(dfs(G[now][0])==1)
		{
			sum2++;
			return 1;
		}
		return dfs(G[now][1]);
	}
}
signed main()
{
	//freopen("string.in", "r", stdin);
	//freopen("string.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>s;
	for(int i=0;i<strlen(s);i++)
	{
		if(s[i]=='(')
		{
			op.push('(');
		}
		else if(s[i]==')')
		{
			while(op.top()!='(')
			{
				work();
			}
			op.pop();
		}
		else if(s[i]=='&')
		{
			while(op.size()&&op.top()=='&')
			{
				work();
			}
			op.push('&');
		}
		else if(s[i]=='|')
		{
			while(op.size()&&op.top()!='(')
			{
				work();
			}
			op.push('|');
		}
		else
		{
			a[cnt]=s[i];
			num.push(cnt++);
		}
	}
	while(op.size())
	{
		work();
	}
	sum=dfs(cnt-1);
	cout<<sum<<endl<<sum1<<" "<<sum2<<endl;
	return 0;
}
/*
*/

2024/9/22 20:24
加载中...