首页 > 代码库 > 【HAOI2008】排名系统
【HAOI2008】排名系统
【题目描述】
排名系统通常要应付三种请求：上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。当某个玩家上传自己最新的得分记录时，他原有的得分记录会被删除。为了减轻服务器负担，在返回某个区段内的排名记录时，最多返回10条记录。
【输入格式】
第一行是一个整数n（n>=10）表示请求总数目。接下来n行,每行包含了一个请求。请求的具体格式如下：
+Name Score 上传最新得分记录。Name表示玩家名字，由大写英文字母组成，不超过10个字符。Score为最多8位的正整数。
?Name 查询玩家排名。该玩家的得分记录必定已经在前面上传。
?Index 返回自第Index名开始的最多10名玩家名字。Index必定合法，即不小于1，也不大于当前有记录的玩家总数。
【输出格式】
对于?Name格式的请求，应输出一个整数表示该玩家当前的排名。
对于?Index格式的请求，应在一行中依次输出从第Index名开始的最多10名玩家姓名，用一个空格分隔。
【样例输入】
20
+ADAM 1000000 加入ADAM的得分记录
+BOB 1000000 加入BOB的得分记录
+TOM 2000000 加入TOM的得分记录
+CATHY 10000000 加入CATHY的得分记录
?TOM 输出TOM目前排名
?1 目前有记录的玩家总数为4，因此应输出第1名到第4名。
+DAM 100000 加入DAM的得分记录
+BOB 1200000 更新BOB的得分记录
+ADAM 900000 更新ADAM的得分记录（即使比原来的差）
+FRANK 12340000 加入FRANK的得分记录
+LEO 9000000 加入LEO的得分记录
+KAINE 9000000 加入KAINE的得分记录
+GRACE 8000000 加入GRACE的得分记录
+WALT 9000000 加入WALT的得分记录
+SANDY 8000000 加入SANDY的得分记录
+MICK 9000000 加入MICK的得分记录
+JACK 7320000 加入JACK的得分记录
?2 目前有记录的玩家总数为12，因此应输出第2名到第11名。
?5 输出第5名到第13名。
?KAINE 输出KAINE的排名
【样例输出】
2
CATHY TOM ADAM BOB
CATHY LEO KAINE WALT MICK GRACE SANDY JACK TOM BOB
WALT MICK GRACE SANDY JACK TOM BOB ADAM DAM
4
【时间限制】
1s
【数据范围】
20%数据满足N<=100
100%数据满足N<=250000
【题解】
平衡树+哈希
将名字存在哈希表中，每次新插入一条信息就现在哈希表中找看之前有没有记录，如果有就删除，然后插入。
但是有个问题，如果你要删的值和结点值相同但是姓名不同，你怎么知道要删左子树还是右子树？？
于是结点还要记录下每个记录时间，删除时只要时间和值相同就行了。
接下来就是平衡树的基本操作了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<cstdlib> 6 #include<ctime> 7 #include<algorithm> 8 using namespace std; 9 const int INF=985003; 10 int n,root,tot,len,head[INF+10]; 11 struct node1{int v,next,time;char ch[10];}hash[250010]; 12 struct node2{int v,time,fix,size,l,r; char ch[10];}tr[250010]; 13 void updata(int p) {tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+1;} 14 void lturn(int &p) {int c=tr[p].r; tr[p].r=tr[c].l; tr[c].l=p; tr[c].size=tr[p].size; updata(p); p=c;} 15 void rturn(int &p) {int c=tr[p].l; tr[p].l=tr[c].r; tr[c].r=p; tr[c].size=tr[p].size; updata(p); p=c;} 16 bool cmp(char a[],char b[]) {for(int i=1;i<max(strlen(a),strlen(b));i++) if(a[i]!=b[i]) return 0;return 1;} 17 int Hash(char ch[]) {int s=0; for(int i=1;i<strlen(ch);i++) {s*=27; s+=ch[i]-‘A‘+1; s%=INF;} return s;} 18 void insert(int &p,int v,int time,char ch[]) 19 { 20 if(!p) 21 { 22 p=++len; tr[p].size=1; tr[p].v=v; tr[p].time=time; tr[p].fix=rand(); 23 memcpy(tr[p].ch,ch,strlen(ch)); return; 24 } 25 tr[p].size++; 26 if(v<=tr[p].v) {insert(tr[p].l,v,time,ch); if(tr[p].fix>tr[tr[p].l].fix) rturn(p);} 27 else {insert(tr[p].r,v,time,ch); if(tr[p].fix>tr[tr[p].r].fix) lturn(p);} 28 } 29 void del(int &p,int v,int time) 30 { 31 if(v==tr[p].v) 32 { 33 if(time==tr[p].time) 34 { 35 if(tr[p].l*tr[p].r==0) p=tr[p].l+tr[p].r; 36 else if(tr[tr[p].l].fix<tr[tr[p].r].fix) {rturn(p); del(p,v,time);} 37 else {lturn(p); del(p,v,time);} 38 } 39 else if(time>tr[p].time) {tr[p].size--; del(tr[p].l,v,time);} 40 else {tr[p].size--; del(tr[p].r,v,time);} 41 } 42 else if(v<tr[p].v) {tr[p].size--; del(tr[p].l,v,time);} 43 else {tr[p].size--; del(tr[p].r,v,time);} 44 } 45 void work(char ch[],int x,int time) 46 { 47 int k=Hash(ch); int i=head[k]; 48 while(i) 49 { 50 if(cmp(hash[i].ch,ch)) 51 { 52 del(root,hash[i].v,hash[i].time); 53 hash[i].time=time; hash[i].v=x; 54 insert(root,x,time,ch); 55 return; 56 } 57 i=hash[i].next; 58 } 59 tot++; 60 hash[tot].time=time; hash[tot].v=x; 61 hash[tot].next=head[k]; head[k]=tot; 62 memcpy(hash[tot].ch,ch,strlen(ch)); 63 insert(root,x,time,ch); 64 } 65 int get(char ch[]) 66 { 67 int k=Hash(ch);int i=head[k]; 68 while(i) 69 { 70 if(cmp(hash[i].ch,ch))return i; 71 i=hash[i].next; 72 } 73 } 74 int rank(int p,int v,int time) 75 { 76 if(p==0) return 0; 77 if(tr[p].v==v) 78 { 79 if(tr[p].time==time) return tr[tr[p].r].size+1; 80 else if(time<tr[p].time) return rank(tr[p].r,v,time); 81 else return tr[tr[p].r].size+1+rank(tr[p].l,v,time); 82 } 83 else if(v>tr[p].v) return rank(tr[p].r,v,time); 84 else return tr[tr[p].r].size+1+rank(tr[p].l,v,time); 85 } 86 void ask1(char ch[]) 87 { 88 int t=get(ch); 89 printf("%d\n",rank(root,hash[t].v,hash[t].time)); 90 } 91 int index(int k,int x) 92 { 93 if(tr[tr[k].r].size+1==x)return k; 94 else if(x<=tr[tr[k].r].size)return index(tr[k].r,x); 95 else return index(tr[k].l,x-tr[tr[k].r].size-1); 96 } 97 void ask2(char ch[]) 98 { 99 int s=0;100 for(int i=1;i<strlen(ch);i++){s*=10;s+=ch[i]-‘0‘;}101 for(int i=s;i<=tot&&i<=s+9;i++)102 {103 printf("%s",tr[index(root,i)].ch+1);104 if(i<tot&&i<s+9)printf(" ");105 }106 printf("\n");107 }108 int main()109 {110 freopen("cin.in","r",stdin);111 freopen("cout.out","w",stdout);112 scanf("%d",&n); char ch[11]; int x;113 for(int i=1;i<=n;i++)114 {115 scanf("%s",ch);116 if(ch[0]==‘+‘) {scanf("%d",&x); work(ch,x,i);}117 else if(ch[1]>=‘A‘&&ch[1]<=‘Z‘) ask1(ch);118 else ask2(ch);119 }120 return 0;121 }
【HAOI2008】排名系统
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。