专栏文章

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

ccomplexor管理员
AT_arc161_e题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mipdzwle
此快照首次捕获于
2025/12/03 10:27
3 个月前
此快照最后确认于
2025/12/03 10:27
3 个月前
查看原文
很有意思的题。
首先考虑 spj 怎么实现，那么要解决两个问题：如何判断无解，如何判断解合法。
对于判断合法，假设 uu 操作后的颜色为 cc，相邻的三个点为 v1,v2,v3v_1,v_2,v_3，那么限制就是操作前这三个点中至少有两个颜色为 cc，或者说如果操作前 v1v_1 颜色不是 cc，那么 v2,v3v_2,v_3 的颜色必须是 cc，v2,v3v_2,v_3 操作前的颜色不是 cc 同理。
那么一个操作后的颜色序列合法，当且仅当不存在满足上述要求的操作前的颜色序列，这就是一个 2-SAT 问题了，可以 O(n)O(n) 解决。
对于判断无解，考虑如果无解，那么说明每个颜色序列都存在一个颜色序列操作一次后得到。这就构成了一个 {0,1}n\{0,1\}^n 到自己的满射，那么它肯定也是双射。但这是不可能的，因为对于 nn 个点全染黑 和 11 个点染白剩下 n−1n-1 个点染黑两种颜色序列，操作一次后的结果都是全黑，那么这不可能是单射，也就不是双射。所以本题不存在无解的情况。
接下来的做法很大胆，但绝大多数人可能都想过（不一定是对于这个题）：直接随机答案。
其实仔细想一想上面那个映射，大概可以感觉到有一种对称性，也就是有“一定比例”的颜色序列都不能被映射到。
具体一点，我们的想法是找到一个局部结构，如果这个局部中有 aa 种可能的颜色序列，只能映射到 b(b<a)b(b<a) 种颜色序列，那么对于全局大概就有 a−ba\frac{a-b}{a} 的序列可以作为答案。
考虑操作前的颜色序列。对于一个点 xx、距离 xx 为 11 的点 y1,y2,y3y_1,y_2,y_3、距离 xx 为 22 的点 z1,1,z1,2,z2,1,z2,2,z3,1,z3,2z_{1,1},z_{1,2},z_{2,1},z_{2,2},z_{3,1},z_{3,2}，只考虑 x,z1,1,z1,2,z2,1,z2,2,z3,1,z3,2x,z_{1,1},z_{1,2},z_{2,1},z_{2,2},z_{3,1},z_{3,2} 的颜色，其他点的颜色已经确定，那么有 27=1282^7=128 种颜色序列。而如果 (z1,1,z1,2),(z2,1,z2,2),(z3,1,z3,2)(z_{1,1},z_{1,2}),(z_{2,1},z_{2,2}),(z_{3,1},z_{3,2}) 中每对点的颜色都一样，那么不管 xx 的颜色是什么，操作一次后的颜色序列都一样。这说明这 128128 种操作前的序列至多对应到 128−8=120128-8=120 种可能的序列。所以感性理解就有 128−120128=116\frac{128-120}{128}=\frac{1}{16} 的序列是可以作为答案的。
这说明可以作为答案的颜色序列在 {0,1}n\{0,1\}^n 中的占比是不超过 O(1)O(1) 的，也就是期望随机不超过 O(1)O(1) 次就能得到答案，所以总复杂度是 O(n)O(n)。
如果用占比为 116\frac{1}{16} 计算，那么随机 300300 次还找不到答案的概率不到 4×10−94\times10^{-9}，即使是 10610^6 组测试数据找不到答案的概率也只有不到 0.0040.004。
事实上，可以证明答案在所有序列中的占比要比 116\frac{1}{16} 高得多，具体分析参考官方题解。
通过代码：
CPP
#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;
}

评论

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

正在加载评论...