自动搬运

查看原文

来自洛谷，原作者为

	GCSG01 我们都有光明的未来||Mahiro & Oyama||https://gridspech.baublejar.com/

搬运于2025-08-24 22:25:56，当前版本为作者最后更新于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;
}