讨论 / 提示一下
wish 2008-08-06 05:28:00
点我顶贴 收藏 删除
以前答应过的,如果到RQNOJ改版之后还没有人做出此题,就给出一点提示。

我不止一次说过此题是数据结构题,请查阅二叉查找树(BST)的相关内容,即可解出此题。

原先的积分悬赏依然有效

#1 DarkMaster@2008-07-31 20:04:00
回复 删除
我用hash表的。。
#2 wish@2008-07-31 20:06:00
回复 删除
这题跟 Hash 表有什么关系啊

再怎么想也想不到那个上面去啊

你 Hash 什么呢?

#3 DarkMaster@2008-07-31 20:08:00
回复 删除
既然你说是BST,那我知道了。。。
#4 wish@2008-07-31 20:08:00
回复 删除
静候佳音
#5 lizhixin@2008-08-06 05:28:00
回复 删除
program rq_218;

type poi=^rex;

rex=record

date,s:longint;

left,right:poi;

end;

var tree:poi;

i,j,k,n,m,gh,sam:longint;

rq:array[0..1000]of longint;

b:array[0..200000]of longint;

procedure buildtree(l,r:longint;var tre:poi);

var mid:longint;

begin

if l>r then exit;

mid:=(l+r) div 2;

new(tre);

tre^.date:=mid;

tre^.left:=nil;tre^.right:=nil;

if l=r then

begin

tre^.s:=1;

exit;

end;

buildtree(l,mid-1,tre^.left);

buildtree(mid+1,r,tre^.right);

tre^.s:=1;

if tre^.right<>nil then inc(tre^.s,tre^.right^.s);

if tre^.left<>nil then inc(tre^.s,tre^.left^.s);

end;

function cas(var tre:poi):longint;

begin

if tre=nil then exit(0);

if (tre^.left=nil) and (tre^.right=nil) then exit(1);

if tre^.left<>nil then cas:=tre^.left^.s+1

else cas:=tre^.s-tre^.right^.s;

end;

procedure del(key:longint;var tre:poi);

var q,p,r:poi;

begin

q:=nil;

p:=tre;

while key<>cas(p) do

begin

q:=p;

if key<cas(p) then p:=p^.left else

begin

key:=key-cas(p);

p:=p^.right;

end;

dec(q^.s);

end;

b[p^.date]:=i;

dec(p^.s);

if (p^.left=nil) and (p^.right=nil) then

begin

if q=nil then begin tre:=nil; exit; end;

if p=q^.left then q^.left:=nil else q^.right:=nil;

end;

if (p^.left=nil) xor (p^.right=nil) then

begin

if p^.left<>nil then r:=p^.left else r:=p^.right;

if q=nil then

begin

tre:=r;exit;

end;

if p=q^.left then q^.left:=r else q^.right:=r;

end;

if (p^.left<>nil) and (p^.right<>nil) then

begin

r:=p;

q:=p;

p:=p^.left;

while p^.right<>nil do

begin

dec(p^.s);

q:=p;

p:=p^.right;

end;

r^.date:=p^.date;

if p=q^.left then q^.left:=p^.left else q^.right:=p^.left;

end;

end;

begin

readln(n,m,gh);

k:=1;

for i:=2 to n do k:=(k+m-1) mod i+1;writeln(k);

for i:=1 to gh do readln(rq[i]);

buildtree(1,n,tree);

sam:=1;

for i:=1 to n do

begin

sam:=(sam+m-1-1) mod (n-i+1)+1;

del(sam,tree);

end;

for i:=1 to gh do writeln(b[rq[i]]);

end.

奖金!?太打击人了!

查看更多回复
提交回复