当前位置：首页 > news >正文

LGP9869 [NOIP 2023] 三值逻辑学习笔记

news 2025/10/14 9:20:17

LGP9869 [NOIP 2023] 三值逻辑学习笔记

\(\texttt{Luogu Link}\)

题意简述

小 \(\texttt{L}\) 今天学习了 \(\texttt{Kleene}\) 三值逻辑。

在三值逻辑中，一个变量的值可能为真、假、未定。记为 \(T,F,U\)。

在三值逻辑上也可以定义逻辑运算。小 \(\texttt{L}\) 现在只学了逻辑非运算：\(\neg T=F,\neg F=T,\neg U=U\)。

现在，小 \(\texttt{L}\) 有 \(n\) 个三值逻辑变量 \(x_1,\cdots,x_n\)。他写下了 \(m\) 个语句，有以下三种：

\(x_i\gets v\)，\(v\in \{T,F,U\}\)。
\(x_i\gets x_j\)。
\(x_i\gets \neg x_j\)。

一开始，小 \(\texttt{L}\) 会给这些变量赋初值，然后按顺序运行这 \(m\) 条语句。小 \(\texttt{L}\) 希望执行了所有语句后，所有变量的最终值与初值都相等。在此基础上他想最小化初值中 \(U\) 的数量。请求出这个最小值。

\(n,m\le 10^5\)。保证所有数据必然有解。

做法解析

首先这种关系赋予连结看着就像并查集题目，题中出现了 \(x_i\gets \neg x_j\)，所以当然对于每个 \(i\) 建 \(x_i\) 和 \(x_{i+n}=\neg x_i\) 两个点。

这个套路对于解题的必要性在于可以通过“有 \(x_i\) 和 \(\neg x_i\) 处于同一连通块”来判不合法或无解之类的。

既然要最终值与初值相等，我们当然关心这些变量的终值是哪儿来的，所以我们记 \(src_i=j\)，意为 \(i\) 的终值来源于 \(j\) 的初值。对于每一条语句，显然相当于执行：\(src_i\gets src_j\)，\(\neg src_i\gets \neg src_j\)。

对。执行 \(m\) 条语句这步实际上不涉及到并查集。你在这用并查集就错了。比如 \(x_1\) 先 \(=x_2\) 再 \(=x_3\)，你并查集把它们全连起来那肯定错了。倒着做只管终值也做不了，因为你不知道终值的来源的来源可以追溯到哪。

最后你按着 \(src\) 去做并查集的 merge() 就行了。这个不需要我教你了吧。

代码实现

#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=1e5+5;
int N,M,X,Y;char ch;
int TT,FF,UU,src[MaxN<<1];
struct UnionFind{int n,ufa[MaxN<<1];void init(int x){n=x;for(int i=1;i<=n;i++)ufa[i]=i;}int find(int u){return ufa[u]==u?u:ufa[u]=find(ufa[u]);}void merge(int u,int v){ufa[find(v)]=find(u);}bool judge(int u,int v){return find(u)==find(v);}
}UnF;
void addb(int u,int o){if(o==1)src[u]=TT,src[u+N]=FF;if(o==2)src[u]=FF,src[u+N]=TT;if(o==3)src[u]=src[u+N]=UU;
}
void addn(int u,int v,int k){src[u]=src[v];src[u+N]=src[v+N];if(k)swap(src[u],src[u+N]);
}
int ans;
void mian(){readis(N,M);UnF.init(N*2+3);TT=N*2+1,FF=N*2+2,UU=N*2+3;for(int i=1;i<=N*2+3;i++)src[i]=i;for(int i=1;i<=M;i++){scanf(" %c",&ch);if(ch=='T')readi(X),addb(X,1);if(ch=='F')readi(X),addb(X,2);if(ch=='U')readi(X),addb(X,3);if(ch=='+')readis(X,Y),addn(X,Y,0);if(ch=='-')readis(X,Y),addn(X,Y,1);}for(int i=1;i<=N*2+3;i++)UnF.merge(i,src[i]);ans=0;for(int i=1;i<=N;i++)ans+=(UnF.judge(i,i+N)||UnF.judge(i,UU));writil(ans);
}
int Tpn,Tcn;
int main(){readis(Tpn,Tcn);while(Tcn--)mian();return 0;
}