bzoj1455 羅馬游戲
Description
羅馬皇帝很喜歡玩殺人游戲。 他的軍隊(duì)里面有n個(gè)人宇驾，每個(gè)人都是一個(gè)獨(dú)立的團(tuán)倍靡。最近舉行了一次平面幾何測(cè)試，每個(gè)人都得到了一個(gè)分?jǐn)?shù)课舍。 皇帝很喜歡平面幾何塌西，他對(duì)那些得分很低的人嗤之以鼻。他決定玩這樣一個(gè)游戲筝尾。 它可以發(fā)兩種命令： 1. Merger(i, j)捡需。把i所在的團(tuán)和j所在的團(tuán)合并成一個(gè)團(tuán)。如果i, j有一個(gè)人是死人筹淫，那么就忽略該命令站辉。 2. Kill(i)。把i所在的團(tuán)里面得分最低的人殺死损姜。如果i這個(gè)人已經(jīng)死了饰剥，這條命令就忽略。 皇帝希望他每發(fā)布一條kill命令摧阅，下面的將軍就把被殺的人的分?jǐn)?shù)報(bào)上來汰蓉。（如果這條命令被忽略，那么就報(bào)0分）
Input
第一行一個(gè)整數(shù)n（1<=n<=1000000）棒卷。n表示士兵數(shù)古沥，m表示總命令數(shù)瘸右。 第二行n個(gè)整數(shù)，其中第i個(gè)數(shù)表示編號(hào)為i的士兵的分?jǐn)?shù)岩齿。（分?jǐn)?shù)都是[0..10000]之間的整數(shù)） 第三行一個(gè)整數(shù)m(1<=m<=100000) 第3+i行描述第i條命令太颤。命令為如下兩種形式： 1. M i j 2. K i
Output
如果命令是Kill，對(duì)應(yīng)的請(qǐng)輸出被殺人的分?jǐn)?shù)盹沈。（如果這個(gè)人不存在龄章，就輸出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;//成為根節(jié)點(diǎn)
}
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;//成為根節(jié)點(diǎn)
}
}
}
}
https://vjudge.net/problem/HDU-1512
題意：有n個(gè)猴子乞封，一開始每個(gè)猴子只認(rèn)識(shí)自己做裙。每個(gè)猴子有一個(gè)力量值，力量值越大表示這個(gè)猴子打架越厲害肃晚。如果2個(gè)猴子不認(rèn)識(shí)锚贱，他們就會(huì)找他們認(rèn)識(shí)的猴子中力量最大的出來單挑，單挑不論輸贏关串，單挑的2個(gè)猴子力量值減半拧廊，這2撥猴子就都認(rèn)識(shí)了，不打不相識(shí)嘛〗蓿現(xiàn)在給m組詢問吧碾，如果2只猴子相互認(rèn)識(shí)，輸出-1墓卦，否則他們各自找自己認(rèn)識(shí)的最牛叉的猴子單挑倦春，求挑完后這撥猴子力量最大值。
題解 ：左偏樹+并查集
#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;//因?yàn)橐獣簳r(shí)刪掉根，所以左右子樹先作為根
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
題意：喜羊羊和灰太狼比較所持有的卡片的大小忠怖，每張卡片上都有一定的點(diǎn)數(shù)添履，有5種操作，如下：
- T K: 拿到第 k 堆所有牌
- C: 喜羊羊和灰太狼手中最大的牌進(jìn)行比較脑又，贏得一方可以把對(duì)方的所有牌全部取過來
- L: 失去手中最大的一張牌
- A P: 手中最大的牌點(diǎn)數(shù)加上P
- E Q: 手中最大的牌點(diǎn)數(shù)改為Q點(diǎn)
共有R輪比賽暮胧，每輪都是雙方輪流操作，灰太狼先抽问麸，最后輸出輸贏即可往衷。
#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");
}
