把i所在的团和j所在的团合并成三个团,若是贰个猴子不认识

Monkey King

 ZOJ –
2334 

标题疏忽:有n个猴子,一起头每一个猴子只认识自身。每一个猴子有3个力量值,力量值越大表示那一个猴子打架越厉害。借使3个猴子不认得,他们就会找他俩认识的猴子中力量最大的出来单挑,单挑不论输赢,单挑的二个猴子力量值减半,这2拨猴子就都认识了,不打不相识嘛。以往给m组询问,假如二只猴子彼此认识,输出-1,不然他们各自找本身认识的最牛叉的猴子单挑,求挑完后那拨猴子力量最大值。

/*
    左偏树模板题,包括合并,删除操作 
*/
#include<iostream>
#include<cstdio>
#define maxn 100010
using namespace std;
int n,m;
struct node{
    int v,dis,l,r,f;
}heap[maxn];
int find(int x){
    if(x==heap[x].f)return x;
    return heap[x].f=find(heap[x].f);
}
int merge(int a,int b){//返回的是合并完之后根节点的编号 
    if(a==0)return b;
    if(b==0)return a;
    if(heap[a].v<heap[b].v)swap(a,b);
    heap[a].r=merge(heap[a].r,b);
    heap[heap[a].r].f=a;
    if(heap[heap[a].l].dis<heap[heap[a].r].dis)swap(heap[a].l,heap[a].r);
    if(heap[a].r==0)heap[a].dis=0;
    else heap[a].dis=heap[heap[a].r].dis+1;
    return a;
}
int pop(int a){
    int l=heap[a].l;
    int r=heap[a].r;
    heap[l].f=l;
    heap[r].f=r;
    heap[a].l=heap[a].r=heap[a].dis=0;
    return merge(l,r);
}
void work(){
    for(int i=1;i<=n;i++){
        scanf("%d",&heap[i].v);
        heap[i].dis=heap[i].l=heap[i].r=0;
        heap[i].f=i;//并查集序号 
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int a,b;scanf("%d%d",&a,&b);
        int aa=find(a),bb=find(b);
        if(aa==bb){puts("-1");continue;}
        heap[aa].v/=2;int u1=pop(aa);u1=merge(u1,aa);//修改权值(先删除,后加入) 
        heap[bb].v/=2;int u2=pop(bb);u2=merge(u2,bb);
        printf("%d\n",heap[merge(u1,u2)].v);
    }
}
int main(){
    freopen("Cola.txt","r",stdin);
    while(scanf("%d",&n)!=EOF)work();
    return 0;
}

 

bzoj1455 杜塞尔多夫娱乐
Description
杜塞尔多夫圣上很欣赏玩杀人游戏。
他的部队内部有n个人,每种人都以贰个独立的团。近来实行了3回平面几何测试,每个人都拿走了1个分数。
天子很欣赏平面几何,他对这多少个得分非常低的人置之不顾。他控制玩那样八个嬉戏。
它能够发三种命令: 1. Merger(i,
j)。把i所在的团和j所在的团合并成2个团。要是i,
j有1人是死人,那么就忽略该命令。 2.
Kill(i)。把i所在的团里面得分最低的人杀死。假若i这厮早就死了,这条命令就马虎。
太岁希望他每公布一条kill命令,上面包车型大巴老将就把被杀的人的分数报上来。(若是那条命令被忽略,那么就报0分)
Input
第①行1个整数n(1<=n<=1000000)。n表示士兵数,m表示总命令数。
第②行n个整数,个中第i个数表示编号为i的大兵的分数。(分数都以[0..10000]中间的整数)
第③行三个整数m(1<=m<=一千00)
第2+i行描述第i条命令。命令为如下二种样式: 1. M i j 2. K i
Output
比方命令是Kill,对应的请输出被杀人的分数。(如果这厮不存在,就输出0)

#include<iostream>
#include<algorithm>
#include<string.h>
#include<cstdio>
using namespace std;
const int maxn=1000010;
int n,m;
int fa[maxn],die[maxn];
int val[maxn],lef[maxn],rig[maxn],dis[maxn];
int father(int u)
{
    while(fa[u]!=u)
    {
        fa[u]=fa[fa[u]];
        u=fa[u];
    }
    return u;
}
int merge(int x,int y)
{
    if(!x) return y;
    if(!y) return x;
    if(val[x]>val[y]) swap(x,y);
    rig[x]=merge(rig[x],y);
    fa[rig[x]]=x;//并查
    if(dis[rig[x]]>dis[lef[x]]) swap(lef[x],rig[x]);
    dis[x]=dis[rig[x]]+1;//如果x没有右孩子,则rig[x]=0,而dis[0]=-1,则dis[x]=0;
    return x;
}
int main()
{
    int u,v,fu,fv,t;
      scanf("%d",&n);
      for(int i=1;i<=n;i++)
      {
          scanf("%d",val+i);
          fa[i]=i;
          dis[i]=0;
          die[i]=0;
          lef[i]=0;
          rig[i]=0;
      }
      dis[0]=-1;
      char op[3];
      scanf("%d",&m);
      for(int i=1;i<=m;i++)
      {
          scanf("%s",op);
          if(op[0]=='M')
          {
            scanf("%d%d",&u,&v);
            if(die[u]||die[v]) continue;
            fu=father(u);
            fv=father(v);
            if(fu==fv) continue;
            t=merge(fu,fv);
            fa[t]=t;//成为根节点
          }
          else{

            scanf("%d",&v);
            if(die[v]) {
                printf("0\n");
            }
            else{
                fv=father(v);
                die[fv]=1;
                printf("%d\n",val[fv]);
                t=merge(lef[fv],rig[fv]);
                fa[t]=t;//成为根节点
            }
          }
      }
}

https://vjudge.net/problem/HDU-1512
题意:有n个猴子,一起始各样猴子只认识自个儿。每一种猴子有2个力量值,力量值越大表示那么些猴子打架越厉害。假使1个猴子不认得,他们就会找他们认识的猴子中力量最大的出来单挑,单挑不论输赢,单挑的1个猴子力量值减半,那2拨猴子就都认识了,不打不相识嘛。以往给m组询问,假诺1只猕猴互相认识,输出-1,不然他们分别找本身认识的最牛叉的猴子单挑,求挑完后那拨猴子力量最大值。
题解 :左偏树+并查集

#include<iostream>
#include<algorithm>
#include<string.h>
#include<cstdio>
using namespace std;
const int maxn=100010;
int n,m;
int fa[maxn];
int val[maxn],lef[maxn],rig[maxn],dis[maxn];
int father(int u)
{
    while(fa[u]!=u)
    {
        fa[u]=fa[fa[u]];
        u=fa[u];
    }
    return u;
}
int merge(int &x,int &y)
{
    if(!x) return y;
    if(!y) return x;
    if(val[x]<val[y]) swap(x,y);
    rig[x]=merge(rig[x],y);
    fa[rig[x]]=x;//并查!
    if(dis[rig[x]]>dis[lef[x]]) swap(lef[x],rig[x]);
    dis[x]=dis[rig[x]]+1;//如果x没有右孩子,则rig[x]=0,而dis[0]=-1,则dis[x]=0;
    return x;
}
int pop(int &t)
{
    int l=lef[t],r=rig[t];
    fa[l]=l;//因为要暂时删掉根,所以左右子树先作为根
    fa[r]=r;
    lef[t]=rig[t]=dis[t]=0;
    return merge(l,r);
}
int main()
{
    int u,v,fu,fv,a,b,c;
    while(scanf("%d",&n)!=EOF){

      for(int i=1;i<=n;i++)
      {
          scanf("%d",val+i);
          fa[i]=i;
          dis[i]=0;
          lef[i]=0;
          rig[i]=0;
      }
      dis[0]=-1;
      scanf("%d",&m);
      for(int i=1;i<=m;i++)
      {
            scanf("%d%d",&u,&v);
            fu=father(u);
            fv=father(v);
            if(fu==fv)
            {
                printf("-1\n");
                continue;
            }
            val[fu]>>=1;
            val[fv]>>=1;
            a=pop(fu);
            b=pop(fv);
            c=merge(a,b);
            c=merge(fu,c);
            c=merge(fv,c);
            printf("%d\n",val[c]);
      }
    }
}

https://vjudge.net/problem/HDU-3031
题意:喜羊羊和灰太狼比较所怀有的卡片的深浅,每张卡片上都有早晚的罗列,有5种操作,如下:

  1. T K: 得到第 k 堆全部牌
  2. C:
    喜羊羊和灰太狼手中最大的牌实行相比较,赢得一方得以把对方的全体牌全体取过来
  3. L: 失去手中最大的一张牌
  4. A P: 手中最大的牌点数加上P
  5. E Q: 手中最大的牌点数改为Q点
    共有卡宴轮竞赛,每轮都以双方轮流操作,灰太狼先抽,最终输出输赢即可。

#include<algorithm>
#include<string.h>
#include<cstdio>
using namespace std;
const int maxn=1000010;
int val[maxn],lef[maxn],rig[maxn],dis[maxn];
int merge(int &x,int &y)
{
    if(!x) return y;
    if(!y) return x;
    if(val[x]<val[y]) swap(x,y);
    rig[x]=merge(rig[x],y);
    if(dis[lef[x]]<dis[rig[x]]) swap(lef[x],rig[x]);
    dis[x]=dis[rig[x]]+1;
    return x;
}
int pop(int &x)
{
    int l=lef[x],r=rig[x];
    lef[x]=rig[x]=dis[x]=0;
    return merge(l,r);
}
int main()
{
    char op[5];
    int sum[2],root[2],num[110],group[110],curr,v,cas,n,m;
    int Happy, Wolffy;
    Happy = Wolffy = 0;
    scanf("%d",&cas);
    while(cas--)
    {
        memset(group,0,sizeof(group));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
            scanf("%d",num+i);
        curr=1;
        dis[0]=-1;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=num[i];j++)
            {
                scanf("%d",&v);
                lef[curr]=rig[curr]=dis[curr]=0;
                val[curr]=v;
                group[i]=merge(group[i],curr);
                curr++;
            }
        }
        sum[0]=sum[1]=0;
        root[0]=root[1]=0;
        for(int i=0;i<n;i++)
        {
            scanf("%s",op);
            if(op[0]=='T')
            {
                scanf("%d",&v);
                root[i&1]=merge(root[i&1],group[v]);
                group[v]=0;
                sum[i&1]+=num[v];
                num[v]=0;
            }
            else if(op[0]=='C')
            {
                if(val[root[0]]>=val[root[1]])
                {
                    root[0]=merge(root[0],root[1]);
                    sum[0]+=sum[1];
                    root[1]=0;
                    sum[1]=0;
                }
                else
                {
                     root[1]=merge(root[0],root[1]);
                    sum[1]+=sum[0];
                    root[0]=0;
                    sum[0]=0;
                }
            }
             else if(op[0]=='L')
            {
                root[i&1]=pop(root[i&1]);
                sum[i&1]--;
            }
             else if(op[0]=='A')
            {
                scanf("%d",&v);
                val[root[i&1]]+=v;
            }
             else
            {
                scanf("%d",&v);
                int t=pop(root[i&1]);
                val[root[i&1]]=v;
                root[i&1]=merge(t,root[i&1]);
            }
        }
        printf("%d:%d\n",sum[0],sum[1]);
        if(sum[0]>=sum[1]) Wolffy++;
        else Happy++;
    }
    if(Wolffy>Happy) printf("Hahaha...I win!!\n");
    else printf("I will be back!!\n");
}

相关文章