Luogu-P9869-三值逻辑

Posted on 2024-11-03 Edited on 2025-02-24 Word count in article: 1.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$ 表示赋值：

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

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

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

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

输入格式

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

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

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

输入的第一行包含两个整数 $n$ 和 $m$ ，分别表示变量个数和语句条数。
接下来 $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]$ 。

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$ 。

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

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$ 函数。

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$ 下标的值。

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

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