自动搬运

查看原文

来自洛谷，原作者为

	George1123 **

搬运于2025-08-24 21:25:17，当前版本为作者最后更新于2019-12-14 21:40:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

${\color{#ee8800}\text{欢迎拜访我这个蒟蒻的博客}}$

P1456 【Monkey King】

此题算法:左偏树(可并堆)

左偏树手画图解

首先要理解正确题目：

有若干个猴盟，最强的猴子当大王。

刚开始猴子互不相识，每只猴子都是自己盟大王。

后来两只猴子起矛盾，各找大王来打架。

打完后大王被削，能力为原来的一半(下取整)。

打完后两猴群合并为同盟并从新选大王

此时输出新大王能力。

(手画勿吐槽)

此题用到左偏树，就是可并堆。

每盟猴子都是一个堆。

每次打架，先双方取大王。

然后，把两个大王削掉。

削完后选新大王(削一个大王如下)。

int weak(int x){//x为大王
	v[x]>>=1; //v[x]/=2;
	int rt=merge(ls[x],rs[x]); //合并子树，新根为rt
	ls[x]=rs[x]=dep[x]=0; //独立x
	return f[rt]=f[x]=merge(rt,x); //加入x，新根和x的祖先为总根
}

特殊情况，矛盾生于同盟间，不打，输出$-1$。

否则，将连个盟合并，皆大欢喜。

if(x==y) puts("-1"); //化解矛盾
else {
	int l=weak(x),r=weak(y); //大王:为啥受伤的总是我
	f[l]=f[r]=merge(l,r); //推举新王
	printf("%d\n",v[f[l]]); //输出新王
}

此外为了加速，$f[]$数组是祖先数组，类似并查集的路径压缩。

以下是代码+注释

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int ls[N],rs[N],f[N];
int v[N],dep[N];
int find(int x){ //路径压缩并查集find函数
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}
int merge(int x,int y){
	if(!x||!y) return x^y; //x+y x|y 都可以
	if(v[x]<v[y]) swap(x,y);
	rs[x]=merge(rs[x],y);
	f[rs[x]]=x;
	if(dep[ls[x]]<dep[rs[x]]) //左偏
		swap(ls[x],rs[x]);
	dep[x]=dep[ls[x]]+1;
	return x;
}
int weak(int x){//x为大王
	v[x]>>=1; //v[x]/=2;
	int rt=merge(ls[x],rs[x]); //合并子树，新根为rt
	ls[x]=rs[x]=dep[x]=0; //独立x
	return f[rt]=f[x]=merge(rt,x); //加入x，新根和x的祖先为总根
}
void solve(){
	dep[0]=-1;
	for(int i=1;i<=n;i++){
		ls[i]=rs[i]=dep[i]=0;
		scanf("%d",v+i),f[i]=i; //并查集一样的初始化
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		x=find(x),y=find(y);
		// printf("%d %d\n",x,y);
		if(x==y) puts("-1");
		else {
			int l=weak(x),r=weak(y);
			f[l]=f[r]=merge(l,r);
			printf("%d\n",v[f[l]]);
		}
	}
}
int main(){
	while(scanf("%d",&n)==1) //多种测试数据
		solve();
	return 0;
}

题目中文翻译是孙悟空。

写题解不易，喜欢就点个赞吧。

谢谢大家! !