P9869 [NOIP2023] 三值逻辑

· · 题解

blog

赛时做法。

钦定 T 为 1，F 为 -1，U 为 0。

发现每个值都有两个状态，它本身及其取反。

在 m 个操作完后我们对每个值的状态一共有三种情况：

  1. 没有对这个值进行操作，不知晓任何信息。

  2. 这个值与另外一个值有关，能从另外一个值推出当前值。

  3. 已经确定是 T/F/U。

考虑定义数组 ok_x 表示 x 这个值有没有被确定，如果被确定了则将其存在 val_x 中。

对于第二种情况，定义数组 p_x 与 sig_x 表示 x 的值与 p_x 的值有关，sig_x = 1/-1 表示 x 是 / 否需要对 p_x 取反。

此时很容易处理出输入部分的代码。

while (m --) {
    char op;
    int x, y;
    cin >> op;
    if (op == '+') {
        cin >> x >> y;
        if (ok[y]) {
            ok[x] = true;
            val[x] = val[y];
        } else {
            ok[x] = false;
            p[x] = p[y];
            sig[x] = sig[y];
        }
    } else if (op == '-') {
        cin >> x >> y;
        if (ok[y]) {
            ok[x] = true;
            val[x] = -val[y];
        } else {
            ok[x] = false;
            p[x] = p[y];
            sig[x] = -sig[y];
        }
    } else {
        cin >> x;
        ok[x] = true;
        if (op == 'U') {
            val[x] = 0;
        } else if (op == 'T') {
        val[x] = 1;
        } else {
            val[x] = -1;
        }
    }
}

考虑如何对答案进行计数。

首先显然的是如果一个值已经确定为 U，那么它一定得是 U，此时值与它有关的不管需不需要取反都必须是 U。

其次如果经过操作后，我们得到了 x 最后的值是它本身取反，那也一定是 U，因为只有 U 取反后还是本身，此时与它和它取反相等的值都要是 U。

对于一个 x 等于另外一个数然而另外一个数确定为 u

不难得到别的情况都有一种方案使得不是 U。

如何处理和某个值相等 / 相反的值？

这是扩展域并查集的经典问题。

让 x 取反在并查集中变成 x+n。

如果一个 x 必须和 y 相等，那么 x 和 y 取反后也要相等，所以在并查集中合并 x,y 和 x+n,y+n。

如果一个 x 要和 y 取反后相等，那么 x 取反后和 y 相等，所以合并 x,y+n 和 x+n,y。

注意计算答案时一个集合的答案只能算一次，但一个集合中可能有多个数都满足，所以算完一个集合的答案后要把这个集合的 siz 清空。

让一个数 x 的答案只在他本身取到而不在取反取到，让 x+n 的大小一开始设为 0。

代码思路比较清晰，应该有比我更简洁的写法。

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    fa[x] = y, siz[y] += siz[x];
}

void add(int &res, int x) {
    x = find(x);
    res += siz[x];
    siz[x] = 0;
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        ok[i] = false, val[i] = 0;
        p[i] = i, sig[i] = 1;
    }
    for (int i = 1; i <= n * 2; i ++) {
        fa[i] = i, siz[i] = i <= n;
    }

    while (m --) {
        char op;
        int x, y;
        cin >> op;
        if (op == '+') {
            cin >> x >> y;
            if (ok[y]) {
                ok[x] = true;
                val[x] = val[y];
            } else {
                ok[x] = false;
                p[x] = p[y];
                sig[x] = sig[y];
            }
        } else if (op == '-') {
            cin >> x >> y;
            if (ok[y]) {
                ok[x] = true;
                val[x] = -val[y];
            } else {
                ok[x] = false;
                p[x] = p[y];
                sig[x] = -sig[y];
            }
        } else {
            cin >> x;
            ok[x] = true;
            if (op == 'U') {
                val[x] = 0;
            } else if (op == 'T') {
                val[x] = 1;
            } else {
                val[x] = -1;
            }
        }
    }

    for (int i = 1; i <= n; i ++) {
        if (ok[i]) continue;
        int x = p[i];
        if (sig[x] == 1) {
            merge(i, x), merge(i + n, x + n);
        } else {
            merge(i + n, x), merge(x + n, i);
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i ++) {
        if (ok[i] && val[i] == 0) {
            add(res, i), add(res, i + n);
        } else if (find(i) == find(i + n)) {
            add(res, i);
        }
    }

    cout << res << "\n";
}