专栏文章

题解：P9869 [NOIP2023] 三值逻辑

yylch
P9869题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio3li8i
此快照首次捕获于
2025/12/02 12:48
3 个月前
此快照最后确认于
2025/12/02 12:48
3 个月前
查看原文
发现每个 xix_i 只有五种可能的值：TT、FF、UU、xjx_j、¬xj\lnot x_j。
如果我们设 xn+1=T,xn+2=Ux_{n+1}=T,x_{n+2}=U，那么 FF 也可以用 ¬xn+1\lnot x_{n+1} 表示。这样所有元素就都可以表示成 xi=xjx_i=x_j 或 xi=¬xjx_i=\lnot x_j 的形式。
在输入时发现只有最后一次赋值会对 xix_i 起实际影响，但其中的一些赋值操作也不是没用，可能会有关系上的影响。考虑先用类似并查集路径压缩的方式来存储每个结点对应的值（赋值结点）。
这样会形成互相独立的若干连通块，只要分开考虑即可。
我们希望使 UU 的个数最小，考虑什么时候会用到 UU。发现 UU 可以适用于除了操作 1 之外的所有情况，所以一定是在一个连通块中赋值出现了矛盾（例如转一圈后回来出现了 xi=¬xix_i=\lnot x_i 的情况），那么就只能用 UU 来解决。这样一整个连通块中所有数都只能是 UU。
因为并查集不好处理遍历，所以考虑根据并查集建图。具体地，对所有具有赋值关系的 i,ji,j 连无向边，若 xi=xjx_i=x_j 边权为 00，若 xi=¬xjx_i=\lnot x_j 边权为 11。（发现 nn 个点 nn 条边实际上是一个基环树）。
在图上我们应该怎么判断这种矛盾呢？发现如果 xix_i 进行了奇数次取反后又回到 xix_i，那么就出现了矛盾。也就是存在边权和为奇数的环。考虑用类似二分图染色的方法判定。
别忘了统计 xn+2x_{n+2}（UU）所在的连通块，因为它们就算不矛盾也注定是 UU。（别忘了减去 UU 自己，因为 UU 在题目中只是充当一个“标识”的作用，无实义）
O(n+m)O(n + m)。
CPP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    int n, m; cin >> n >> m;
    int T = n + 1, U = n + 2;

    vector<int> fa(n + 5), t(n + 5); // 记录每个结点的值（赋值的结点）和是否取反
    iota(fa.begin(), fa.end(), 0); // 初始化fa[i]=i
    for(int i = 1; i <= m; i ++){
        char op; cin >> op;
        if(op == 'T'){
            int x; cin >> x; fa[x] = T, t[x] = 0;
        }
        else if(op == 'F'){
            int x; cin >> x; fa[x] = T, t[x] = 1;
        }
        else if(op == 'U'){
            int x; cin >> x; fa[x] = U, t[x] = 0;
        }
        else if(op == '+'){
            int x, y; cin >> x >> y;
            fa[x] = fa[y], t[x] = t[y];
        }
        else if(op == '-'){
            int x, y; cin >> x >> y;
            fa[x] = fa[y], t[x] = t[y] ^ 1;
        }
    }

    // 建无向图+染色判定
    vector<int> vis(n + 5), val(n + 5); // 标记数组、染色权值
    vector<array<int, 2>> G[n + 5];
    for(int i = 1; i <= n; i ++){
        G[fa[i]].push_back({i, t[i]}); G[i].push_back({fa[i], t[i]});
    }
    function<int(int,bool&)> dfs = [&](int u, bool &flag){ // 染色判定+计算连通块大小
        vis[u] = 1;
        int siz = 1;
        for(auto [v, w] : G[u]){
            if(vis[v] && val[v] != (val[u] ^ w)){
                flag = false;
            }
            else if(!vis[v]){
                val[v] = val[u] ^ w; siz += dfs(v, flag);
            }
        }
        return siz;
    };
    int ans = 0;
    for(int i = 1; i <= n; i ++){
        if(!vis[i]){
            bool flag = true; val[i] = 1; int siz = dfs(i, flag);
            if(!flag) ans += siz; // 如果矛盾统计答案
        }
    }

    // 处理U所在的连通块大小
    fill(vis.begin(), vis.end(), 0); // 重置vis数组
    function<int(int)> dfs2 = [&](int u){ // 搜索U所在连通块大小
        vis[u] = 1;
        int siz = 1;
        for(auto [v, w] : G[u]){
            if(!vis[v]) siz += dfs2(v);
        }
        return siz;
    };
    ans += dfs2(U) - 1; // 别忘了减去U自己

    cout << ans << '\n';
}

signed main()
{
    ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int c, T; cin >> c >> T;
    while(T --) solve();
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...