第二十三届全国信息学奥林匹克竞赛
NOI 2006
第一试
| 题目名称 | 生日快乐 |
| 可执行文件名 | happybirthday |
| 输入文件名 | N/A |
| 输出文件名 | N/A |
| 时限 | 4 秒 |
| 测试点数目 | 10 |
| 每测试点分值 | 10 |
| 是否有部分分 | 无 |
| 题目类型 | 交互 |
生日快乐
【任务描述】
今天是栋栋的生日，他邀请了N 个好友参加Party 。朋友们都知道，栋栋最喜欢吃果冻。因此, 每个朋友带来的生日礼物全是一包果冻.。
在每个朋友送他一包果冻的同时，栋栋还要这个朋友送他一个幸运号码L（1 ≤ L ≤ N）。然后栋栋会先把这包果冻放在一旁，并且把之前的所有果冻包按照果冻的数量从小到大排序（如果果冻数量相等，先后顺序任意）。接着，栋栋再把当前这包果冻插入到有序的果冻包队列中，使得这个队列仍然有序（如果存在其他的果冻包与该果冻包数量相等，则把该果冻包放在它们的前面）。完成这个操作后，栋栋就会进行如下操作：
“如果这个朋友是男生，栋栋会从他送的包的后一个包开始向后数L 个（该朋友的幸运号码），从那个包里取出一个果冻，吃掉。
“如果这个朋友是女生，栋栋会从她送的包的前一个包开始向前数L 个（该朋友的幸运号码），从那个包里取出一个果冻，吃掉。
栋栋实在是太粗心了，以至于他收完所有的礼物后，都不知道吃过哪些朋友的果冻，现在，他希望你帮他一下，当他每吃一个果冻后马上告诉他可能吃的是谁送的(由于排序不是确定的，所以栋栋只要你给他一种可能的答案就行了)。
这是一个交互式的题目，你必须调用库函数来完成所有操作而不能访问任何文件。
【数据规模和约定】
对于所有的数据，我们保证：1 ≤ n ≤ 500000，0 ≤ count ≤ 10^8 ，1 ≤ luckynumber ≤ n.在测试时，你的数据也应该满足我们的数据范围，否则有可能运行异常。
【题解】
平衡树的的典型应用。我这里对SBT(Size Balanced Tree)进行2处改写来做这题：首先是在Insert过程中返回插入节点的秩，这是一个顺便的改动，非常简单；再就是在Delete和Select的基础上改写出了SBT_Select_Delete，即选择指定秩的节点删除，并返回此节点。这个也不难，看看我的代码就知道了。只是注意，既然删除的节点要回收利用，那么从树中删除后就需要处理清楚size和ch[]域。
BTW，题目中给的count范围包括0，这是不负责任的。仔细想想就发现一旦出现这样的节点你就无法确定该如何处理了。当然了，评测时并没有给出这样的数据，否则鬼知道怎么处理呢。
时空开销：
代码：
#include "happybirthday_lib_c.cpp"
struct SBTNode{
SBTNode *ch[2];
long size, key, id;
SBTNode(long _key, long _id, long _size);
}NIL=SBTNode(0,0,0);
SBTNode::SBTNode(long _key, long _id, long _size=1){
key=_key,id=_id,size=_size;
ch[0]=ch[1]=&NIL;
}
typedef SBTNode* SBTree;
void SBT_Rotate(SBTree &x, bool flag){
SBTNode *y = x->ch[!flag];
x->ch[!flag]=y->ch[flag],y->ch[flag]=x;
y->size=x->size;
x->size=x->ch[0]->size+x->ch[1]->size+1;
x=y;
}
void SBT_Maintain(SBTree &T,bool flag){
if(T->ch[flag]->ch[flag]->size>T->ch[!flag]->size)
SBT_Rotate(T,!flag);
else if(T->ch[flag]->ch[!flag]->size>T->ch[!flag]->size)
SBT_Rotate(T->ch[flag],flag),SBT_Rotate(T,!flag);
else return;
SBT_Maintain(T->ch[0],0),SBT_Maintain(T->ch[1],1);
SBT_Maintain(T,0),SBT_Maintain(T,1);
}
long SBT_Insert(SBTree &T, SBTNode *toAdd){
if(T==&NIL){
T=toAdd;
return 1;
}else{
T->size++;
bool flag=toAdd->key>T->key;
long r=SBT_Insert(T->ch[flag],toAdd)+(flag?T->ch[0]->size+1:0);
SBT_Maintain(T,flag);
return r;
}
}
SBTNode *SBT_Select_Delete(SBTree &T,long i){
if(T==&NIL) return &NIL;
T->size--;
unsigned long r = T->ch[0]->size + 1;
if(i==r){
SBTNode *toDel = NULL;
if(T->ch[0]==&NIL||T->ch[1]==&NIL){
toDel=T;
T=T->ch[T->ch[1]!=&NIL];
}else{
toDel = SBT_Select_Delete(T->ch[1],1);
swap(T->key,toDel->key),swap(T->id,toDel->id);
}
toDel->ch[0]=toDel->ch[1]=&NIL;
toDel->size=1;
return toDel;
}
else return SBT_Select_Delete(T->ch[i>r],i>r?i-r:i);
}
int main(){
long c,l,r,id=1; bool isboy;
SBTNode *toEat; SBTree T=&NIL;
for(init();getpresent(c,l,isboy);id++){
SBTNode *toAdd = new SBTNode(c,id);
r = SBT_Insert(T,toAdd);
if(isboy) r+=l;
else r-=l;
if(r<=0||r>T->size) tell(-1);
else{
toEat = SBT_Select_Delete(T,r);
tell(toEat->id);
if(--toEat->key>0) SBT_Insert(T,toEat);
else delete toEat;
}
}
return 0;
}
P.S.有一件事情很郁闷，那就是……这题用不着平衡树-_-|||
因为数据都是random的，普通BST表现反倒会更好。。。（但是比赛时谁知道呢）
可能你对下面的文章也感兴趣：
