欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - HDU3031
题意概括
喜羊羊和灰太狼要比赛。
有R次比赛。
对于每次比赛，首先输入n,m，n表示喜羊羊和灰太狼的这次比赛回合数，m表示一开始有m堆数字。
然后输入m个数，第i个(p[i])表示第i堆里面有多少个数。
接下来的m行，第i行有p[i]个数，分别表示第i堆数有哪些。
然后n回合，灰太狼和喜羊羊大战。
两人轮流操作，灰太狼先。
1) T K: 拿到第 k 堆所有数字
2) C: 喜羊羊和灰太狼手中最大的数字进行比较，赢得一方可以把对方的所有数字全部取过来。（牌数如果相同就什么也不干）
3) L: 失去手中最大的数字
4) A P: 手中最大的数字加上P
5) E Q: 手中最大的数字改为Q
然后，每次比赛结束，输出“灰太狼手中数字个数 : 喜羊羊手中数字个数”
所有比赛结束之后，统计灰太狼和喜羊羊赢的次数。
如果灰太狼的次数>=喜羊羊的次数，那么输出"Hahaha...I win!!"
否则输出"I will be back!!"
题解
这题就是题意比较难理解。
几乎是裸的可并堆，左偏树一发就可以了。
应该不需要解释吧。
不会的自己去看左偏树。
代码
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
const int M=105,N=M*10000;
int Case,n,m,p[M],root[M],v1=0,v0=0;
int ls[N],rs[N],npl[N],val[N],cnt;
void makeheap(int x,int v){
ls[x]=rs[x]=npl[x]=0;
val[x]=v;
}
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);
if (npl[rs[a]]>npl[ls[a]])
swap(rs[a],ls[a]);
npl[a]=npl[rs[a]]+1;
return a;
}
void pop(int &rt){
rt=merge(ls[rt],rs[rt]);
}
void change(int &rt,int v){
int x=merge(ls[rt],rs[rt]);
makeheap(rt,v);
rt=merge(rt,x);
}
int main(){
scanf("%d",&Case);
while (Case--){
cnt=0;
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
scanf("%d",&p[i]);
memset(root,0,sizeof root);
for (int i=1;i<=m;i++)
for (int j=1,x;j<=p[i];j++){
scanf("%d",&x);
makeheap(++cnt,x);
root[i]=merge(root[i],cnt);
}
int x[2],rt[2];
memset(rt,0,sizeof rt);
memset(x,0,sizeof x);
for (int i=1;i<=n;i++){
char op[2];
int a;
scanf("%s",op);
if (op[0]=='T'){
scanf("%d",&a);
rt[i&1]=merge(rt[i&1],root[a]);
x[i&1]+=p[a];
}
if (op[0]=='C'){
if (val[rt[0]]==val[rt[1]])
continue;
if (val[rt[0]]>val[rt[1]]){
x[0]+=x[1];
x[1]=0;
rt[0]=merge(rt[0],rt[1]);
rt[1]=0;
}
else {
x[1]+=x[0];
x[0]=0;
rt[1]=merge(rt[1],rt[0]);
rt[0]=0;
}
}
if (op[0]=='L'){
pop(rt[i&1]);
x[i&1]--;
}
if (op[0]=='A'){
scanf("%d",&a);
change(rt[i&1],val[rt[i&1]]+a);
}
if (op[0]=='E'){
scanf("%d",&a);
change(rt[i&1],a);
}
}
printf("%d:%d
",x[1],x[0]);
if (x[1]>=x[0])
v1++;
else
v0++;
}
puts(v1<v0?"I will be back!!":"Hahaha...I win!!");
return 0;
}