cf1040E. Network Safety(并查集)

题意

题目链接

一张图，n个点，m条边，每个点有个权值x，x<=1e18。如果一条边的两个端点不一样，那么这条边是安全的，开始时所有边都是安全的。

现在有一个病毒y，病毒可以入侵任意的点，入侵一个点后的权值为(y^x)。

(S,y)表示病毒的权值为y，它只入侵了点集S中的点，整张图的边都是安全的。求出所有的(S,y)。

Sol

不算是特别难想的div2压轴题。。

题目中保证了任意两个节点互不相同，因此想让图不安全，对于$(A, x)$一定是存在 A内一点 ^ x = 与该点相邻点的权值

显然，对于每一条边我们可以求出对应的x。

刚开始我傻乎乎的以为任意两个节点之间对应的值都是不同的，但是这样肯定是错的

比如 101 ^ 1 = 100, 1011 ^ 1 = 1010

但就算有相同的也没关系。

考虑$x$的贡献，如果存在两个节点，假设其权值分别为a,b，满足a ^ x = b

那么该节点要么同时不出现，要么同时出现，也就相当于把这两个点看成了一个点

然后我在这里又掉了一次坑，题目中只是说了“刚开始是安全的”，我天真的以为是互不相同。。

这样的话，就有可能存在好多个点看成一个点的情况，直接用并查集维护即可

最终的答案 = $\sum_{k} 2^siz(k) + (2^k - cnt) * (2^n)$

cnt表示互不相同的x的数量

$siz(k)$表示把$x ^ k = y$的点全都缩起来后的总点数

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<map>

#include<vector>

#define Pair pair<int, int>

#define MP(x, y) make_pair(x, y)

#define fi first

#define se second

#define LL long long

using namespace std;

const int MAXN = 1e6 + , mod = 1e9 + ;

inline LL read() {

    char c = getchar(); LL x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * f;

}

int N, M, fa[MAXN];

LL po[MAXN], c[MAXN], K;

map<LL, vector<Pair> >mp;

int find(int x) {

    return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);

}

main() {

    N = read(); M = read(); K = read();

    po[] = ;

    for(int i = ; i <= N; i++) c[i] = read();

    for(int i = ; i <= max((LL)N, K); i++) po[i] = (1ll *  * po[i - ]) % mod;

    for(int i = ; i <= M; i++) {

        int x = read(), y = read();

        mp[c[x] ^ c[y]].push_back(MP(x, y));

    }

    LL ans = ;

    map<LL, vector<Pair> >::iterator it;

    for(int i = ; i <= N; i++) fa[i] = i;

    for(it = mp.begin(); it != mp.end(); it++) {

        LL val = it -> first;

        vector<Pair> now = it -> second;

        vector<int> res;

        for(int i = ; i < now.size(); i++) {

            int fx = find(now[i].fi), fy = find(now[i].se);

            res.push_back(fx); res.push_back(fy);

            if(fx == fy) continue;

            fa[fx] = fy;

        }

        for(int i = ; i < res.size(); i++) fa[res[i]] = res[i];

        (ans += po[tot]) %= mod;

    }

    printf("%I64d", (ans + 1ll * (po[K] - mp.size()) * po[N] % mod) % mod);

    return ;

}

巴特西

cf1040E. Network Safety(并查集)

题意

Sol

最新文章

热门文章