Species Tree 利用HashTable實(shí)現(xiàn)
題目再現(xiàn)
題目?jī)?nèi)容：
|
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
|
給定一個(gè)物種演化圖，關(guān)系的表示方式如下：x y : 表示x為y的先祖。一個(gè)物種只會(huì)有一個(gè)先祖，一個(gè)先祖可以有很多個(gè)演化出來的物種，請(qǐng)你找出每個(gè)問題詢問物種的祖父物種(先祖的先祖)，每個(gè)物種會(huì)使用一個(gè)不重復(fù)的編號(hào)來表示，如果該物種沒有祖父物種的話或是不存在，那么請(qǐng)將他的祖父物種當(dāng)是0。(憑空而生)保證所有物種間一定有所關(guān)連，且不會(huì)有重復(fù)演化的現(xiàn)象發(fā)生，即演化圖只會(huì)是一棵樹。輸入格式:只有一組測(cè)資。第一行會(huì)有兩個(gè)數(shù)字N、Q，代表總共有N個(gè)物種及Q個(gè)問題。接下來N-1行，每一行有兩個(gè)數(shù)字x、y，意義如題目所述。接下來的Q行，每一行有一個(gè)數(shù)字Z，代表要詢問的物種編號(hào)。測(cè)資范圍：1 < N < 100000 < Q < 10000 < x, y, z < 1000000輸出格式：對(duì)于每一個(gè)詢問的物種編號(hào)，將他們的祖父物種編號(hào)加總后再輸出。輸入樣例：6 31000 20001000 30002000 40003000 50005000 6000500060001234輸出樣例：4000時(shí)間限制：100ms內(nèi)存限制：16000kb |
算法實(shí)現(xiàn)
1. 簡(jiǎn)單數(shù)組下標(biāo)查找法
通過題目的要求，這里可以使用最簡(jiǎn)單的方法，因?yàn)檩斎氲膞 , y中，y的值是確定不變的，所以這里可以定義一個(gè)y的取值范圍那么大的數(shù)組，下標(biāo)就是y的值，內(nèi)容就是x的值，這樣查找起來十分方便，時(shí)間復(fù)雜度是O(1)，但是空間上就會(huì)浪費(fèi)比較多了。
|
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表實(shí)現(xiàn)
因?yàn)榉椒?中，浪費(fèi)空間嚴(yán)重，所以這里使用Hash表實(shí)現(xiàn)。
|
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來實(shí)現(xiàn)
看著用C實(shí)現(xiàn)起來，相對(duì)來說實(shí)現(xiàn)的各個(gè)功能都要自己寫，這里看一下用C++的STL里面的map來實(shí)現(xiàn)上面的題目，非常簡(jiǎn)單（不得不說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;} |
感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
