题解：P9869 [NOIP2023] 三值逻辑

bssmessi · 2025-11-27 19:12:10 · 题解

介绍一个更加简洁易懂的并查集做法。

我们先考虑定义一个 f 数组表示当前 x 变量所取的值，变量被赋为 T、F、U 的值分别用 1、-1、0 表示，这是一种巧妙便捷的选择，这样我们处理 + 和 - 的时候就可以直接令 f_{x}=f_{y} 或 f_{x}=-f_{y} 了。

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;
}

处理完后 f_{x} 表示着 x 变量的最终取值，现在我们就可以将 x 并入 f_{x} 中,\lnot x 并入 \lnot f_{x} 中。

但是我们最先用对 x 取相反数的方式传递 f 值，这样是在赋值时是比较方便，但是如果直接照搬到 fa 中下标会是负数，比较难处理，所以我们可以对于 x<0，使 x=n-x，这样就可以解决这一问题。

int get(int x){
    if(x<0) return n-x;
    return x;   
}

接着我们考虑变量 x 必须被取为 U 的条件是 x 的祖先是 U 或 x 的祖先是 \lnot x，但是我们令 U=0，这样我们发现当 x 取 U 时，x 与 \lnot x 恰好也是相等的，所以我们只用判断这一个条件就可以了。

#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;
}