题解：ARC161E Not Dyed by Majority (Cubic Graph)

· · 题解

很有意思的题。

首先考虑 spj 怎么实现，那么要解决两个问题：如何判断无解，如何判断解合法。

对于判断合法，假设 u 操作后的颜色为 c，相邻的三个点为 v_1,v_2,v_3，那么限制就是操作前这三个点中至少有两个颜色为 c，或者说如果操作前 v_1 颜色不是 c，那么 v_2,v_3 的颜色必须是 c，v_2,v_3 操作前的颜色不是 c 同理。

那么一个操作后的颜色序列合法，当且仅当不存在满足上述要求的操作前的颜色序列，这就是一个 2-SAT 问题了，可以 O(n) 解决。

对于判断无解，考虑如果无解，那么说明每个颜色序列都存在一个颜色序列操作一次后得到。这就构成了一个 \{0,1\}^n 到自己的满射，那么它肯定也是双射。但这是不可能的，因为对于 n 个点全染黑 和 1 个点染白剩下 n-1 个点染黑两种颜色序列，操作一次后的结果都是全黑，那么这不可能是单射，也就不是双射。所以本题不存在无解的情况。

接下来的做法很大胆，但绝大多数人可能都想过（不一定是对于这个题）：直接随机答案。

其实仔细想一想上面那个映射，大概可以感觉到有一种对称性，也就是有“一定比例”的颜色序列都不能被映射到。

具体一点，我们的想法是找到一个局部结构，如果这个局部中有 a 种可能的颜色序列，只能映射到 b(b<a) 种颜色序列，那么对于全局大概就有 \frac{a-b}{a} 的序列可以作为答案。

考虑操作前的颜色序列。对于一个点 x、距离 x 为 1 的点 y_1,y_2,y_3、距离 x 为 2 的点 z_{1,1},z_{1,2},z_{2,1},z_{2,2},z_{3,1},z_{3,2}，只考虑 x,z_{1,1},z_{1,2},z_{2,1},z_{2,2},z_{3,1},z_{3,2} 的颜色，其他点的颜色已经确定，那么有 2^7=128 种颜色序列。而如果 (z_{1,1},z_{1,2}),(z_{2,1},z_{2,2}),(z_{3,1},z_{3,2}) 中每对点的颜色都一样，那么不管 x 的颜色是什么，操作一次后的颜色序列都一样。这说明这 128 种操作前的序列至多对应到 128-8=120 种可能的序列。所以感性理解就有 \frac{128-120}{128}=\frac{1}{16} 的序列是可以作为答案的。

这说明可以作为答案的颜色序列在 \{0,1\}^n 中的占比是不超过 O(1) 的，也就是期望随机不超过 O(1) 次就能得到答案，所以总复杂度是 O(n)。

如果用占比为 \frac{1}{16} 计算，那么随机 300 次还找不到答案的概率不到 4\times10^{-9}，即使是 10^6 组测试数据找不到答案的概率也只有不到 0.004。

事实上，可以证明答案在所有序列中的占比要比 \frac{1}{16} 高得多，具体分析参考官方题解。

通过代码：

#include <bits/stdc++.h>
typedef long long LL;
typedef std::pair<int, int> pii;
typedef unsigned long long ULL;
#define MP std::make_pair 
#define fi first
#define se second
char buf[1 << 20], *p1 = 0, *p2 = 0;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), (p1 == p2)) ? 0 : (*p1++))
int read()
{
    int s = 0; int f = 1, c = getchar();
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) s = s * 10 + (c ^ 48);
    return f ? s : -s;
}
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fll;
template<typename T> void Fmax(T &x, T y){ if (x < y) x = y; }
template<typename T> void Fmin(T &x, T y){ if (y < x) x = y; }
const int MAXN = 100005;
int n, m, col[MAXN], id[MAXN][2];
int e[MAXN][3], cnt[MAXN];
void init()
{
    n = read(), m = n / 2 * 3; 
    memset(cnt + 1, 0, n << 2);
    for (int i = 1; i <= m; i++)
    {
        int u = read(), v = read();
        e[u][cnt[u]++] = v, e[v][cnt[v]++] = u;
    }
    for (int i = 1; i <= n; i++)
        id[i][0] = (i - 1) << 1, id[i][1] = (i - 1) << 1 | 1;
}
namespace SAT
{
    int hd[MAXN], to[MAXN * 3], nxt[MAXN * 3], tot;
    void add(int x, int y){ to[++tot] = y, nxt[tot] = hd[x], hd[x] = tot; }
    int dfn[MAXN], low[MAXN], dcnt, st[MAXN], tp, N, bel[MAXN];
    bool inSt[MAXN];
    void init(int n){ tot = -1, memset(hd, -1, n << 3); }
    void dfs(int x)
    {
        dfn[x] = low[x] = ++dcnt;
        inSt[st[++tp] = x] = true;
        for (int e = hd[x], y; ~e; e = nxt[e])
            if (!dfn[y = to[e]]) dfs(y), Fmin(low[x], low[y]);
            else if (inSt[y]) Fmin(low[x], dfn[y]);
        if (low[x] == dfn[x])
        {
            ++N;
            for (int u = -1; u != x; )
                inSt[u = st[tp--]] = false, bel[u] = N;
        }
    }
    bool tarjan(int n)
    {
        memset(dfn, 0, n << 3);
        dcnt = N = 0;
        for (int i = 0; i < n * 2; i++)
            if (!dfn[i]) dfs(i);
        for (int i = 0; i < n; i++)
            if (bel[i << 1] == bel[i << 1 | 1])
                return false;
        return true;
    }
}
bool chk()
{
    SAT::init(n);
    for (int i = 1; i <= n; i++)
    {
        int o = col[i];
        SAT::add(id[e[i][0]][o ^ 1], id[e[i][1]][o]), SAT::add(id[e[i][0]][o ^ 1], id[e[i][2]][o]);
        SAT::add(id[e[i][1]][o ^ 1], id[e[i][0]][o]), SAT::add(id[e[i][1]][o ^ 1], id[e[i][2]][o]);
        SAT::add(id[e[i][2]][o ^ 1], id[e[i][0]][o]), SAT::add(id[e[i][2]][o ^ 1], id[e[i][1]][o]);
    }
    return !SAT::tarjan(n);
}
std::mt19937 rnd(time(0));
void mian()
{
    init();
    for (; ;)
    {
        for (int i = 1; i <= n; i++)
            col[i] = rnd() & 1;
        if (chk())
        {
            for (int i = 1; i <= n; i++)
                putchar("BW"[col[i]]);
            putchar('\n'); return ;
        }
    }  
}
int main()
{
    for (int Tcnt = read(); Tcnt--; ) mian();
    return 0;
}