bzoj 1862/1056 [HAOI2008]排名系统,bzojhaoi2008【奥门永利误乐域】

hdu 4585 Shaolin,hdu4585shaolin

原题链接:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=46093

奥门永利误乐域 1 1
#include<cstdio> 2 #include<cstdlib> 3
#include<iostream> 4 #include<algorithm> 5 const int
Max_N = 101000; 6 const int INF = 0x7fffffff; 7 struct Node{ 8 int v,
id, s; 9 Node *ch[2]; 10 inline void 11 set(int _v = 0, int _id =
0, int _s = 0, Node *p = NULL){ 12 ch[0] = ch[1] = p; 13 v = _v,
id = _id, s = _s; 14 } 15 inline void push_up(){ 16 s = ch[0]->s

  • ch[1]->s + 1; 17 } 18 inline int cmp(int x) const{ 19 return x
    > v; 20 } 21 }; 22 struct SizeBalanceTree{ 23 Node *tail, *root,
    *null; 24 Node stack[Max_N]; 25 void init(){ 26 tail = &stack[0];
    27 null = tail++; 28 null->set(); 29 root = null; 30 } 31 inline Node
    *newNode(int v, int id){ 32 Node *p = tail++; 33 p->set(v, id, 1,
    null); 34 return p; 35 } 36 inline void rotate(Node* &x, int d){ 37
    Node *k = x->ch[!d]; 38 x->ch[!d] = k->ch[d]; 39
    k->ch[d] = x; 40 k->s = x->s; 41 x->push_up(); 42 x = k;
    43 } 44 inline void Maintain(Node* &x, int d){ 45 if (x->ch[d] ==
    null) return; 46 if (x->ch[d]->ch[d]->s >
    x->ch[!d]->s){ 47 rotate(x, !d); 48 } else if
    (x->ch[d]->ch[!d]->s > x->ch[!d]->s){ 49
    rotate(x->ch[d], d), rotate(x, !d); 50 } else { 51 return; 52 } 53
    Maintain(x, 0), Maintain(x, 1); 54 } 55 inline void insert(Node* &x,
    int v, int id){ 56 if (x == null){ 57 x = newNode(v, id); 58 return; 59
    } else { 60 x->s++; 61 int d = x->cmp(v); 62 insert(x->ch[d],
    v, id); 63 x->push_up(); 64 Maintain(x, d); 65 } 66 } 67 inline void
    insert(int v, int id){ 68 insert(root, v, id); 69 } 70 inline Node
    *select(Node *x, int v, int dx){ 71 Node *pre = null; 72 while (x !=
    null && x->v != v){ 73 int d = x->cmp(v); 74 if (d == !dx) pre =
    x; 75 x = x->ch[d]; 76 } 77 x = x->ch[dx]; 78 if (x == null){
    79 return pre; 80 } else { 81 while (x->ch[!dx] != null) x =
    x->ch[!dx]; 82 return x; 83 } 84 } 85 inline int calc(Node *r, int
    k) { 86 if (r == null) return INF; 87 return std::abs(r->v – k); 88 }
    89 inline void gogo(int id, int v){ 90 int ans = 0; 91 Node *k1 =
    select(root, v, 0); 92 Node *k2 = select(root, v, 1); 93 int d1 =
    calc(k1, v), d2 = calc(k2, v); 94 ans = d1 > d2 ? k2->id :
    k1->id; 95 printf(“%d %d\n”, id, ans); 96 } 97 }sbt; 98 int main(){
    99 #ifdef LOCAL 100 freopen(“in.txt”, “r”, stdin); 101
    freopen(“out.txt”, “w+”, stdout); 102 #endif 103 int n, id, v; 104
    while (~scanf(“%d”, &n) && n){ 105 sbt.init(); 106 sbt.insert((int)1e9,
    1); 107 for (int i = 0; i < n; i++){ 108 scanf(“%d %d”, &id, &v); 109
    sbt.insert(v, id); 110 sbt.gogo(id, v); 111 } 112 } 113 return 0; 114 }
    View Code

 

http://www.bkjia.com/cjjc/993288.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/993288.htmlTechArticlehdu 4585 Shaolin,hdu4585shaolin
原题链接:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=46093
1 #includecstdio 2 #includecstdlib 3 #includeiostream 4
#includea…

bzoj 1862/1056 [HAOI2008]排名系统,bzojhaoi2008

原题链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1862

很恶心的 一道题,我也不晓得自己是第几次写这题了%>_<%。

写了两种方法,平衡树+哈希和平衡树+map。哈希函数是抄别人的。比较了一下还是哈希快一些。

题意很简单,就不说了。

具体思路是,平衡树维护排名,map建立姓名和分数一一对应的关系。

求rank时题意默认是越先提交得分排名越靠前(相同得分的条件下)。

具体如下:

平衡树+map

 

奥门永利误乐域 2 1
#include<algorithm> 2 #include<iostream> 3
#include<cstdlib> 4 #include<cstring> 5
#include<cstdio> 6 #include<string> 7 #include<map>
8 using std::min; 9 using std::map; 10 using std::string; 11 const int
Max_N = 260000; 12 char src[Max_N][12]; 13 typedef char
State[100]; 14 struct Node{ 15 int v, s, t, id; 16 Node *ch[2]; 17
inline void set(int _v = 0, int _s = 0, int _t = 0, int _id = 0,
Node *p = NULL){ 18 ch[0] = ch[1] = p; 19 v = _v, s = _s, t =
_t, id = _id; 20 } 21 inline void push_up(){ 22 s = ch[0]->s +
ch[1]->s + 1; 23 } 24 inline int cmp(int _v, int _t) const{ 25 if
(v == _v){ 26 return t == _t ? -1 : _t > t; 27 } 28 return v >
_v; 29 } 30 }; 31 struct SizeBalanceTree{ 32 Node stack[Max_N]; 33
Node *root, *null, *tail; 34 Node *store[Max_N]; 35 int top; 36
void init(){ 37 tail = &stack[0]; 38 null = tail++; 39 null->set();
40 root = null; 41 top = 0; 42 } 43 inline Node *newNode(int v, int t,
int id){ 44 Node *p = null; 45 if (top) p = store[–top]; 46 else p =
tail++; 47 p->set(v, 1, t, id, null); 48 return p; 49 } 50 inline
void rotate(Node* &x, int d){ 51 Node *k = x->ch[!d]; 52
x->ch[!d] = k->ch[d]; 53 k->ch[d] = x; 54 k->s =
x->s; 55 x->push_up(); 56 x = k; 57 } 58 inline void
Maintain(Node* &x, int d){ 59 if (x->ch[d] == null) return; 60 if
(x->ch[d]->ch[d]->s > x->ch[!d]->s){ 61
rotate(x, !d); 62 } else if (x->ch[d]->ch[!d]->s >
x->ch[!d]->s){ 63 rotate(x->ch[d], d), rotate(x, !d); 64 }
else { 65 return; 66 } 67 Maintain(x, 0), Maintain(x, 1); 68 } 69 inline
void insert(Node* &x, int v, int t, int id){ 70 if (x == null){ 71 x =
newNode(v, t, id); 72 return; 73 } else { 74 x->s++; 75 int d =
x->cmp(v, t); 76 insert(x->ch[d], v, t, id); 77
x->push_up(); 78 Maintain(x, d); 79 } 80 } 81 inline void del(Node*
&x, int v, int t){ 82 if (x == null) return; 83 x->s–; 84 int d =
x->cmp(v, t); 85 if (-1 == d){ 86 if (!x->ch[0]->s ||
!x->ch[1]->s){ 87 store[top++] = x; 88 x = x->ch[0]->s
? x->ch[0] : x->ch[1]; 89 } else { 90 Node *ret =
x->ch[1]; 91 for (; ret->ch[0] != null; ret =
ret->ch[0]); 92 x->v = ret->v, x->t = ret->t, x->id
= ret->id; 93 del(x->ch[1], ret->v, ret->t); 94 } 95 }
else { 96 del(x->ch[d], v, t); 97 } 98 if (x != null)
x->push_up(); 99 } 100 inline int find(Node *x, int v, int t){ 101
int k = 0, cur = 0; 102 for (; x != null;){ 103 int d = x->cmp(v, t);
104 k = x->ch[0]->s; 105 if (-1 == d) break; 106 else if (!d) x
= x->ch[0]; 107 else cur += k + 1, x = x->ch[1]; 108 } 109
return cur + k + 1; 110 } 111 inline int rank(Node *x, int k){ 112 for
(; x != null;){ 113 int t = x->ch[0]->s; 114 if (k == t + 1)
break; 115 else if (k <= t) x = x->ch[0]; 116 else k -= t + 1, x
= x->ch[1]; 117 } 118 return x->id; 119 } 120 inline void
insert(int v, int t, int id){ 121 insert(root, v, t, id); 122 } 123
inline void del(int v, int t){ 124 del(root, v, t); 125 } 126 inline int
find(int v, int t){ 127 return find(root, v, t); 128 } 129 inline int
rank(int k){ 130 return rank(root, k); 131 } 132 }sbt; 133 struct node{
134 int v, t, id; 135 node(){}; 136 node(int _v, int _t, int _id)
:v(_v), t(_t), id(_id){} 137 }; 138 map<string, node > stri;
139 void gogo(char *s, int v, int t, int &tot){ 140 string str(s); 141
if (stri.count(str) != 0){ 142 sbt.del(stri[str].v, stri[str].t);
143 stri[str].v = v, stri[str].t = t; 144 sbt.insert(v, t,
stri[str].id); 145 return; 146 } 147 strcpy(src[++tot], s); 148
sbt.insert(v, t, tot); 149 node ret(v, t, tot); 150 stri[str] = ret;
151 } 152 int main(){ 153 #ifdef LOCAL 154 freopen(“in.txt”, “r”,
stdin); 155 freopen(“out.txt”, “w+”, stdout); 156 #endif 157
sbt.init(); 158 State s1, buf; 159 int n, v, tot = 0; 160 scanf(“%d\n”,
&n); 161 for (int i = 1; i <= n; i++){ 162 gets(buf); 163 if
(buf[0] == ‘+’){ 164 sscanf(&buf[1], “%s %d”, s1, &v); 165 gogo(s1,
v, i, tot); 166 } else if (buf[0] == ‘?’ && isalpha(buf[1])){ 167
sscanf(&buf[1], “%s”, s1); 168 printf(“%d\n”, sbt.find(stri[s1].v,
stri[s1].t)); 169 } else { 170 int ed; 171 sscanf(&buf[1], “%d”,
&v); 172 ed = min(v + 9, tot); 173 for (int j = v; j <= ed; j++) {
174 printf(“%s%c”, src[sbt.rank(j)], j != ed ? ‘ ‘ : ‘\n’); 175 } 176
} 177 } 178 return 0; 179 } View
Code

 

平衡树+哈希

奥门永利误乐域 3 1
#include<algorithm> 2 #include<iostream> 3
#include<cstdlib> 4 #include<cstring> 5
#include<cstdio> 6 #include<string> 7 #include<map>
8 using std::min; 9 using std::pair; 10 using std::string; 11 typedef
char State[100]; 12 typedef unsigned long long ull; 13 const int
Max_N = 260000; 14 struct Node{ 15 int v, s, t, id; 16 Node *ch[2];
17 inline void 18 set(int _v = 0, int _s = 0, int _t = 0, int _id =
0, Node *p = NULL){ 19 ch[0] = ch[1] = p; 20 v = _v, s = _s, t =
_t, id = _id; 21 } 22 inline void push_up(){ 23 s = ch[0]->s +
ch[1]->s + 1; 24 } 25 inline int cmp(int _v, int _t) const{ 26 if
(v == _v){ 27 return t == _t ? -1 : _t > t; 28 } 29 return v >
_v; 30 } 31 }; 32 struct SizeBalanceTree{ 33 Node stack[Max_N]; 34
Node *root, *null, *tail; 35 Node *store[Max_N]; 36 int top; 37
void init(){ 38 tail = &stack[0]; 39 null = tail++; 40 null->set();
41 root = null; 42 top = 0; 43 } 44 inline Node *newNode(int v, int t,
int id){ 45 Node *p = null; 46 if (top) p = store[–top]; 47 else p =
tail++; 48 p->set(v, 1, t, id, null); 49 return p; 50 } 51 inline
void rotate(Node* &x, int d){ 52 Node *k = x->ch[!d]; 53
x->ch[!d] = k->ch[d]; 54 k->ch[d] = x; 55 k->s =
x->s; 56 x->push_up(); 57 x = k; 58 } 59 inline void
Maintain(Node* &x, int d){ 60 if (x->ch[d] == null) return; 61 if
(x->ch[d]->ch[d]->s > x->ch[!d]->s){ 62
rotate(x, !d); 63 } else if (x->ch[d]->ch[!d]->s >
x->ch[!d]->s){ 64 rotate(x->ch[d], d), rotate(x, !d); 65 }
else { 66 return; 67 } 68 Maintain(x, 0), Maintain(x, 1); 69 } 70 inline
void insert(Node* &x, int v, int t, int id){ 71 if (x == null){ 72 x =
newNode(v, t, id); 73 return; 74 } else { 75 x->s++; 76 int d =
x->cmp(v, t); 77 insert(x->ch[d], v, t, id); 78
x->push_up(); 79 Maintain(x, d); 80 } 81 } 82 inline void del(Node*
&x, int v, int t){ 83 if (x == null) return; 84 x->s–; 85 int d =
x->cmp(v, t); 86 if (-1 == d){ 87 if (!x->ch[0]->s ||
!x->ch[1]->s){ 88 store[top++] = x; 89 x = x->ch[0]->s
? x->ch[0] : x->ch[1]; 90 } else { 91 Node *ret =
x->ch[1]; 92 for (; ret->ch[0] != null; ret =
ret->ch[0]); 93 x->v = ret->v, x->t = ret->t, x->id
= ret->id; 94 del(x->ch[1], ret->v, ret->t); 95 } 96 }
else { 97 del(x->ch[d], v, t); 98 } 99 if (x != null)
x->push_up(); 100 } 101 inline int find(Node *x, int v, int t){ 102
int k = 0, cur = 0; 103 for (; x != null;){ 104 int d = x->cmp(v, t);
105 k = x->ch[0]->s; 106 if (-1 == d) break; 107 else if (!d) x
= x->ch[0]; 108 else cur += k + 1, x = x->ch[1]; 109 } 110
return cur + k + 1; 111 } 112 inline int rank(Node *x, int k){ 113 for
(; x != null;){ 114 int t = x->ch[0]->s; 115 if (k == t + 1)
break; 116 else if (k <= t) x = x->ch[0]; 117 else k -= t + 1, x
= x->ch[1]; 118 } 119 return x->id; 120 } 121 inline void
insert(int v, int t, int id){ 122 insert(root, v, t, id); 123 } 124
inline void del(int v, int t){ 125 del(root, v, t); 126 } 127 inline int
find(int v, int t){ 128 return find(root, v, t); 129 } 130 inline int
rank(int k){ 131 return rank(root, k); 132 } 133 }sbt; 134 #define BASE
133 135 #define MOD 299997 136 #define MAXN 500000 137 int
now[Max_N], _time[Max_N]; 138 struct HashSet{ 139 int
head[MAXN]; 140 int tot, next[MAXN]; 141 ull hash[MAXN]; 142 char
src[Max_N][12]; 143 inline ull GetHash(char *s){ 144 ull re = 0;
145 while (*s != ‘\0’) re = re * BASE + *s++; 146 return re; 147 }
148 inline int Insert(char *s) { 149 ull _hash = GetHash(s); 150 int x
= _hash % MOD; 151 for (int i = head[x]; i; i = next[i]){ 152 if
(hash[i] == _hash) return i; 153 } 154 next[++tot] = head[x]; 155
hash[tot] = _hash; 156 head[x] = tot; 157 strcpy(src[tot], s);
158 return tot; 159 } 160 }map; 161 int main(){ 162 #ifdef LOCAL 163
freopen(“in.txt”, “r”, stdin); 164 freopen(“out.txt”, “w+”, stdout); 165
#endif 166 int n, v; 167 sbt.init(); 168 State s1, buf; 169
scanf(“%d\n”, &n); 170 for (int i = 1; i <= n; i++){ 171 gets(buf);
172 if (buf[0] == ‘+’){ 173 sscanf(&buf[1], “%s %d”, s1, &v); 174
int x = map.Insert(s1); 175 if (now[x]) sbt.del(now[x],
_time[x]); 176 now[x] = v, _time[x] = i; 177
sbt.insert(now[x], _time[x], x); 178 } else if (buf[0] == ‘?’ &&
isalpha(buf[1])){ 179 sscanf(&buf[1], “%s”, s1); 180 int x =
map.Insert(s1); 181 printf(“%d\n”, sbt.find(now[x], _time[x]));
182 } else { 183 int ed; 184 sscanf(&buf[1], “%d”, &v); 185 ed = min(v

  • 9, map.tot); 186 for (int j = v; j <= ed; j++) { 187 printf(“%s%c”,
    map.src[sbt.rank(j)], j != ed ? ‘ ‘ : ‘\n’); 188 } 189 } 190 } 191
    return 0; 192 } View Code

 

http://www.bkjia.com/cjjc/993283.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/993283.htmlTechArticlebzoj 1862/1056 [HAOI2008]排名系统,bzojhaoi2008
原题链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1862 很恶心的
一道题,我也不晓得自己是第几次写…

发表评论

电子邮件地址不会被公开。 必填项已用*标注