Wuyanru's blog
0%

[ARC161E] Not Dyed by Majority (Cubic Graph)

发表于 分类于 ，

非常好猜结论，使我的大脑旋转。

题目链接。

题意

现在有一张 个点的图，每一个点度数恰好是 。每一个点是黑色或白色之一。

称一次操作是，所有点的颜色同时变为它的邻居的众数。

构造一组颜色方案，使得任意的初始情况，进行一次操作之后，不能变成这种方案。

。

题解

首先考虑如何 check 一个方案是否合法。

如果一个点 最后是白色，它又三个邻居 ，这说明操作之前， 中至少有一个白色， 中至少有一个白色， 中至少有一个白色。

这可以用一个 2-SAT 解决，跑不出方案说明构造合法。

现在知道怎么 check 了，怎么构造呢？

考虑这么一个事情，设 的三个邻居分别是 ，然后 的邻居是 。

假设有一组初始方案，点 是白色，并且对于 有 和 同色。

可以发现，此时若把点 转成黑色，操作一次后得到的结果不会变，这说明什么呢？

说明我们可以找到 对初始方案，使得每一对方案一次操作之后得到相同结果。

那就说明，至少有 种方案是合法的，意味着我们随机一组方案，他有至少 的概率合法。

那么我们直接一直随机方案，直到随到一组合法的为止。

时间复杂度单组 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
template<const int N,const int M>
struct graph
{
    int head[N+5];
    int ww[M+5];
    int t[M+5];
    int x[M+5];
    int cntm;
    graph(){ cntm=1;}
    inline void clear(int n=N)
    {
        cntm=1;
        for(int i=1;i<=n;i++) head[i]=0;
    }
    inline void ad(int u,int v,int w=0)
    {
        cntm++;
        t[cntm]=v;
        x[cntm]=head[u];
        ww[cntm]=w;
        head[u]=cntm;
    }
    inline void add(int u,int v,int w=0)
    {
        ad(u,v,w);
        ad(v,u,w);
    }
    inline int st(int num){ return head[num];}
    inline int to(int num){ return t[num];}
    inline int nx(int num){ return x[num];}
    inline int w(int num){ return ww[num];}
};
graph<100000,300000>g;
mt19937 _rand(0);
bool v[50005];
vc<int>e[50001];
bool in[100001];
int sta[100001],top;
int dfn[100001];
int low[100001];
int scc[100001];
int n,c,tim;
inline void R()
{
    for(int i=1;i<=n;i++) v[i]=_rand()&1;
}
void dfs(int num)
{
    dfn[num]=low[num]=++tim;
    in[num]=1,sta[++top]=num;
    for(int i=g.st(num);i;i=g.nx(i))
    {
        int p=g.to(i);
        if(!dfn[p]) dfs(p),low[num]=min(low[num],low[p]);
        else if(in[p]) low[num]=min(low[num],dfn[p]);
    }
    if(dfn[num]!=low[num]) return ;
    c++;int now;
    do
    {
        now=sta[top--];
        scc[now]=c,in[now]=0;
    }while(now!=num);
}
inline bool check()
{
    for(int i=1;i<=n;i++) for(int j=0;j<3;j++) for(int k=0;k<3;k++) if(j!=k)
        g.ad(e[i][j]+(!v[i])*n,e[i][k]+v[i]*n);

    for(int i=1;i<=2*n;i++) if(!dfn[i]) dfs(i);

    bool f=1;
    for(int i=1;i<=n;i++) if(scc[i]==scc[i+n]) f=0;
    memset(dfn,0,sizeof(int)*(2*n+1));
    memset(low,0,sizeof(int)*(2*n+1));
    tim=c=0,g.clear(2*n);

    return f;
}
inline void solve()
{
    n=read();
    for(int i=1;i<=n;i++) e[i].clear();
    for(int i=1;i<=n*3/2;i++)
    {
        int u=read(),v=read();
        e[u].push_back(v);
        e[v].push_back(u);
    }

    R();
    while(check()) R();

    for(int i=1;i<=n;i++) putchar(v[i]?'B':'W');
    putchar('\n');
}
int main()
{
    int T=read();
    while(T--) solve();
    return 0;
}