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;
}
后记
实际上题目不需要特别保证“必定有解”,因为有解是必然的。对于并查集而言,某个连通块只要里面不包含 \(T,F\),那你全赋值 \(U\) 就必定合法。包含 \(T,F\) 的时候,\(u=T\) 时总有 \(\neg u=F\),所以它们的终值不会搅和(感性理解一下)。