contents
Problem
找在同一個區域的 IP 中的 IP 遮罩。
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] = '
|
近期评论