[ZOJ4021]Boolean Expression

Zarxdy34 posted @ 2018年4月08日 15:05 in ZOJ with tags , 21630 阅读

        题目大意:给出一个布尔表达式S(只含'!','&','|','T','F','(',')'),要求加上最少的字符使表达式的值为真。(\(|S| \leq 10^5\))

        题解:原表达式为真时答案就是0了,原表达式为假时由于可以在表达式最后加上'|T'使表达式值为真,所以答案一定小于等于2,如果只加一个字符的话显然只能加'!',所以当原表达式为假时,这道题目可以转化为是否能在某一括号或'T'、'F'前面加上一个'!'使得原表达式值为真。这样一来我们可以这么考虑:原来每一子表达式的值只有0和1(表示假和真),我们将它改成值为0,1,2,3,其中0表示假,1表示真,2表示原式为假,但可以通过加上一个'!'后变成真,3表示原式为真,但可以通过加上一个'!'后变成假。然后我们可以通过重新定义运算来计算表达式的值。这里由于表达式的值并非只和运算符左右的值有关,而是和连着的整段相同运算符所组成的表达式有关,所以当前运算符和栈顶运算符相同时不能直接弹出,要等到下一个优先级更小的运算符出现时才能开始处理。

        另外,由于'!'加在括号里面的作用不如加在括号前面,所以可以先把括号里的值先算出来,然后把整个表达式改成只有'&'和'|'的表达式,会更容易处理。(我代码里没有写)

 

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;

char s[maxn];
char qc[maxn];
int pri[256];
int qx[maxn];
int qcn,qxn;
int n;

int And(int x,int y) {return x&y&1;}
int Or(int x,int y) {return (x|y)&1;}

void Calc()
{
	int cnt[4];
	memset(cnt,0,sizeof(cnt));
	char ch=qc[qcn];
	cnt[qx[qxn]]=1;
	while (qcn && qc[qcn]==ch)
	{
		int x=qx[qxn],y=qx[qxn-1];
		cnt[qx[qxn-1]]++;
		qxn-=2;
		if (ch=='&') qx[++qxn]=And(x,y);
		if (ch=='|') qx[++qxn]=Or(x,y);
		qcn--;
	}
	if (ch=='&' && cnt[0]==0 && cnt[2]==1) qx[qxn]|=2;
	else if (ch=='&' && qx[qxn]==1 && cnt[3]) qx[qxn]|=2;
	else if (ch=='|' && cnt[1]==0 && cnt[2]==1) qx[qxn]|=2;
	else if (ch=='|' && qx[qxn]==0 && cnt[2]) qx[qxn]|=2;
}

int main()
{
	pri['!']=1;
	pri['&']=2;
	pri['|']=3;
	pri[')']=pri['(']=4;
	int T;
	scanf("%d",&T);
	while (T--)
	{
		scanf("%s",s);
		n=strlen(s);
		qcn=qxn=0;
		for (int i=0;i<n;i++)
		{
			if (s[i]=='F' || s[i]=='T')
			{
				qx[++qxn]=(s[i]=='T')+2;
				while (qcn && qc[qcn]=='!') qx[qxn]^=1,qcn--;
			}
			else if (s[i]!='(')
			{
				while (qcn && pri[s[i]]>pri[qc[qcn]])
					Calc();
				qc[++qcn]=s[i];
				if (s[i]==')')
				{
					qcn-=2;
					qx[qxn]|=2;
					while (qcn && qc[qcn]=='!') qx[qxn]^=1,qcn--;
				}
			}
			else qc[++qcn]=s[i];
		}
		while (qcn) Calc();
		if (qx[1]==1 || qx[1]==3) printf("0\n");
		else if (qx[1]==2) printf("1\n");
		else printf("2\n"); 
	}
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter