专栏文章

AT_arc161_e [ARC161E] Not Dyed by Majority (Cubic Graph) 题解

JJorisyKuno Kako
AT_arc161_e题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@mio0f69o
此快照首次捕获于
2025/12/02 11:19
3 个月前
此快照最后确认于
2025/12/02 11:19
3 个月前
查看原文
这也太变态了。
首先证明一定有解。
设初始颜色序列 c∈Sc\in S 映射到最终的颜色序列为 c′∈Tc'\in T。若 ∣S∣>∣T∣|S|>|T|，那么显然就会存在未被映射到的颜色序列。如果这个成立那么就有解。
n<10n<10 的情况枚举可得，下面阐述 n≥10n\ge 10 的情况。
令 e(x)e(x) 表示与点 xx 直接相连的点的集合。设有一个点 xx，e(x)={u,v,w}e(x)=\{u,v,w\}，那么有 e(u)={x,u1,u2},e(v)={x,v1,v2},e(w)={x,w1,w2}e(u)=\{x,u_1,u_2\},e(v)=\{x,v_1,v_2\},e(w)=\{x,w_1,w_2\}。
如果说 cu1=cu2,cv1=cv2,cw1=cw2c_{u_1}=c_{u_2},c_{v_1}=c_{v_2},c_{w_1}=c_{w_2}，那么可以唯一确定 cu′=¬cu1,cv′=¬cv1,cw′=¬cw1c'_u=\lnot c_{u_1},c'_v=\lnot c_{v_1},c'_w=\lnot c_{w_1}。这三个都被唯一确定了，那么 cx′c'_x 也是唯一确定的。
那么此时发现，cxc_x 的值不影响 c′c'——换句话说，这个时候至少有 2n−62^{n-6} 种不同的 cc 对应着相同的 c′c'。
也就是说，如果我们随机一个 cc，那么其无解的概率 ≥164\ge\dfrac 1{64}。事实上，根据官方题解的说法，这个概率大得多（≈0.48\approx0.48）。不过我们估计的概率已经足以证明，我们可以 O(1)O(1) 次随出一个合法方案。
那么现在的问题就是要如何 check 合法性。
考虑一下，我们的限制形如，设有节点 xx 以及 e(x)={u,v,w}e(x)=\{u,v,w\}，「若 cx′≠cuc'_x\neq c_u，则 cx′=cv=cwc'_x=c_v=c_w」（轮换同理）。2-SAT 即可。
CPP
#include<bits/stdc++.h>
#define N 50005
#define ll long long
#define mod 
using namespace std;

mt19937_64 rnd(time(0));
vector<int>g0[N],g[N<<1];
int n,m,dfn[N<<1],low[N<<1],stk[N<<1],inst[N<<1],scc[N],cscc,ans[N];

void tarjan(int x)
{
    dfn[x]=low[x]=++dfn[0];
    stk[++stk[0]]=x;
    inst[x]=1;
    for(auto y:g[x])
    {
        if(!dfn[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(inst[y]) low[x]=min(low[x],dfn[y]);
    }
    if(low[x]^dfn[x]) return;
    cscc++;
    int y;
    do
    {
        y=stk[stk[0]--];
        inst[y]=0;
        scc[y]=cscc;
    }
    while(x^y);
}

bool jd()
{
    for(int i=1;i<=n*2;i++) g[i].clear();
    for(int i=1;i<=n;i++)
    {
        for(auto x:g0[i])
        {
            for(auto y:g0[i])
            {
                if(x==y) continue;
                g[x+(ans[i]^1)*n].push_back(y+ans[i]*n);
            }
        }
    }
    fill(scc,scc+n*2+1,0);
    fill(dfn,dfn+n*2+1,0);
    fill(low+1,low+n*2+1,0);
    fill(inst+1,inst+n*2+1,0);
    stk[0]=cscc=0;
    for(int i=1;i<=n*2;i++)
    {
        if(dfn[i]) continue;
        tarjan(i);
    }
    for(int i=1;i<=n;i++)
    {
        if(scc[i]^scc[i+n]) continue;
        return 1;
    }
    return 0;
}

void sol()
{
    cin>>n;
    m=n*3/2;
    for(int i=1;i<=n;i++) g0[i].clear();
    while(m--)
    {
        int u,v;
        cin>>u>>v;
        g0[u].push_back(v);
        g0[v].push_back(u);
    }
    while(1)
    {
        for(int i=1;i<=n;i++) ans[i]=rnd()&1;
        if(!jd()) continue;
        for(int i=1;i<=n;i++) cout<<"WB"[ans[i]];
        cout<<'\n';
        break;
    }
}

int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--) sol();
    return 0;
}

评论

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

正在加载评论...