题目大意
给定一个由大小写字母(变量),|
和 ~
组成的布尔代数式,变量可以任意赋值为 True
或 False
。求对于给定的变量,有多少种赋值方案使得给定的代数式值为 True
。
思路
一个一个看,首先考虑 |
,先假设只有 |
,则当代数式中有一个变量为 True
时,代数式的值变为 True
。因为每一个变量有两种取值,总的方案数便为 \(2^n\) 个,但当所有变量都为 False
时,代数式值为 False
,所以方案数要减一,为 \(2^n-1\)。
再把 ~x
加进来,若只有 ~x
或 x
,就相当于一个单独变量,与上面的结果相同,若既有 ~x
又有 x
,不妨将他们放一起变为 ~x|x
,这个式子的结果恒为 \(1\),所以方案数为 \(2^n\)。
实现
用 map
记录变量的出现情况,若既有 x
又有 ~x
,结果为 \(2^n\),否则为 \(2^n -1\)。
代码
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
map<char,int>a,b,c;//a:是否有变量x,b:是否有~x,m2:是否有x
string s;
signed main()
{
int n=0;
bool f=false;//是否有x|~x
string s;
cin>>s;
for(int i=0;i<s.size();i++)
if((s[i]<='z'&&s[i]>='a')||(s[i]<='Z' && s[i]>='A'))
{
if(s[i-1]!='~')c[s[i]]=1;
else if(s[i-1]=='~')b[s[i]]=1;
if(a[s[i]]==0)n++,a[s[i]]=1;
if(c[s[i]]==1&&b[s[i]]==1)
f=true;
}
cout<<(int)pow(2,n)-(!f);//pow的返回有坑,要转int QWQ
return 0;
}
本文章同步发表于洛谷上。
标签:P7020,NWRRC2017,False,变量,代数式,int,题解,给定,True From: https://www.cnblogs.com/GCSG01/p/18373846