bzoj 3714 [ PA 2014 ] Kuglarz —— 思路+最小生成树

时间：2022-05-31 02:32:49

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3714

因为每个杯子下最多一个小球，所以从奇偶性就可以看出有没有球；

询问一段区间，等于知道一段区间的奇偶性；

设 s[i] 表示从 0 到 i 的小球总数的奇偶性，已知 s[0] = 0；

那么询问区间 [l,r] ，相当于知道了 s[l-1] ^ s[r]，那么知道其中一个就可以知道另一个了，而目标是知道所有 s[i] , 1 <= i <= n

所以把询问区间 [l,r] 看做是 l-1 到 r 的一条边，求最小生成树即可；

竟然跑了13秒才过，明明做法都一样...

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int const xn=;

int n,fa[xn];

ll ans;

struct N{int u,v,w;}ed[xn*xn];

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

int rd()

{

    int ret=,f=; char ch=getchar();

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

    while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

    return f?ret:-ret;

}

bool cmp(N x,N y){return x.w<y.w;}

int main()

{

    n=rd(); int ct=;

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

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

            ed[++ct].u=i-,ed[ct].v=j,ed[ct].w=rd();

    sort(ed+,ed+ct+,cmp);

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

    for(int i=;i<=ct;i++)

    {

        int x=find(ed[i].u),y=find(ed[i].v),w=ed[i].w;

        if(x==y)continue;

        fa[x]=y; ans+=w;

    }

    printf("%lld\n",ans);

    return ;

}

相关文章