P9869-NOIP2023-B-三值逻辑

· · 题解

题目传送门

题外话

由于很多人对本题并查集做法提问，本人于二零二四年一月二十日对此篇题解进行了更新。

巧妙方法

相信大家已经知道此题的并查集、高斯消元等解法了，本人在此篇题解对此不再赘述，只是给大家提供一种代码细节——处理三值逻辑的符号的一些巧妙的方法。

我们其实可以把三值逻辑分别赋予三个值，再把这三个值赋予三个常量，常量名就以 T、F、U 所命名，方便我们下面并查集中的代码编写。我们接着规定逻辑非运算就是把值的正负取反，那么 U 常量的值就应该为 0（因为 0=-0）。而 T 常量和 F 常量的值呢？因为要把常量值和变量值区别开，我们这里取一个 n 的上限加一的值，即 100001 和 -100001。这样我们在代码编写中就可以以常量名代替繁琐的字符判断，本人认为是十分巧妙且便捷的。

本人做法

这里具体说一下并查集做法（也是更新部分）。

我们的大体思路是先按照题意模拟，给所有输入的操作的相关变量用并查集标记，在并查集查询操作前我们就可以确定哪些变量的值是确定的，哪些是不确定的，这时我们的任务就是最小化不确定的变量中 U 的个数。那哪些情况的变量它的值一定是 U 呢？总的来说有两种：

我们把这两种情况查询出来，再统计个数，就是最终答案了！由于 x 的值可能我们可能标记成负数了，所以并查集查询时遇到负数要取相反数，不然就会运行错误（别问我怎么知道的，哭）。

由于我们要查询的 x 的祖先有可能是 -x，取相反数后又是 x，这样就会陷入死循环。于是我们需要用 book 数组记录是否到过这个点的相反数（其实就是上面所写的情况一）。由于 book 记录的值也有负数，所以我们要给记录的值统一加上一个 n 把其全变成正数。这时需要注意 book 数组的大小要开到 2\times n 哦。

然后，就没有然后了（写代码呗）。

代码

上代码（马蜂良好，条件语句清楚，适宜阅读）。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int T=100001,F=-100001,U=0;//三值逻辑
int c,t,n,m,a,b,fa[100005];
char ch[100005];
bool book[300005];
int find(int x) {
    int re;
    if(x==T||x==F)re=x;
    else if(book[n-x]||x==U)re=U;
    else if(book[x+n])re=T;
    else if(x<0) {
        if(x==-fa[-x])re=x;
        else {
            book[x+n]=1;
            re=find(-fa[-x]);//这里注意细节
            book[x+n]=0;//清空
        }
    } else {
        if(x==fa[x])re=x;
        else {
            book[x+n]=1;
            re=fa[x]=find(fa[x]);
            book[x+n]=0;//清空
        }
    }
    return re;
}
signed main() {
    cin>>c>>t;
    while(t--) {
        cin>>n>>m;
        for(int i=1; i<=n; i++)fa[i]=i;
        for(int i=1; i<=m; i++) {
            cin>>ch[i];
            if(ch[i]=='T') {
                cin>>a;
                fa[a]=T;
            } else if(ch[i]=='F') {
                cin>>a;
                fa[a]=F;
            } else if(ch[i]=='U') {
                cin>>a;
                fa[a]=U;
            } else {
                cin>>a>>b;
                if(ch[i]=='+')fa[a]=fa[b];
                else fa[a]=-fa[b];
            }
        }
        int ans=0;
        for(int i=1; i<=n; i++) {
            if(find(i)==U)ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

后记

祝点赞的人都有蓝勾！

另外，这么好的一篇题解，关注一下我呗。

站长曾经说过，不抄袭题解代码，只借鉴题解思路，但应该给题解点个赞，并且关注写题解的人（开玩笑的）。