打卡信奥刷题（3389）用C++实现信奥题 P9869 [NOIP2023] 三值逻辑

P9869 [NOIP2023] 三值逻辑

题目描述

小 L 今天学习了 Kleene 三值逻辑。

在三值逻辑中，一个变量的值可能为：真（$True$，简写作 $T$）、假（$False$，简写作 $F$）或未确定（$Unknown$，简写作 $U$）。

在三值逻辑上也可以定义逻辑运算。由于小 L 学习进度很慢，只掌握了逻辑非运算 $\neg$，其运算法则为：
$$\neg T=F,\neg F=T,\neg U=U.$$

现在小 L 有 $n$ 个三值逻辑变量 $x_1,\cdots ,x_n$。小 L 想进行一些有趣的尝试，于是他写下了 $m$ 条语句。语句有以下三种类型，其中 $\leftarrow$ 表示赋值：

一开始，小 L 会给这些变量赋初值，然后按顺序运行这 $m$ 条语句。

小 L 希望执行了所有语句后，所有变量的最终值与初值都相等。在此前提下，小 L 希望初值中 $Unknown$ 的变量尽可能少。

在本题中，你需要帮助小 L 找到 $Unknown$ 变量个数最少的赋初值方案，使得执行了所有语句后所有变量的最终值和初始值相等。小 L 保证，至少对于本题的所有测试用例，这样的赋初值方案都必然是存在的。

输入格式

本题的测试点包含有多组测试数据。

输入的第一行包含两个整数 $c$ 和 $t$，分别表示测试点编号和测试数据组数。对于样例，$c$ 表示该样例与测试点 $c$ 拥有相同的限制条件。

接下来，对于每组测试数据：

• 输入的第一行包含两个整数 $n$ 和 $m$，分别表示变量个数和语句条数。
• 接下来 $m$ 行，按运行顺序给出每条语句。
  • 输入的第一个字符 $v$ 描述这条语句的类型。保证 $v$ 为 TFU+- 的其中一种。
  • 若 $v$ 为 TFU 的某一种时，接下来给出一个整数 $i$，表示该语句为 $x_i\leftarrow v$；
  • 若 $v$ 为 +，接下来给出两个整数 $i,j$，表示该语句为 $x_i\leftarrow x_j$；
  • 若 $v$ 为 -，接下来给出两个整数 $i,j$，表示该语句为 $x_i\leftarrow \neg x_j$。

输出格式

对于每组测试数据输出一行一个整数，表示所有符合条件的赋初值方案中，$Unknown$ 变量个数的最小值。

输入输出样例 #1

输入 #1

1 3
3 3
– 2 1
– 3 2
+ 1 3
3 3
– 2 1
– 3 2
– 1 3
2 2
T 2
U 2

输出 #1

0
3
1

说明/提示

【样例解释 #1】

第一组测试数据中，$m$ 行语句依次为

• $x_2\leftarrow \neg x_1$；
• $x_3\leftarrow \neg x_2$；
• $x_1\leftarrow x_3$。

一组合法的赋初值方案为 $x_1=T,x_2=F,x_3=T$，共有 $0$ 个 $Unknown$ 变量。因为不存在赋初值方案中有小于 $0$ 个 $Unknown$ 变量，故输出为 $0$。

第二组测试数据中，$m$ 行语句依次为

• $x_2\leftarrow \neg x_1$；
• $x_3\leftarrow \neg x_2$；
• $x_1\leftarrow \neg x_3$。

唯一的赋初值方案为 $x_1=x_2=x_3=U$，共有 $3$ 个 $Unknown$ 变量，故输出为 $3$。

第三组测试数据中，$m$ 行语句依次为

• $x_2\leftarrow T$；
• $x_2\leftarrow U$；

一个最小化 $Unknown$ 变量个数的赋初值方案为 $x_1=T,x_2=U$。$x_1=x_2=U$ 也是一个合法的方案，但它没有最小化 $Unknown$ 变量的个数。

【样例解释 #2】

该组样例满足测试点 $2$ 的条件。

【样例解释 #3】

该组样例满足测试点 $5$ 的条件。

【样例解释 #4】

该组样例满足测试点 $8$ 的条件。

【数据范围】

对于所有测试数据，保证：

• $1\le t\le 6$，$1\le n,m\le 10^5$；
• 对于每个操作，$v$ 为 TFU+- 中的某个字符，$1\le i,j\le n$。

C++实现

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

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容