P9869 [NOIP2023] 三值逻辑

题目描述

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

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

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

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

  1. xi ← v，其中 v 为 T, F, U 的一种；
  2. xi ← xj；
  3. xi ← ¬xj。

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

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

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

输入格式

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

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

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

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

输出格式

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

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
9
10
11
12
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

1
2
3
0
3
1

说明/提示

【样例解释 #1】

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

  • x2 ← ¬x1；
  • x3 ← ¬x2；
  • x1 ← x3。

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

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

  • x2 ← ¬x1；
  • x3 ← ¬x2；
  • x1 ← ¬x3。

唯一的赋初值方案为 x1 = x2 = x3 = U，共有 3 个 Unknown 变量，故输出为 3。

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

  • x2 ← T；
  • x2 ← U；

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

【数据范围】

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

  • 1 ≤ t ≤ 6，1 ≤ n, m ≤ 105；
  • 对于每个操作，v 为 TFU+- 中的某个字符，1 ≤ i, j ≤ n。

解决方案

1. 解题思路

考场上蒙圈了，直接无脑并查集，结果 40 分…… 但现在仔细一想其实很简单。我们模拟一下，就拿 样例 1 的第 2 组数据 来说：

初始状态 x1, x2, x3

第一步执行后 (x2 ← ¬x1) x1, ¬x1, x3

第二步执行后 (x3 ← ¬x2) x1, ¬x1, x1 (注：此时 x2 是 ¬x1，再取反就是 x1)

第三步执行后 (x1 ← ¬x3) ¬x1, ¬x1, x1 (注：此时 x3 指向的是上一轮的 x1，取反即 ¬x1)

题目又说，执行完这些语句后，初值与终值相等，所以：

x1 = ¬x1,  x2 = ¬x1,  x3 = x1

显然，如果推导出了 x1 = ¬x1，那么 x1 必须为 U，进而导致 x2, x3 也必须为 U。

2. 核心结论

只要按顺序模拟，最后判断每个变量是否矛盾，或与一个矛盾的变量相等即可。

具体来说，需要 2n + 3 个变量，分别是：

  • 1 ∼ n: 即 x1 ∼ xn
  • n + 1 ∼ 2n: 即 ¬x1 ∼ ¬xn
  • 2n + 1, 2n + 2, 2n + 3: 分别代表常量 T, F, U

用数组 t[i] 来表示 xi 节点目前等于 xt[i]，初始 t[i] = i。

全部赋值完后，开始并查集。由于初值与终值相等，因此 xi 的值应当等于 xt[i]，把他们放在一个集合里。

最后，如果 xi 和 xn + i 在同一个集合里，则 xi 只能是 U。

3. 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int c,T,f[2*maxn],n,m,t[2*maxn];
int fa(int x){
  if(f[x]==x)return x;
  return f[x]=fa(f[x]);
}
void me(int x,int y){
  int fx=fa(x),fy=fa(y);
  f[fx]=fy;
}
int main(){
  scanf("%d%d",&c,&T);
  while(T--){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=2*n+3;++i){
      f[i]=i;
      t[i]=i;   
    }
    char ch;
    for(int i=1;i<=m;++i){
      
      scanf(" %c",&ch);
      int x;
      scanf("%d",&x);
      if(ch=='+'){
        int y;scanf("%d",&y);
        if(y!=x){
          t[x]=t[y];
          t[n+x]=t[n+y];
        }
      }
      else if(ch=='-'){
        int y;scanf("%d",&y);
        if(y!=x){
          t[n+x]=t[y];
          t[x]=t[n+y];
        }
        else swap(t[x],t[n+x]); 
      }
      else{
        int op=0;
        if(ch=='T')op=1;
        if(ch=='F')op=2;
        if(ch=='U')op=3;
        if(op<=2){
          t[x]=2*n+op;
          t[n+x]=2*n+3-op;
        }
        else{
          t[x]=t[n+x]=2*n+3;
        }
      }
    }
    for(int i=1;i<=n;++i){
      if(t[i]!=i){
        me(i,t[i]);me(n+i,t[n+i]);
      }
    }
    int ans=0;
    for(int i=1;i<=n;++i){
      if(fa(i)==fa(n+i))ans+=1;
    }
    printf("%d\n",ans);
  }
}