题解 P1456 【Monkey King】

· · 题解

{\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;
}

题目中文翻译是孙悟空。

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

谢谢大家! !