题解：P7020 [NWRRC2017] Boolean Satisfiability

GCSG01 · 2024-07-26 09:19:52 · 题解

题目大意

给定一个由大小写字母（变量），| 和 ~ 组成的布尔代数式，变量可以任意赋值为 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;
}