acm兩個(gè)題目，hdoj1521&hdoj2795。
hdoj1521講的是一群猴子，他們每一個(gè)都有一個(gè)力量值。剛剛開始猴子們是互相不認(rèn)識(shí)的。每一只猴子都可能和別的猴子吵架，當(dāng)吵架的時(shí)候，他們會(huì)把自己認(rèn)識(shí)的所有的人的老大(力量值最大的那只猴子，當(dāng)然包括自己)拉過來，兩只力量值最大的猴子會(huì)協(xié)調(diào)他們，然后這兩群猴子就認(rèn)識(shí)了。代價(jià)是兩只力量值最大的猴子減半。現(xiàn)在給出猴子們吵架的順序和每只猴子的力量值，輸出吵架之后那一堆猴子最大的力量值。題目詳見：
http://acm.hdu.edu.cn/showproblem.php?pid=1521。
看到這個(gè)題目首先想到了并查集。但是并查集重點(diǎn)描述的是每個(gè)節(jié)點(diǎn)之間的關(guān)系，或者說并查集的設(shè)計(jì)思想重點(diǎn)在節(jié)點(diǎn)關(guān)系上。如果要取得并查集中最大值，刪除最大值，想不到好的辦法。果斷看discuss,左偏樹+并查集。好吧。其實(shí)題目很明顯有幾種操作：取得最大值，刪除節(jié)點(diǎn)，合并集合。取得最大值和刪除節(jié)點(diǎn)是二叉堆的強(qiáng)項(xiàng)，但是二叉堆對(duì)于合并復(fù)雜度很差，O(N)，而本題中用到合并的次數(shù)很多。So，左偏樹。
左偏樹是個(gè)什么玩意呢？簡(jiǎn)單的說，就是可以合并的二叉樹，復(fù)雜度為O(logN),并且滿足堆的性質(zhì)。（重點(diǎn)在可以合并堆，實(shí)際上，左偏樹就是可并堆的一種實(shí)現(xiàn)，其余的實(shí)現(xiàn)還有Fib堆）。具體的介紹和證明在這篇論文上：左偏樹的特點(diǎn)及其應(yīng)用。百度之吧。大神已經(jīng)講得很清楚了。
代碼如下：
#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;
}
第二個(gè)題，并查集。
題目大意：開學(xué)了，有一個(gè)h*w黑板，上面是空的。現(xiàn)在有N張1*width的海報(bào)要貼在上面。規(guī)則是，行號(hào)越小越好，行號(hào)相同的情況下，越左邊越好。很久以前看過這個(gè)題目，那時(shí)候沒有好好想。誤以為是個(gè)二維線段樹巴拉巴拉的。。。現(xiàn)在想想，其實(shí)黑板的每一行只要用一個(gè)數(shù)組記錄下來就好，然后把所有的列組織成線段樹
記錄所有線段的最大的長(zhǎng)度。這樣這個(gè)題目就轉(zhuǎn)化成了線段樹最簡(jiǎn)單的那種形式：區(qū)間記錄一段節(jié)點(diǎn)信息，要注意的是，更新下層節(jié)點(diǎn)信息后要更改父節(jié)點(diǎn)的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：明天體側(cè)，求RP~