acm两个题目，hdoj1521&hdoj2795。
hdoj1521讲的是一群猴子，他们每一个都有一个力量值。刚刚开始猴子们是互相不认识的。每一只猴子都可能和别的猴子吵架，当吵架的时候，他们会把自己认识的所有的人的老大(力量值最大的那只猴子，当然包括自己)拉过来，两只力量值最大的猴子会协调他们，然后这两群猴子就认识了。代价是两只力量值最大的猴子减半。现在给出猴子们吵架的顺序和每只猴子的力量值，输出吵架之后那一堆猴子最大的力量值。题目详见：
http://acm.hdu.edu.cn/showproblem.php?pid=1521。
看到这个题目首先想到了并查集。但是并查集重点描述的是每个节点之间的关系，或者说并查集的设计思想重点在节点关系上。如果要取得并查集中最大值，删除最大值，想不到好的办法。果断看discuss,左偏树+并查集。好吧。其实题目很明显有几种操作：取得最大值，删除节点，合并集合。取得最大值和删除节点是二叉堆的强项，但是二叉堆对于合并复杂度很差，O(N)，而本题中用到合并的次数很多。So，左偏树。
左偏树是个什么玩意呢？简单的说，就是可以合并的二叉树，复杂度为O(logN),并且满足堆的性质。（重点在可以合并堆，实际上，左偏树就是可并堆的一种实现，其余的实现还有Fib堆）。具体的介绍和证明在这篇论文上：左偏树的特点及其应用。百度之吧。大神已经讲得很清楚了。
代码如下：
#include <stdio.h>
#include <string.h>
#define MAXN 500010
typedef struct
{
int l,r,d,strong;
int f;
}node;
node heap[MAXN];
void swap(int& a,int& b)
{
int tmp;
tmp = a;
a = b;
b = tmp;
}
int merge(int a,int b)
{
if(a == 0)
return b;
if(b == 0)
return a;
if(heap[a].strong < heap[b].strong)
swap(a,b);
int res = merge(b,heap[a].r);
heap[a].r = res;
heap[res].f = a;
if(heap[heap[a].l].d < heap[heap[a].r].d)
swap(heap[a].l,heap[a].r);
if(heap[a].r == 0)
heap[a].d = 0;
else
heap[a].d = heap[heap[a].r].d+1;
return a;
}
int findp(int i)
{
return i==heap[i].f?heap[i].f:findp(heap[i].f);
}
int pop(int n)
{
int l = heap[n].l;
int r = heap[n].r;
heap[n].f = n;
heap[n].l=heap[n].r=heap[n].d=0;
heap[l].f = l;
heap[r].f = r;
return merge(l,r);
}
int main()
{
int N,M;
while(scanf("%d",&N)!=EOF)
{
int i,a,b;
for(i=1;i<=N;i++)
{
heap[i].l=heap[i].r=heap[i].d=0;
heap[i].f = i;
scanf("%d",&heap[i].strong);
}
scanf("%d",&M);
for(i=0;i<M;i++)
{
scanf("%d%d",&a,&b);
int m = findp(a);
int n = findp(b);
if(m==n)
printf("-1\n");
else
{
heap[m].strong/=2;
heap[n].strong/=2;
a = pop(m);
a= merge(a,m);
b = pop(n);
b =merge(b,n);
int root = merge(a,b);
printf("%d\n",heap[findp(root)].strong);
}
}
}
return 0;
}
第二个题，并查集。
题目大意：开学了，有一个h*w黑板，上面是空的。现在有N张1*width的海报要贴在上面。规则是，行号越小越好，行号相同的情况下，越左边越好。很久以前看过这个题目，那时候没有好好想。误以为是个二维线段树巴拉巴拉的。。。现在想想，其实黑板的每一行只要用一个数组记录下来就好，然后把所有的列组织成线段树
记录所有线段的最大的长度。这样这个题目就转化成了线段树最简单的那种形式：区间记录一段节点信息，要注意的是，更新下层节点信息后要更改父节点的max值。
贴代码：
#include <stdio.h>
#define MAXN 1000000
#define max(a,b) a>b?a:b
typedef struct
{
int l,r,max,row;
}
node;
node data[MAXN];
int width,ROW;
void build(int i,int l,int r)
{
data[i].l = l;
data[i].r = r;
int mid = (l+r)/2;
data[i].max = width;
if(l<r)
{
build(2*i,l,mid);
build(2*i+1,mid+1,r);
}
else
{
data[i].row = ROW;
ROW++;
}
}
int query(int i,int l)
{
if(data[i].max<l)
return -1;
if(data[i].l == data[i].r)
{
data[i].max -= l;
data[i/2].max=max(data[i].max,data[i+1].max);
return data[i].row;
}
if(data[2*i].max>=l)
{
int res = query(2*i,l);
data[i].max=max(data[2*i].max,data[2*i+1].max);
return res;
}
else
{
int res = query(2*i+1,l);
data[i].max=max(data[2*i].max,data[2*i+1].max);
return res;
}
}
int main()
{
int h,w,n,i,tmp;
while(scanf("%d%d%d",&h,&w,&n)!=EOF)
{
ROW = 1;
width = w;
if(h>210000)
h = 210000;
build(1,1,h);
for(i=0;i<n;i++)
{
scanf("%d",&tmp);
printf("%d\n",query(1,tmp));
}
}
return 0;
}
左偏树的论文还没做证明。留着。
PSS：明天体侧，求RP~