CodeForces 959E Mahmoud and Ehab and the xor-MST (MST+找规律)

题目大意：

给定一个数n，代表有一个0~n-1的完全图，该图中所有边的边权为两端点的异或值，求这个图的MST的值。

解题分析：

数据较大，$10^{12}$个点的完全图，然后异或又暂时推不出什么性质，所以先起手Kruskal打一张小数据完全图的MST的表，发现规律其实还是蛮好找的。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+;

int fa[N],cnt,ncase;

struct Edge{ int u,v,w;

    bool operator < (const Edge &tmp)const{

        return w<tmp.w;

    }

}e[N];

map<int,int>mpa;

inline void add(int u,int v,int w){

    e[++cnt]=(Edge){u,v,w};

}

inline int find(int &x){

    while(x!=fa[x])

        x=fa[x]=fa[fa[x]];

}

inline void Kruskal(){

    sort(e+,e++cnt);

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

        int u=e[i].u,v=e[i].v;

        find(u);find(v);

        if(u!=v){

            fa[v]=u;

            printf("%dth edge , w=%d\n",++ncase,e[i].w);

            mpa[e[i].w]++;

        }

    }

    for(auto i:mpa){

        printf("%d have %d (num)\n",i.first,i.second);

    }

}

int main(){

    int n;cin>>n;

    ncase=;

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

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

        for(int j=i+;j<n;j++){

            add(i,j,i^j);

        }

    }

    Kruskal();

}

打表

然后根据规律就可以快速求解了。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main(){

    ll n,ans,w=;

    scanf("%lld",&n);

    while(n>){

        ans+=w*(n>>);  //(n>>1)代表边数,w代表权值

        w<<=;

        n-=n>>;

    }

    cout<<ans<<endl;

}

巴特西

CodeForces 959E Mahmoud and Ehab and the xor-MST (MST+找规律)

最新文章

热门文章