UVa 1590 - IP Networks

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

找在同一個區域的 IP 中的 IP 遮罩。

Sample Input

1
2
3
4
3
194.85.160.177
194.85.160.183
194.85.160.178

Sample Output

1
2
194.85.160.176
255.255.255.248

Solution

也就是說我們必須找到其最長共同前綴,知道共同前綴的長度直接輸出 1111111…111000。

用 trie 對於這一道題目,只會用到 0/1 兩種字符,也可以直接暴力掃描,用 trie 沒有甚麼特別快的好處。

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
struct Trie {
int n, label, dist;
int link[2];
} Node[1048576];
int TrieSize;
int insertTrie(const char* str) {
static int i, idx;
for(i = idx = 0; str[i]; i++) {
if(Node[idx].link[str[i]-'0'] == 0) {
TrieSize++;
memset(&Node[TrieSize], 0, sizeof(Node[0]));
Node[TrieSize].label = TrieSize;
Node[TrieSize].dist = i + 1;
Node[idx].link[str[i]-'0'] = TrieSize;
}
idx = Node[idx].link[str[i]-'0'];
}
Node[idx].n ++;
return Node[idx].label;
}
void binaryIP(const int ip[], char buf[]) {
int idx = 0;
for (int i = 0; i < 4; i++) {
for (int j = 8 - 1; j >= 0; j--) {
buf[idx++] = '0' + ((ip[i]>>j)&1);
}
}
buf[idx] = '\0';
}
void getAllLCP(char buf[]) {
int idx = 0, bidx = 0;
do {
int branch = 0, next = 0, c = 0;
for (int i = 0; i < 2; i++) {
if (Node[idx].link[i]) {
branch++, next = Node[idx].link[i], c = i;
}
}
if (branch != 1)
break;
buf[bidx++] = c + '0', idx = next;
} while (true);
buf[bidx] = '\0';
}
int main() {
int n, ip[4];
char bip[128];
while (scanf("%d", &n) == 1) {
TrieSize = 0;
memset(&Node[0], 0, sizeof(Node[0]));
for (int i = 0; i < n; i++) {
scanf("%d.%d.%d.%d", &ip[0], &ip[1], &ip[2], &ip[3]);
binaryIP(ip, bip);
insertTrie(bip);
}
getAllLCP(bip);
int m = (int)strlen(bip);
for (int i = 0; i < 4; i++) {
int bb = 0;
for (int j = 8 - 1; j >= 0; j--) {
if (i * 8 + 7 - j < m) {
if (bip[i * 8 + 7 - j] == '1') {
bb |= 1<<j;
}
}
}
printf("%d%c", bb, i == 3 ? '\n' : '.');
}
for (int i = 0; i < 4; i++) {
int bb = 0;
for (int j = 8 - 1; j >= 0; j--) {
if (i * 8 + 7 - j < m) {
bb |= 1<<j;
}
}
printf("%d%c", bb, i == 3 ? '\n' : '.');
}
}
return 0;
}
/*
3
194.85.160.177
194.85.160.183
194.85.160.178
*/