专栏文章

题解：P9869 [NOIP2023] 三值逻辑

bbssmessi
P9869题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimzgyhj
此快照首次捕获于
2025/12/01 18:05
3 个月前
此快照最后确认于
2025/12/01 18:05
3 个月前
查看原文
介绍一个更加简洁易懂的并查集做法。
我们先考虑定义一个 ff 数组表示当前 xx 变量所取的值，变量被赋为 TT、FF、UU 的值分别用 11、−1-1、00 表示，这是一种巧妙便捷的选择，这样我们处理 ++ 和 −- 的时候就可以直接令 fx=fyf_{x}=f_{y} 或 fx=−fyf_{x}=-f_{y} 了。
CPP
for(int i=2;i<=n;i++) f[i]=i;
for(int i=0;i<=2*n;i++) fa[i]=i;
for(int i=1;i<=m;i++){
    char opt;cin>>opt;int x,y; 
    if(opt=='+') x=read()+1,y=read()+1,f[x]=f[y];
    //若为 +，就令f_x=f_y
    else if(opt=='-') x=read()+1,y=read()+1,f[x]=-f[y];
    //若为 -，就令f_x=-f_y，意思是使f_x等于f_y的反值。
    else if(opt=='T') x=read()+1,f[x]=1;
    else if(opt=='F') x=read()+1,f[x]=-1;
    else if(opt=='U') x=read()+1,f[x]=0;
}
处理完后 fxf_{x} 表示着 xx 变量的最终取值，现在我们就可以将 xx 并入 fxf_{x} 中,¬x\lnot x 并入 ¬fx\lnot f_{x} 中。
但是我们最先用对 xx 取相反数的方式传递 ff 值，这样是在赋值时是比较方便，但是如果直接照搬到 fafa 中下标会是负数，比较难处理，所以我们可以对于 x<0x<0，使 x=n−xx=n-x，这样就可以解决这一问题。
CPP
int get(int x){
	if(x<0) return n-x;
	return x; 	
}
接着我们考虑变量 xx 必须被取为 UU 的条件是 xx 的祖先是 UU 或 xx 的祖先是 ¬x\lnot x，但是我们令 U=0U=0，这样我们发现当 xx 取 UU 时，xx 与 ¬x\lnot x 恰好也是相等的，所以我们只用判断这一个条件就可以了。
CPP
#include<bits/stdc++.h>
using namespace std;
int read(){
	int f=1,k=0;char c=getchar();
	while(!isdigit(c)&&c!='-') c=getchar();
	if(c=='-') f=-1,c=getchar();
	while(isdigit(c)) k=k*10+(c-'0'),c=getchar();
	return f*k;
}
const int N=2e5+10;
int c,t,n,m,f[N],fa[N];
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y){
	int fx=find(x),fy=find(y);
	if(fx!=fy) fa[fx]=fy;
}
int get(int x){
	if(x<0) return n-x;
	return x; 	
}
int main(){
	c=read(),t=read();
	while(t--){
		n=read()+1,m=read();int ans=0;
		for(int i=2;i<=n;i++) f[i]=i;
		for(int i=0;i<=2*n;i++) fa[i]=i;
		for(int i=1;i<=m;i++){
			char opt;cin>>opt;int x,y; 
			if(opt=='+') x=read()+1,y=read()+1,f[x]=f[y];
			else if(opt=='-') x=read()+1,y=read()+1,f[x]=-f[y];
			else if(opt=='T') x=read()+1,f[x]=1;
			else if(opt=='F') x=read()+1,f[x]=-1;
			else if(opt=='U') x=read()+1,f[x]=0;
		}
		for(int i=2;i<=n;i++){
			merge(i,get(f[i]));merge(i+n,get(-f[i]));
		}
		for(int i=2;i<=n;i++){
			if(find(i)==find(i+n)) ans++;
		}
		cout<<ans<<"\n";
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...