HDU3031 To Be Or Not To Be 左偏树 可并堆
2024-10-12 06:23:23
欢迎访问~原文出处——博客园-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\n",x[1],x[0]);
if (x[1]>=x[0])
v1++;
else
v0++;
}
puts(v1<v0?"I will be back!!":"Hahaha...I win!!");
return 0;
}
最新文章
- 分布式缓存技术memcached学习(三)——memcached内存管理机制
- 自定义NSLog
- h5的特点
- CSS 实现:父元素包含子元素,子元素垂直居中布局
- C# 获取某月的第一天和最后一天
- SSH登陆服务器的简单命令
- jbpmAPI-4
- iOS学习笔记(02) - 关键字 __kindof
- IOS开发,遇到的第一个bug
- D. Powerful array
- ecshop支付方式含线下自提
- 如何将外部数据库 导入到系统的SQL中
- oracle 列行转换
- time 命令
- listcard记录
- day05流程控制while循环 流程控制for循环
- PAT A1106 Lowest Price in Supply Chain (25 分)——树的bfs遍历
- iOS UILabel设置居上对齐,居中对齐,居下对齐
- [kx]宇宙-银河
- 【ActiveMQ入门-9】ActiveMQ学习-与Spring集成2