[bzoj3714]:[PA2014]Kuglarz

Description

魔术师的桌子上有n个杯子排成一行,编号为1,2,…,n,其中某些杯子底下藏有一个小球,如果你准确地猜出是哪些杯子,你就可以获得奖品。花费c_ij元,魔术师就会告诉你杯子i,i+1,…,j底下藏有球的总数的奇偶性。
采取最优的询问策略,你至少需要花费多少元,才能保证猜出哪些杯子底下藏着球?


Solution

用s[i]表示前i个杯子内的球的总数。
对于每次询问就是相当于求出了s[r]-s[l-1]的奇偶性。
我们已经知道了s[0]=0,那么对于每一个i,只要知道了s[i]-s[0]的奇偶性,就可以还原每个杯子的情况。
那么,对于s[r]和s[l]相当于在r和l-1上连一条边
求最小生成树即可


Code

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define re register int
using namespace std;

const int N=2029;
struct E{
    int u,v,val;    
}edg[N*N];
int father[N];
int cnt=0;
long long ans;

inline int read(){
    char c=getchar();int x=0,f=1;
    while(!isdigit(c)){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x*f;
}

inline bool cmp(E p,E q){
    return p.val<q.val;
}

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

inline void unionn(int m,int n){
    int r1=find(m),r2=find(n);
    if(r1==r2)return ;
    father[r1]=r2;
}

inline void add(int u,int v,int val){
    edg[++cnt]=((E){u,v,val});
}

int main(){
    int n=read();
    for(re i=1;i<=n;i++)
        father[i]=i;
    int tot=n;
    for(re i=1;i<=n;i++){
        for(re j=1;j<=tot;j++){
            int tmp=i+j-1;
            int v=read();
            add(tmp,i-1,v);
        }
        tot--;
    }
    sort(edg+1,edg+cnt+1,cmp);
    tot=0;
    int now=0;
    while(tot!=n){
        now++;
        if(find(edg[now].u)==find(edg[now].v))continue;
        unionn(edg[now].u,edg[now].v);
        tot++;
        ans+=edg[now].val;
    }   
    printf("%lld",ans);
    return 0;   
}