Species Tree 利用HashTable實現
題目再現
題目內容：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
給定一個物種演化圖，關系的表示方式如下：x y : 表示x為y的先祖。一個物種只會有一個先祖，一個先祖可以有很多個演化出來的物種，請你找出每個問題詢問物種的祖父物種(先祖的先祖)，每個物種會使用一個不重復的編號來表示，如果該物種沒有祖父物種的話或是不存在，那么請將他的祖父物種當是0。(憑空而生)保證所有物種間一定有所關連，且不會有重復演化的現象發生，即演化圖只會是一棵樹。輸入格式:只有一組測資。第一行會有兩個數字N、Q，代表總共有N個物種及Q個問題。接下來N-1行，每一行有兩個數字x、y，意義如題目所述。接下來的Q行，每一行有一個數字Z，代表要詢問的物種編號。測資范圍：1 < N < 100000 < Q < 10000 < x, y, z < 1000000輸出格式：對于每一個詢問的物種編號，將他們的祖父物種編號加總后再輸出。輸入樣例：6 31000 20001000 30002000 40003000 50005000 6000500060001234輸出樣例：4000時間限制：100ms內存限制：16000kb |
算法實現
1. 簡單數組下標查找法
通過題目的要求，這里可以使用最簡單的方法，因為輸入的x , y中，y的值是確定不變的，所以這里可以定義一個y的取值范圍那么大的數組，下標就是y的值，內容就是x的值，這樣查找起來十分方便，時間復雜度是O(1)，但是空間上就會浪費比較多了。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
#include <stdio.h>#include <string.h>int main(){ int arrBucket[1000000]; int N, Q; int x, y, z; long long sum = 0; memset(arrBucket, 0, sizeof(arrBucket)); scanf("%d %d", &N, &Q); while(N -- > 1){ scanf("%d %d", &x, &y); arrBucket[y] = x; } while(Q --){ scanf("%d", &z); if(arrBucket[z] != 0){ if(arrBucket[arrBucket[z]] != 0){ sum += arrBucket[arrBucket[z]]; } } } printf("%lld", sum); return 0;} |
2. Hash表實現
因為方法1中，浪費空間嚴重，所以這里使用Hash表實現。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
#include <stdio.h>#include <stdlib.h>#define NULLKEY -1typedef struct { int *elem; //元素 int *elemP; //父元素 int count;}HashTable;int Hash(HashTable H, int k){ return k % H.count;}void InitHashTable(HashTable *H){ int i; H->elem = (int *)malloc(sizeof(int) * H->count); H->elemP = (int *)malloc(sizeof(int) * H->count); for(i = 0; i < H->count; i ++){ H->elem[i] = NULLKEY; H->elemP[i] = NULLKEY; }}void InsertHash(HashTable *H, int key, int value){ int addr; addr = Hash(*H, key); while(H->elem[addr] != NULLKEY){ addr = (addr + 1) % H->count; } H->elem[addr] = key; H->elemP[addr] = value;}int FindHash(HashTable *H, int key, int *addr){ *addr = Hash(*H, key); while(H->elem[*addr] != key){ *addr = (*addr + 1) % H->count; if(H->elem[*addr] == NULLKEY || *addr == Hash(*H, key)){ return 0; } } return 1;}int main(){ int N, Q; int x, y, z, addr; long long sum = 0; HashTable H; scanf("%d %d", &N, &Q); H.count = N - 1; InitHashTable(&H); while(N -- > 1){ scanf("%d %d", &x, &y); InsertHash(&H, y, x); } while(Q --){ scanf("%d", &z); if(FindHash(&H, z, &addr)){ if(FindHash(&H, H.elemP[addr], &addr)){ sum += H.elemP[addr]; } } } printf("%lld", sum); return 0;} |
3. 用C++的map來實現
看著用C實現起來，相對來說實現的各個功能都要自己寫，這里看一下用C++的STL里面的map來實現上面的題目，非常簡單（不得不說STL真的很好用，但是不如HashTable速度快，空間上也不如HashTable占用的小）
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
#include <iostream>#include <map>using namespace std;int main() { int n, q; cin >> n >> q; map<int,int> mp; map<int,int>::iterator it; int x, y, z; for (int i=1; i<n; ++i) { cin >> x >> y; mp.insert(pair<int,int>(y,x)); } int sum = 0; for (int i=0; i<q; ++i) { cin >> z; it = mp.find(z); if (it != mp.end()) { it = mp.find(it->second); if (it != mp.end()) sum += it->second; } } cout << sum; return 0;} |
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
