解題區/解題區 - UVa

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
*/