欢迎访问~原文出处——博客园-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;
}

  

最新文章

  1. 分布式缓存技术memcached学习(三)——memcached内存管理机制
  2. 自定义NSLog
  3. h5的特点
  4. CSS 实现:父元素包含子元素,子元素垂直居中布局
  5. C# 获取某月的第一天和最后一天
  6. SSH登陆服务器的简单命令
  7. jbpmAPI-4
  8. iOS学习笔记(02) - 关键字 __kindof
  9. IOS开发,遇到的第一个bug
  10. D. Powerful array
  11. ecshop支付方式含线下自提
  12. 如何将外部数据库 导入到系统的SQL中
  13. oracle 列行转换
  14. time 命令
  15. listcard记录
  16. day05流程控制while循环 流程控制for循环
  17. PAT A1106 Lowest Price in Supply Chain (25 分)——树的bfs遍历
  18. iOS UILabel设置居上对齐,居中对齐,居下对齐
  19. [kx]宇宙-银河
  20. 【ActiveMQ入门-9】ActiveMQ学习-与Spring集成2

热门文章

  1. axios - 基于 Promise 的 HTTP 异步请求库
  2. MySql 安装与使用图文教程
  3. Navicat Premium连接各种数据库
  4. Shiro+Spring+SpringMVC+Mybatis整合
  5. tidb 架构 ~Tidb学习系列(2)
  6. 批量下载Coursera及其他场景上的文件
  7. 解决Centos下yum无法更新
  8. Debian 安装配置(包括kdevelop)
  9. string替换字符串,路径的斜杠替换为下划线
  10. 【转】linux的特殊符号与正则表达式