HDU1512 ZOJ2334 Monkey King 左偏树

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解


题目传送门 - ZOJ2334

题目传送门 - HDU1512


题意概括

  在一个森林里住着N(N<=10000)只猴子。在一开始,他们是互不认识的。但是随着时间的推移,猴子们少不了争斗,但那只会发生在互不认识(认识具有传递性)的两只猴子之间。争斗时,两只猴子都会请出他认识的猴子里最强壮的一只(有可能是他自己)进行争斗。争斗后,这两只猴子就互相认识。每个猴子有一个强壮值,但是被请出来的那两只猴子进行争斗后,他们的强壮值都会减半(例如10会减为5,5会减为2)。现给出每个猴子的初始强壮值,给出M次争斗,如果争斗的两只猴子不认识,那么输出争斗后两只猴子的认识的猴子里最强壮的猴子的强壮值,否则输出 -1。


题解

  左偏树大力维护。

  找根就最暴力的来。


代码

#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
const int N=100005;
int n,m;
int fa[N],ls[N],rs[N],npl[N],val[N];
int getf(int k){
while (fa[k])
k=fa[k];
return k;
}
int merge(int a,int b){
if (!a||!b)
return a+b;
if (val[a]<val[b])
swap(a,b);
rs[a]=merge(rs[a],b);
fa[rs[a]]=a;
if (npl[rs[a]]>npl[ls[a]])
swap(rs[a],ls[a]);
npl[a]=npl[rs[a]]+1;
return a;
}
int weaken(int a){
fa[ls[a]]=fa[rs[a]]=0;
int b=merge(ls[a],rs[a]);
fa[a]=ls[a]=rs[a]=npl[a]=0;
val[a]>>=1;
return merge(a,b);
}
int main(){
while (~scanf("%d",&n)){
for (int i=1;i<=n;i++){
scanf("%d",&val[i]);
fa[i]=ls[i]=rs[i]=npl[i]=0;
}
scanf("%d",&m);
while (m--){
int a,b;
scanf("%d%d",&a,&b);
a=getf(a),b=getf(b);
if (a==b){
puts("-1");
continue;
}
a=weaken(a);
b=weaken(b);
printf("%d\n",max(val[a],val[b]));
merge(a,b);
}
}
return 0;
}

  

上一篇:2018.12.30 bzoj3027: [Ceoi2004]Sweet(生成函数+搜索)


下一篇:2015.12.29~2015.12.30真题回顾!-- HTML5学堂