poj 2418 Hardwood Species，pojhardwood
原題鏈接：http://poj.org/problem?id=2418
簡單題。。
平衡樹，寫了個模板。。動態分配內存確實很慢。。。
![]()
1 #include<algorithm>
2 #include<iostream>
3 #include<string>
4 #include<cstdlib>
5 #include<cstring>
6 #include<cstdio>
7 using std::string;
8 template<typename T>
9 class sb_tree{
10 private:
11 struct Node{
12 T data;
13 int s, c;
14 Node *ch[2];
15 Node(const T&d) :s(1), c(1), data(d){}
16 Node() :s(0), c(0){ ch[0] = ch[1] = this; }
17 inline void push_up(){
18 s = ch[0]->s + ch[1]->s + c;
19 }
20 inline int cmp(const T&v) const{
21 return v == data ? -1 : v > data;
22 }
23 }*null, *root;
24 inline void rotate(Node* &x, int d){
25 Node *k = x->ch[!d];
26 x->ch[!d] = k->ch[d];
27 k->ch[d] = x;
28 k->s = x->s;
29 x->push_up();
30 x = k;
31 }
32 inline void Maintain(Node* &x, int d){
33 if (x->ch[d] == null) return;
34 if (x->ch[d]->ch[d]->s > x->ch[!d]->s){
35 rotate(x, !d);
36 } else if (x->ch[d]->ch[!d]->s > x->ch[!d]->s){
37 rotate(x->ch[d], d), rotate(x, !d);
38 } else {
39 return;
40 }
41 Maintain(x, 0), Maintain(x, 1);
42 }
43 inline void insert(Node *&x, const T&data){
44 if (!x->s){
45 x = new Node(data);
46 x->ch[0] = x->ch[1] = null;
47 } else{
48 x->s++;
49 int d = x->cmp(data);
50 if (-1 == d){
51 x->c++;
52 return;
53 }
54 insert(x->ch[d], data);
55 x->push_up();
56 Maintain(x, d);
57 }
58 }
59 inline void del(Node *&x, const T&data){
60 if (!x->s) return ;
61 x->s--;
62 int d = x->cmp(data);
63 if (-1 == d){
64 if (x->c > 1){
65 x->c--;
66 return;
67 } else if (!x->ch[0]->s || !x->ch[1]->s){
68 x = x->ch[0]->s ? x->ch[0] : x->ch[1];
69 } else {
70 Node *ret = x->ch[1];
71 for (; ret->ch[0]->s; ret = ret->ch[0]);
72 del(x->ch[1], x->data = ret->data);
73 }
74 } else {
75 del(x->ch[d], data);
76 }
77 if (x->s) x->push_up();
78 }
79 void clear(Node* &x){
80 if (x->s) clear(x->ch[0]), clear(x->ch[1]), delete x;
81 }
82 public:
83 sb_tree() :null(new Node), root(null){}
84 ~sb_tree(){ clear(root), delete null; }
85 inline void clear(){ clear(root), root = null; }
86 inline void insert(const T&data){
87 insert(root, data);
88 }
89 inline void del(const T&data){
90 del(root, data);
91 }
92 inline bool find(const T&data){
93 Node *x = root;
94 while (x->s && x->data != data) x = x->ch[x->data < data];
95 return x->s;
96 }
97 inline const T&kth(int k){
98 Node *x = root;
99 for (int t = 0; x != null;){
100 t = x->ch[0]->s;
101 if (k <= t) x = x->ch[0];
102 else if (t + 1 <= k && k <= t + x->c) break;
103 else k -= t + x->c, x = x->ch[1];
104 }
105 return x->data;
106 }
107 inline int rank(const T&data){
108 Node *x = root;
109 int t = 0, cur = 0;
110 for (cur = 0; x != null;){
111 t = x->ch[0]->s;
112 if (data == x->data) break;
113 else if (data < x->data) x = x->ch[0];
114 else cur += t + x->c, x = x->ch[1];
115 }
116 return cur + t + 1;
117 }
118 inline const T&operator[](int k){
119 return kth(k);
120 }
121 inline const T&preorder(const T&data){
122 Node *x = root, *y = 0;
123 while (x->s){
124 if (x->data < data) y = x, x = x->ch[1];
125 else x = x->ch[0];
126 }
127 return y ? y->data : data;
128 }
129 inline const T&successor(const T&data){
130 Node *x = root, *y = 0;
131 while (x->s){
132 if (data < x->data) y = x, x = x->ch[0];
133 else x = x->ch[1];
134 }
135 return y ? y->data : data;
136 }
137 inline int size(){ return root->s; }
138 inline void query(Node *x, int cnt){
139 if (x != null){
140 query(x->ch[0], cnt);
141 string str = x->data;
142 printf("%s %.4lf\n", str.c_str(), (double)x->c * 100 / cnt);
143 query(x->ch[1], cnt);
144 }
145 }
146 inline void query(){
147 int cnt = size();
148 query(root, cnt);
149 }
150 };
151 int main(){
152 #ifdef LOCAL
153 freopen("in.txt", "r", stdin);
154 freopen("out.txt", "w+", stdout);
155 #endif
156 char buf[100];
157 sb_tree<string> ans;
158 while (gets(buf)) ans.insert(buf);
159 ans.query();
160 return 0;
161 }
View Code
如果不想寫平衡樹，就寫個快排吧。。注意用c提交：
![]()
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 typedef char State[33];
5 State st[1000010];
6 int cmp(const char* src, const char *_src){
7 return strcmp((char *)src, (char *)_src);
8 }
9 int main(){
10 State ret, buf;
11 int i, k, cnt = 0;
12 while (gets(ret)) strcpy(st[cnt++], ret);
13 qsort(st, cnt, sizeof(st[0]), cmp);
14 i = 0;
15 while (i < cnt){
16 strcpy(buf, st[i]), k = 0;
17 for (; 0 == strcmp(buf, st[i]); i++) k++;
18 printf("%s %.4lf\n", buf, (double)k * 100 / cnt);
19 }
20 return 0;
21 }
View Code
