P9869题解

· · 个人记录

P9869 [NOIP2023] 三值逻辑

题目传送门

题解

T2 三值逻辑(tribool)

考察：模拟、图论（？）

我们拿个数组分别记录每个值在此刻与谁相等或与谁相反，特殊的，对于定值，多用 3 个变量记录，这是好模拟的。

然后操作结束后会得到若干初始值之间的相等与相反关系，考虑用无向有权图来刻画，那么由于每个点最多只贡献一条边，最终得到的是一个树与基环树的森林。

考虑对于每个联通块统计答案，容易发现，一个联通块要么全是 U 要么全不是 U，所以：如果其中有 U，那么只能算上贡献，否则除非迫不得已，我们一定不会赋 U。什么叫迫不得已？只有一种情况，就是基环树的环为奇环（奇环树（雾）），然后答案就是好统计的了。

但是细节很多，比如你基环树会找环吗？

我的代码相当丑：

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
    int s=0,m=0;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
    while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return m?-s:s;
}
int c,t,n,m,a[100005],fl[100005];
char op[5];int x,y;
int h[100005],cnt;
struct QWQ{int v,w,nxt;} e[100005*2];
void add(int u,int v,int w) {e[++cnt]={v,w,h[u]},h[u]=cnt;}
int vis[100005],num,ff,ans;
stack<int> st,wt;
void dfs(int u,int p,int ww) {
    vis[u]=1;num++;
    st.push(u);wt.push(ww);
    for(int i=h[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w;
        if(v==p) continue;
        if(vis[v]&&ff==-1) {
            ff=w;
            while(st.size()&&st.top()!=v) {
                ff^=wt.top();
                st.pop();wt.pop();
            }
        }
        if(!vis[v]) dfs(v,u,w);
    }
    if(ff==-1) st.pop(),wt.pop();
}
signed main() {
    cin>>c>>t;
    while(t--) {
        n=read(),m=read();
        for(int i=1;i<=n+3;i++) a[i]=i,fl[i]=0;
        memset(h,0,sizeof(h));cnt=0;
        memset(vis,0,sizeof(vis));
        ans=0,num=0;
        for(int i=1;i<=m;i++) {
            scanf("%s%lld",op+1,&x);
            switch(op[1]) {
                case '+':y=read();a[x]=a[y],fl[x]=fl[y];break;
                case '-':y=read();a[x]=a[y],fl[x]=fl[y]^1;break;
                case 'T':a[x]=n+1,fl[x]=0;break;
                case 'F':a[x]=n+2,fl[x]=0;break;
                case 'U':a[x]=n+3,fl[x]=0;break;
            }
        }
        for(int i=1;i<=n;i++)
            add(i,a[i],fl[i]),add(a[i],i,fl[i]);
        while(st.size()) st.pop(),wt.pop();ff=-1;
        dfs(n+3,0,0);
        ans+=num-1;
        while(st.size()) st.pop(),wt.pop();ff=-1;
        if(!vis[n+1]) dfs(n+1,0,0);
        while(st.size()) st.pop(),wt.pop();ff=-1;
        if(!vis[n+2]) dfs(n+2,0,0);
        for(int i=1;i<=n;i++) {
            if(!vis[i]) {
                while(st.size()) st.pop(),wt.pop();ff=-1;
                int las=num;
                dfs(i,0,0);
                if(ff==1) ans+=num-las;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

时间复杂度 O(\sum n+m)。