首页 > 其他分享 >Gym100078F Formula

Gym100078F Formula

时间:2023-10-13 15:35:08浏览次数:37  
标签:return 变量 int Gym100078F 真值表 Formula calc op

非常好,竟然是有思维的模拟题。换句话讲就是有模拟的思维题

题意:给定一个由与或非组成的逻辑表达式,你需要把他化简成一个变量不重复的与或非逻辑表达式或报告无解。

发现如果允许变量重复了,这个逻辑表达式没有什么性质,任何一种真值表都可以通过合适的构造得来。所以题目相当于直接告诉我们一个真值表。

变量重复时我们可以用 \(\neg a\lor a\) 制造常量,然后像全 0 全 1 这样的表达式也可以制造出来了。

然而如果变量不重,那么真值表将具有一些良好的性质:其中结果一定既有 0 又有 1。然而这个性质并不是充要的,比如这道题的第 4 个样例依然是无解。

只考虑二元运算符,我们发现与和或其实能力很有限,它们甚至不能组成异或门!(这也是第 4 个样例输出 No 的原因)这启示我们不能通过一些简单的判断有无解。

本题突破口在与变量数较少(只有 11 个),所以可以考虑搜索/状压 DP。

由于构造出的答案只考虑与和或时形成了一颗变量的二叉树,我们先考虑直接对这棵树进行搜索。具体地,我们维护一个变量集合及其对应的真值表,每次尝试将变量集合分成两半作为两颗子树,并对应地计算两边的真值表。

手玩一下发现,当钦定左边的集合取值固定的时候,我们以此时的真值为依据分裂右边的集合。当左边的集合取值变化后,分裂出的右边的集合必须要是一样的(前提是如果分裂出了两个集合)。因为与和或的性质,当左边取某个常量时,答案要么直接变成一个常量,要么完全取决于右边的取值。而我们上面讨论的真值表既有 0 又有 1 的性质保证了我们至少进行一次分裂(否则无解)。

然而这样搜复杂度没有保证,考虑记忆化(DP)。

这个时候真值表肯定是记忆化不下来了。我们考虑继续找一些性质:当递归到的变量集合确定时,其真值表是固定的!对于某一个变量集合,如果它能够作为最终逻辑表达式的一颗子树,那么它既有 0 又有 1,在它的补集取某些值时,这棵子树的取值总有一种可能会直接决定答案。所以说我们可以直接通过全局的真值表来分裂出这个变量集合的真值表。

当然这里的真值表实际上就是两个集合,跟具体的 01 没关系了,反正可以加个非。

所以直接记忆化搜索,跑得飞快,时间复杂度精细算一下大概是 \(O(5^k)\) 左右的,其中 \(k\) 是变量数最大为 \(11\),实测远远跑不满。(至于这个 5 咋来的大家可以自己思考,不排除笔者算错了的可能性)

#include <cctype>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cassert>
#include <cstring>
using namespace std;
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=(x<<1)+(x<<3)+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
const int N=100003;
typedef vector<int> vi;
bitset<2048> bs;
char str[N];int slen;
char var[14];int vnum,vmsk;
bitset<26> visvar,valvar;
int lc[N],rc[N],cnt;
char op[N];
int oprank(char c){
	if(c=='~') return 2;
	if(c=='&') return 1;
	if(c=='|') return 0;
	return -1;
}
int build(int l,int r){
	while(isspace(str[l])) ++l;
	while(isspace(str[r])) --r;
	int p=++cnt;
	if(l==r){op[p]=str[r];return p;}
	int x=-1,mn=3;
	for(int i=l,c=0;i<r;++i){
		if(str[i]==' '||isalpha(str[i])) continue;
		if(str[i]=='('){++c;continue;}
		if(str[i]==')'){--c;continue;}
		if(c) continue;
		if(isalpha(str[i])) continue;
		if(oprank(str[i])<mn){mn=oprank(str[i]);x=i;}
	}
	if(x<0&&str[l]=='('&&str[r]==')') return build(l+1,r-1);
	op[p]=str[x];
	if(op[p]!='~') lc[p]=build(l,x-1);
	rc[p]=build(x+1,r);
	return p;
}
void trav(int x){
	putchar('(');
	if(lc[x]) trav(lc[x]);
	putchar(op[x]);
	if(rc[x]) trav(rc[x]);
	putchar(')');
}
void showtable(){
	for(int s=0;s<(1<<vnum);++s){
		for(int i=0;i<vnum;++i)
			putchar((s>>i&1)^48);
		putchar(':');
		putchar(bs[s]^48);
		putchar('\n');
	}
}
bool calc(int x){
	if(isalpha(op[x])) return valvar[op[x]-97];
	if(op[x]=='&') return calc(lc[x])&&calc(rc[x]);
	if(op[x]=='|') return calc(lc[x])||calc(rc[x]);
	if(op[x]=='~') return !calc(rc[x]);
	__builtin_unreachable();
}
void analyse(){
	int rt=build(0,slen-1);
	for(int i=0;i<slen;++i)
		if(isalpha(str[i])){
			if(visvar[str[i]-97]) continue;
			visvar[str[i]-97]=1;
			var[vnum++]=str[i];
		}
	for(int s=0;s<(1<<vnum);++s){
		for(int i=0;i<vnum;++i) valvar[var[i]-97]=(s>>i&1);
		bs[s]=calc(rt);
	}
}
vi lis[2048];
bitset<2048> cv,ban;
bitset<2048> vis,res,slef,srig,sop;
int sp[2048];
vi vec[2048][2];
bool proc(int s){
	int _s=vmsk^s;
	for(int t=_s;;t=(t-1)&_s){
		lis[t].clear();
		if(!t) break;
	}
	for(int t=0;t<(1<<vnum);++t) lis[t&_s].emplace_back(t);
	bool fir=0;
	for(int t=_s;;t=(t-1)&_s){
		bool c[2]={0,0};
		for(int x:lis[t]) c[bs[x]]=1;
		if(!c[0]||!c[1]){
			if(!t) break;
			continue;
		}
		if(fir){
			c[0]=c[1]=0;
			for(int x:lis[t]) c[cv[x&s]^bs[x]]=1;
			if(c[0]&&c[1]) return 1;
		}
		else{
			for(int x:lis[t]) vec[s][bs[x]].emplace_back(x&s),cv[x&s]=bs[x];
			fir=1;
		}
		if(!t) break;
	}
	if(vec[s][0].empty()||vec[s][1].empty()) return 1;
	if(__builtin_popcount(s)==1u){
		if(vec[s][0].back()>vec[s][1].back()) vec[s][0].swap(vec[s][1]);
	}
	return !fir;
}
bool judge(int s){
	if(ban[s]) return 0;
	if(__builtin_popcount(s)==1u) return 1;
	if(vis[s]) return res[s];
	vis.set(s);cv.reset();
	for(int x:vec[s][1]) cv.set(x);
	for(int t=(s-1)&s;t>(s^t);t=(t-1)&s){
		int _t=s^t;
		if(ban[t]||ban[_t]) continue;
		sp[s]=t;
		bool fl=0;
		int cur=0;
		for(int a=0;a<2;++a){
			for(int b=0;b<2;++b){
				int c[2]={0,0};
				for(int x:vec[t][a])
					for(int y:vec[_t][b]) ++c[cv[x|y]];
				if(c[0]&&c[1]){fl=1;break;}
				cur=cur<<1|(!c[0]);
			}
			if(fl) break;
		}
		if(fl||!__builtin_parity(cur)) continue;
		if(judge(t)&&judge(_t)){
			switch(cur){
			case 7:  slef[s]=0;srig[s]=0;sop[s]=0;break;
			case 13: slef[s]=1;srig[s]=0;sop[s]=0;break;
			case 11: slef[s]=0;srig[s]=1;sop[s]=0;break;
			case 14: slef[s]=1;srig[s]=1;sop[s]=0;break;
			case 1:  slef[s]=0;srig[s]=0;sop[s]=1;break;
			case 4:  slef[s]=1;srig[s]=0;sop[s]=1;break;
			case 2:  slef[s]=0;srig[s]=1;sop[s]=1;break;
			case 8:  slef[s]=1;srig[s]=1;sop[s]=1;break;
			__builtin_unreachable();
			}
			return res[s]=1;
		}
	}
	return res[s]=0;
}
void output(int s){
	if(__builtin_popcount(s)==1u){
		putchar(var[__lg(s)]);
		return;
	}
	putchar('(');
	if(slef[s]) putchar('~');
	output(sp[s]);
	if(sop[s]) putchar('&');
	else putchar('|');
	if(srig[s]) putchar('~');
	output(s^sp[s]);
	putchar(')');
}
bool isuseless(int x){
	for(int s=0;s<(1<<vnum);++s)
		if(bs[s]!=bs[s^(1<<x)]) return 0;
	return 1;
}
int main(){
	freopen("formula.in","r",stdin);
	freopen("formula.out","w",stdout);
	assert(scanf("%[^\n]",str)==1);
	slen=strlen(str);
	analyse();vmsk=(1<<vnum)-1;
	for(int s=1;s<(1<<vnum);++s) ban[s]=proc(s);
	for(int i=0;i<vnum;++i) if(isuseless(i)) vmsk^=(1<<i);
	if(vnum==1){
		if(ban[1]) puts("No");
		else{
			puts("Yes");
			if(bs[0]) putchar('~');
			putchar(var[0]);
		}
		return 0;
	}
	if(judge(vmsk)){
		puts("Yes");
		output(vmsk);
	}
	else puts("No");
	return 0;
}

标签:return,变量,int,Gym100078F,真值表,Formula,calc,op
From: https://www.cnblogs.com/yyyyxh/p/formula.html

相关文章

  • PHP 导出 Excel 报错: Formula Error: An unexpected error occurred
    1.问题描述一个项目中用到了需要将用户手机号导出到Excel,最初写完测试是正常的,如下图所示 在后来的某一天,导出手机号突然出现了报错,如下图所示 通过提示我们将问题定位在了B列4867行。这是因为在excel中,单元格中的值如果是以“=”开头,则说明这个单元格是根据其......
  • 无涯教程-JavaScript - ISFORMULA函数
    描述如果对包含公式的单元格的引用,则ISFORMULA函数返回逻辑值TRUE。否则返回FALSE。语法ISFORMULA(reference)争论Argument描述Required/OptionalreferenceReferencecanbeacellreference,aformula,oranamethatreferstoacell.RequiredNotes如果引......
  • Interesting Formulas
    1:\(A^{log_BC}\)=\(C^{log_BA}\)可以把A看成\(B^x\),C看成\(B^y\),那么原式可以变成\((B^x)^{(log_BB^y)}\)=\((B^x)^y\)=\((B^y)^x\)=\((B^y)\)^(\(log_BB^x\))=\(C^{log_BA}\)2:\(\sumC_k^i(i∈[0,k])\)=\(2^k\)经典公式(?)3:三阶前缀和公式及推导:(非......
  • XL-Formula流式统计运算方式配置说明
    1、简介XL-Formula是一种用于描述流式统计运算方式的配置标准,它代表着一种通用型流式统计系统的实现方法,更深层次它代表着一种以通用型流式统计技术为切入点,低成本实现企业数据化运营的理念。该配置标准语法简洁、功能强大、解析效率高、便于理解和使用。XL-Formula涵盖了各种......
  • 曲线艺术编程 coding curves 第十二章 超级椭圆与超级方程(Superellipses and Superfor
    第十三章超级椭圆与超级方程(SuperellipsesandSuperformulas)原作:KeithPetershttps://www.bit-101.com/blog/2022/11/coding-curves/译者:池中物王二狗(sheldon)源码:github:https://github.com/willian12345/coding-curves曲线艺术编程系列第十三章在这一章我们将讨论......
  • The Importance of Particle Size Analysis in Preformulation Studies
    Thesizeoftheparticlesiscalledparticlesize.TheparticlesizeoftheAPIiscloselyrelatedtothehomogeneityofthepreparationprocessintermsofmixing,theaccuracyofdosage,andcompressibility,andithasanimpactonthesolubility,durat......
  • test3-with-formulas
    Advertisement:)pica-highqualityandfastimageresizeinbrowser.babelfish-developerfriendlyi18nwithpluralssupportandeasysyntax.Youwil......
  • MATH1851 Trigonometric Formula Notes
    大学里老师都默认我们学过正割\(\sec\),余割\(\csc\)与余切\(\cot\)再加上高中的一些公式都有点遗忘,开个贴做个笔记常规的\(\sinx,\cosx,\tanx\)以及之间的关......
  • HDOU2139 Calculate the formula
    链接:​​http://acm.hdu.edu.cn/showproblem.php?pid=2139​​很有意思,又是一个java过不了的题目。之前遇到过因为输入输出慢而A不了的,但可以使用java的StreamTokenizer和Pr......
  • Error: [email protected] has been disabled because it is a versioned formula!
    首先找到文件sudovim/opt/homebrew/Library/Taps/homebrew/homebrew-core/Formula/[email protected]找到disabel这一行,然后注释掉(就是在前面加个#);#disable!date:"202......