首页 > 其他分享 >题解:P7020 [NWRRC2017] Boolean Satisfiability

题解:P7020 [NWRRC2017] Boolean Satisfiability

时间:2024-08-22 14:50:36浏览次数:10  
标签:P7020 NWRRC2017 False 变量 代数式 int 题解 给定 True

题目传送门

题目大意

给定一个由大小写字母(变量),|~ 组成的布尔代数式,变量可以任意赋值为 TrueFalse。求对于给定的变量,有多少种赋值方案使得给定的代数式值为 True

思路

一个一个看,首先考虑 |,先假设只有 |,则当代数式中有一个变量为 True 时,代数式的值变为 True。因为每一个变量有两种取值,总的方案数便为 \(2^n\) 个,但当所有变量都为 False 时,代数式值为 False,所以方案数要减一,为 \(2^n-1\)。
再把 ~x 加进来,若只有 ~xx,就相当于一个单独变量,与上面的结果相同,若既有 ~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

相关文章

  • 题解:P9788 [ROIR 2020 Day2] 区域规划
    题目传送门思路首先我们看下数据范围,$n<=3000$,范围很小,所以暴力枚举。于是第一份代码出来了。#include<bits/stdc++.h>usingnamespacestd;ints,a,b,c,d,n,m;intmain(){ ios::sync_with_stdio(false); cin.tie(),cout.tie(); cin>>n>>m; for(a=1;a<=n;a++) {......
  • 题解:P9784 [ROIR 2020 Day1] 超速
    传送门思路我们设\(T\)为所花的总时间,\(d\)为超速多少。然后不难知道$T=\sum_{i=1}^{n}\frac{l_i}{v_i+d}$,所以我们实际上是要找到符合条件最小的\(d\)。再结合题目所说最高被罚款的金额最少,然后二分枚举答案即可。时间复杂度\(O(nq\log(m))\)。AC代码#include......
  • 题解:P10892 SDOI2024
    题解:P10892SDOI2024题目传送门题目思路通过阅读题面,我们可以看出,其实对于每一次纠结,如果交出了\(\frac{n-1}{2}\)只猫猫,则剩下的为\(\frac{n+1}{2}\)只猫猫;如果交出了\(\frac{n+1}{2}\)只猫猫,则剩下的为\(\frac{n-1}{2}\)只猫猫。为了使纠结的次数尽可能小,我们要交出......
  • 启动应用程序出现pspluginwkr.dll找不到问题解决
    其实很多用户玩单机游戏或者安装软件的时候就出现过这种问题,如果是新手第一时间会认为是软件或游戏出错了,其实并不是这样,其主要原因就是你电脑系统的该dll文件丢失了或没有安装一些系统软件平台所需要的动态链接库,这时你可以下载这个pspluginwkr.dll文件(挑选合适的版本文件)把......
  • 启动应用程序出现ptpprov.dll找不到问题解决
    其实很多用户玩单机游戏或者安装软件的时候就出现过这种问题,如果是新手第一时间会认为是软件或游戏出错了,其实并不是这样,其主要原因就是你电脑系统的该dll文件丢失了或没有安装一些系统软件平台所需要的动态链接库,这时你可以下载这个ptpprov.dll文件(挑选合适的版本文件)把它放......
  • 洛谷 P2590 [ZJOI2008] 树的统计 题解
    题目大意给你一个\(N\),然后再给你两个长度为\(N\)的序列。让你构造一个仅有\(0\)和\(1\)的\(N\timesN\)的正方形,但是要满足两个序列的顺序:第一个序列指的是该正方形每一行所构成的二进制数的大小顺序。第二个序列指的是该正方形每一列所构成的二进制数的大小顺序。......
  • [ARC181C] Row and Column Order 题解
    题目大意给你一个\(N\),然后再给你两个长度为\(N\)的序列。让你构造一个仅有\(0\)和\(1\)的\(N\timesN\)的正方形,但是要满足两个序列的顺序:第一个序列指的是该正方形每一行所构成的二进制数的大小顺序。第二个序列指的是该正方形每一列所构成的二进制数的大小顺序。......
  • 题解:AT_abc352_e [ABC352E] Clique Connect
    [题目通道]([ABC352E]CliqueConnect-洛谷)鄙人今日写人生第一篇题解希望管理大大通过首先,我们先看题:它说一共有n个点,m回操作。。。每次操作都有一个Ki和CiKi代表有Ki个点,Ci代表每条边所赋的边权一看就知道这是个最小生成树的板子我使用了著名的kruskal话......
  • P10892 题解
    思路考虑贪心策略。当剩下的猫猫数量为偶数的时候,直接取出\(\large\frac{n}{2}\)只猫猫即可。否则当剩下的猫猫数量为奇数的时候,则要尽可能保持第二天猫猫的数量为偶数。则要考虑\(n-\large\frac{n-1}{2}\)和\(n-\large\frac{n+1}{2}\)哪个是偶数。第二条化简一下就......
  • AGC003 题解
    目录A-WannagobackhomeB-SimplifiedmajhongA-Wannagobackhome注意到横纵坐标是独立的,因此可以分开考虑。考虑横坐标或纵坐标最终为零的充要条件为:没有出现任何关于它的任何操作(没有N和S,或没有W和E);出现所有关于它的任何操作(有向正方向走与往负方向走,如有......