Luogu-P9869-三值逻辑

Posted on Edited on Word count in article: 2.4k

题目 P9869 [NOIP2023] 三值逻辑

题目描述

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

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

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

$$
\lnot \mathit{T} = \mathit{F}, \lnot \mathit{F} = \mathit{T}, \lnot\mathit{U} = \mathit{U}.
$$

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

  1. $x_i \leftarrow v$，其中 $v$ 为 $\mathit{T}, \mathit{F}, \mathit{U}$ 的一种；
  2. $x_i \leftarrow x_j$；
  3. $x_i \leftarrow \lnot x_j$。

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

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

在本题中，你需要帮助小 L 找到 $\mathit{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 \lnot x_j$。

输出格式

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

思路：并查集

虽然这是个绿题，但是需要考虑的细节和问题转化的思维量应该足够当蓝题了。

问题转化

我个人写并查集的习惯是：

  • 父节点数组：$root$
  • 查找：find
  • 合并：merge

赋值的性质

  • 覆盖性
    一个变量的值取决于最后一次的赋值。
    所以，只需要在赋值的时候将之前的内容覆盖即可。

  • 传递性
    如果进行 $b \leftarrow a,c \leftarrow b$，那么 $c=a$。

并查集处理

如果我们认为，$x_i \leftarrow x_j$ 时直接令 $root[i]=j$，那么后续对 $x_j$ 的赋值操作也会影响 $x_i$ 的值。

但是根据题意，这不符合要求。

我们称，一个变量赋值的根本来源为根值。

又因为赋值具有传递性，所以一个变量的值只与它的根值有关。

例如，假设 $a,b,c,d$ 的初值分别为 $1,2,3,4$，在 $b \leftarrow a, c \leftarrow b, b \leftarrow d$ 之后，变量的值如下：

操作次数 a b c d
1 1 1 3 4
2 1 1 1 4
3 1 4 1 4

所以在 $x_i \leftarrow x_j$ 时，令 $root[i]=root[j]$，即可正确赋值。

冲突的情况

如果经过合并之后，$x$ 的根值为 $\lnot x$，因为 $x$ 最终变为了 $\not x$，要想保持最终 $x$ 的值不变，那么 $x$ 的初值一定为 $U$。

所以，所有以 $x$ 为根值的变量都是 $U$。

同时，如果 $x$ 的根值本身即为 $U$，那么 $x$ 一定是 $U$。

并查集

经过处理之后，就可以用并查集来找到每一个 $x_i$ 的根值了。

赋值操作处理

每次赋值可以按如下方式保存：

  • 如果 $x_i \leftarrow x_j$，那么 $root[i]=root[j]$。
  • 如果 $x_i \leftarrow \lnot x_j$，那么 $root[i]=-root[j]$。

特别地，将 $T,F,U$ 视为常量，建立一个常量数组 $idx$，让 $T,U$ 的下标大于所有变量的下标，再令 $idx[F]=-idx[T]$。

1
2
3
4
5
6
7
8
9
int idx['Z'];

int main(){
    // ...
    idx['T'] = 1e5 + 5;
    idx['F'] = -idx['T'];
    idx['U'] = 1e5 + 6;
    // ...
}

记录访问状态

由于此题的特殊性，在递归 $find(root[x])$ 时不加处理会死循环（当 $root[x]$ 为 $-x$ 时）。

所以，使用 $vis[x]$ 记录 $x$ 是否访问过：

  • 如果访问过 $x$，证明所有根值为 $x$ 的变量均不为 $U$。
  • 如果访问过 $-x$，那么由上述结论可知，$x$ 的根值应该为 $U$。

注意：以下代码存在不合理的地方，因此不可直接使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int find(int x) {
    if(check(x)) return x;
    if(vis[-x]) {
        root[x] = idx['U'];
        return idx['U'];
    }
    if(vis[x]) return x;
    // cout << x << endl;
    // printf("%d <- %d\n", root[x], x);
    if(root[x] != x) {
        vis[x] = true;
        root[x] = find(root[x]);
        vis[x] = false;
    }
    return root[x];
}

正负同时处理

由于存在负数，所以对于每个数字的处理都要正负一起进行。

所以，以下才是正确的 $find$ 函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int find(int x) {
    if(check(x)) return x;
    if(vis[-x]) {
        root[x] = idx['U'];
        root[-x] = -root[x];
        return idx['U'];
    }
    if(vis[x]) return x;
    // cout << x << endl;
    // printf("%d <- %d\n", root[x], x);
    if(root[x] != x) {
        vis[x] = true;
        root[x] = find(root[x]);
        root[-x] = -root[x];
        vis[x] = false;
    }
    return root[x];
}

计数

对所有的 $i \in [1,n]$，如果 $find(i)$ 为 $idx[U]$，就计数一次。

处理负数下标

我们知道，在C++中数组的下标只能 $\leq 0$。

但是刚才的代码中，出现了负数下标，要怎么处理？

以下提供两种方式

  • 第一种是将所有需要用到负数下标的位置统一加上 $N$，再访问 $x+N$ 来访问。

优点是编写方便，缺点是容易混淆。

  • 第二种也是我用的方法，自定义一个数组类型，如果 $x$ 为负数就返回 $x+N$ 下标的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <typename T, const int len>
struct Array {
    T value[len];
    T &operator[](int x) {
        int index = x;
        if(index < 0) index += len;
        return value[index];
    }
    void clear() {
        set(value, 0);
    }
};

Array<int, N * 2> root;
Array<bool, N * 2> vis;

AC Code

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
// template v12
#include <bits/stdc++.h>
#define set(x, y) memset(x, y, sizeof x)

using namespace std;
using ll = long long;

const int inf = 0x7f7f7f7f;

const int N = 1e5 + 10;

template <typename T, const int len>
struct Array {
    T value[len];
    T &operator[](int x) {
        int index = x;
        if(index < 0) index += len;
        return value[index];
    }
    void clear() {
        set(value, 0);
    }
};

Array<int, N * 2> root;
Array<bool, N * 2> vis;

int idx['Z'];

bool check(int x) {
    return (x == idx['T'] || x == idx['F'] || x == idx['U'] || x == -idx['U']);
}

int find(int x) {
    if(check(x)) return x;
    if(vis[-x]) {
        root[x] = idx['U'];
        root[-x] = -root[x];
        return idx['U'];
    }
    if(vis[x]) return x;
    // cout << x << endl;
    // printf("%d <- %d\n", root[x], x);
    if(root[x] != x) {
        vis[x] = true;
        root[x] = find(root[x]);
        root[-x] = -root[x];
        vis[x] = false;
    }
    return root[x];
}

void merge(int x, int y, int k) {
    root[x] = k * root[y];
    root[-x] = -root[x];
}

void init(int n) {
    for(int i = 1; i <= n; i++) {
        root[i] = i;
        root[-i] = -i;
    }
    root[idx['T']] = idx['T'];
    root[idx['F']] = idx['F'];
    root[idx['U']] = idx['U'];
    root[-idx['U']] = -idx['U'];
    vis.clear();
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("tribool3.in", "r", stdin);
    freopen("tribool.out", "w", stdout);
#endif
    idx['T'] = 1e5 + 5;
    idx['F'] = -idx['T'];
    idx['U'] = 1e5 + 6;
    int t;
    cin >> t >> t;
    int n, m;
    int t1, t2;
    while(t-- > 0) {
        cin >> n >> m;
        init(n);
        char c;
        int ans = 0;
        for(int i = 1; i <= m; i++) {
            cin >> c;
            switch(c) {
                case '+':
                    cin >> t1 >> t2;
                    merge(t1, t2, 1);
                    break;
                case '-':
                    cin >> t1 >> t2;
                    merge(t1, t2, -1);
                    break;
                default:
                    cin >> t1;
                    merge(t1, idx[c], 1);
                    break;
            }
        }
        for(int i = 1; i <= n; i++) {
            if(abs(find(i)) == idx['U']) ans++;
        }
        cout << ans << endl;
    }
    return 0;
}