NOI 2006 — 生日快乐(happybirthday)
这道困扰了我许久的题目,终于被我过掉了…
话说当时觉得这道题太难写,于是一直没敢写…
然后呢,现在Splay写熟悉了,正好FNOI做这道题,于是咬咬牙开始写.
这个东西的调试实在是太恶心人了,不过还好,在用尽方法把file of integer转成text之后,终于能调试了…
写错了两个地方,一个是如果刚插入一个人有x个果冻,而要吃掉的那包也有x个果冻,这是我会把刚插入的那个人的果冻吃掉…加了个小判断搞掉.
第二个是,friendID变量用重了…把一些改成了friendID_,过掉~
程序写的不是太恶心.
用object写的,然后速度有些慢.于是删了object,加上inline,速度快了些.偶然删去了inline,速度竟然更快!
想起了HopCroft那个问题…现在还不知道怎么回事,等着周源来问他…
{
生日快乐; happybirthday; NOI 2006
- sqybi's code
- Splay
}
//for my winsty
program happybirthday_sqybi;
uses
happybirthday_p;
const
nn = 500000;
type
link = ^obj1;
obj1 = record
v: longint;
next: link;
end;
TSplayTree = object
data, father: array[1..nn*2]of longint;
size: array[0..nn*2]of longint;
son: array[0..1, 1..nn*2]of longint;
head: array[1..nn*2]of link;
root, num: longint;
procedure init;
procedure rotate(x, w: longint);
procedure splay(x, y: longint);
procedure addNode(x, y, z, id: longint);
procedure insert(x, y, id: longint);
procedure delete(x: longint);
function find(x, y: longint): longint;
function rank(x, y: longint; var id: longint): longint;
end;
var
x, y, friendID, friendID_, p: longint;
f: boolean;
tree: TSplayTree;
procedure TSplayTree.init;
begin
root := 0;
num := 0;
end;
procedure TSplayTree.rotate(x, w: longint);
var
y, z: longint;
begin
y := father[x];
z := size[y] - size[son[0, y]] - size[son[1, y]];
son[1-w, y] := son[w, x];
if son[w, x] <> 0 then father[son[w, x]] := y;
father[x] := father[y];
if father[y] <> 0 then
if y = son[0, father[y]] then
son[0, father[y]] := x
else
son[1, father[y]] := x;
father[y] := x;
son[w, x] := y;
size[x] := size[y];
size[y] := z + size[son[0, y]] + size[son[1, y]];
end;
procedure TSplayTree.splay(x, y: longint);
begin
while father[x] <> y do begin
if father[father[x]] <> y then begin
if father[x] = son[0, father[father[x]]] then begin
if x = son[0, father[x]] then begin
rotate(father[x], 1);
rotate(x, 1);
end
else begin
rotate(x, 0);
rotate(x, 1);
end;
end
else begin
if x = son[1, father[x]] then begin
rotate(father[x], 0);
rotate(x, 0);
end
else begin
rotate(x, 1);
rotate(x, 0);
end;
end;
end
else
if x = son[0, father[x]] then
rotate(x, 1)
else
rotate(x, 0);
end;
if y = 0 then root := x;
end;
procedure TSplayTree.addNode(x, y, z, id: longint);
var
work: link;
begin
data[x] := y;
father[x] := z;
size[x] := 1;
son[0, x] := 0;
son[1, x] := 0;
new(work);
work^.v := id;
work^.next := nil;
head[x] := work;
end;
procedure TSplayTree.insert(x, y, id: longint);
var
work: link;
begin
if root = 0 then begin
inc(num);
addNode(num, y, 0, id);
root := num;
exit;
end;
repeat
inc(size[x]);
if y = data[x] then break;
if y < data[x] then begin
if son[0, x] = 0 then break;
x := son[0, x];
end
else begin
if son[1, x] = 0 then break;
x := son[1, x];
end;
until false;
if y = data[x] then begin
new(work);
work^.v := id;
work^.next := head[x];
head[x] := work;
end
else if y < data[x] then begin
inc(num);
addNode(num, y, x, id);
son[0, x] := num;
x := num;
end
else begin
inc(num);
addNode(num, y, x, id);
son[1, x] := num;
x := num;
end;
splay(x, 0);
end;
procedure TSplayTree.delete(x: longint);
var
y, z: longint;
work: link;
begin
splay(x, 0);
if size[x] - size[son[0, x]] - size[son[1, x]] > 1 then begin
dec(size[x]);
work := head[x];
head[x] := work^.next;
dispose(work);
exit;
end;
dispose(head[x]);
if son[0, x] = 0 then begin
if son[1, x] = 0 then begin
init;
exit;
end;
root := son[1, x];
father[son[1, x]] := 0;
exit;
end;
y := son[0, x];
while son[1, y] <> 0 do y := son[1, y];
splay(y, x);
z := size[y] - size[son[0, y]] - size[son[1, y]];
father[y] := 0;
root := y;
son[1, y] := son[1, x];
if son[1, x] <> 0 then father[son[1, x]] := y;
size[y] := z + size[son[0, y]] + size[son[1, y]];
end;
function TSplayTree.find(x, y: longint): longint;
begin
repeat
if y = data[x] then break;
if y < data[x] then
x := son[0, x]
else
x := son[1, x];
until false;
splay(x, 0);
find := size[son[0, x]] + 1;
end;
function TSplayTree.rank(x, y: longint; var id: longint): longint;
begin
id := -1;
rank := 0;
if (y < 1) or (y > size[root]) then exit;
repeat
if size[son[0, x]] >= y then
x := son[0, x]
else if size[x] - size[son[1, x]] >= y then begin
id := head[x]^.v;
if id = friendID then
id := head[x]^.next^.v;
rank := x;
break;
end
else begin
y := y - (size[x] - size[son[1, x]]);
x := son[1, x];
end;
until false;
splay(x, 0);
end;
begin
init;
tree.init;
friendID := 0;
while getpresent(x, y, f) do begin
inc(friendID);
tree.insert(tree.root, x, friendID);
p := tree.find(tree.root, x);
p := tree.rank(tree.root, p-y+ord(f)*2*y, friendID_);
if friendID_ <> -1 then begin
tree.delete(p);
if tree.data[p] > 1 then
tree.insert(tree.root, tree.data[p]-1, friendID_);
end;
tell(friendID_);
end;
end.
阅读(122 次)