hihocoder1289-403-forbidden

发表于   |   分类于 ，   |  

题目大意

　　http://hihocoder.com/problemset/problem/1289

　　此题是微软2016校园招聘4月在线笔试的第二题。给出一系列ip和mask的规则，让你判断一个新的ip是allow还是deny。注意的是，有些输入条件没有mask，也就是全部匹配（mask＝32），匹配规则是按照最先匹配的原则而不是最长匹配，当没有规则匹配上时返回allow。

题目分析

　　思路参考了这篇文章https://glatue.wordpress.com/2016/04/12/hihocoder-1289-403-forbidden/

　　比较明显的用trie树来处理前缀匹配，注意数据量是在10万，处理ip转换时要用高效率的位操作而不要用字符串转换处理.

　　每个树节点存储当前行号line，是为了最后查找时候找最上面的一行，也就是最先匹配原则。还要存储是否允许，当然该值仅当为word节点才有效，其它节点的isAllow没有意义。还要注意根节点的line和isAllow也是有意义的，保存那些mask值为0的ip，当没有匹配到任何叶节点当然就直接返回根节点的isAllow值

代码

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <cstdio>
#include <cstdlib>
#include <string>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAX_VALUE 100001
typedef unsigned int uint;
class TrieNode {
public:
    int line;
    bool isAllow;
    TrieNode* childNodes[2];
    TrieNode() {
        for(int i = 0; i < 2; i++) {
            childNodes[i] = NULL;
        }
        isAllow = true;
        line = 0; // line >= 1 ,so initial value of line is 0.
    }
    
};
class Trie {
public:
    Trie() {
        root = new TrieNode();
    }
    
    // Inserts a word into the trie.
    void insert(int word, int mask, bool isAllow, int line) {
        
        if(mask == 0) {//like "allow 1.2.4.5/0"
            if(root->line == 0) {
                root->isAllow = isAllow;
                root->line = line;
            }
            return;
        }
        TrieNode* cur = root;
        for(int i = 0; i < mask; i++) {
            int k = word & 0x80000000 ? 1 : 0;
            word <<= 1;
            if((cur->childNodes)[k] == NULL) {
                (cur->childNodes)[k] = new TrieNode();
            }
            cur = (cur->childNodes)[k];
            if(i == mask - 1) {
                if(cur->line == 0) {
                    cur->isAllow = isAllow;
                    cur->line = line;
                }
            }
        }
    }
    
    // Returns if the word is in the trie.
    bool searchAllow(int word) {
        
        int ansline = root->line;
        if(ansline == 0) {
            ansline = MAX_VALUE;
        }
        bool ansAllow = root->isAllow;
        TrieNode* cur = root;
        for(int i = 0; i < 32; i++) {
            int k = word & 0x80000000 ? 1 : 0;
            word <<= 1;
            if((cur->childNodes)[k] == NULL) {
                break;
            }
            cur = (cur->childNodes)[k];
            if(cur->line > 0 && cur->line < ansline) {
                ansAllow = cur->isAllow;
            }
        }
        return ansAllow;
    }
    
private:
    TrieNode* root;
};
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    getchar();
    Trie* trie =  new Trie();
    for(int i = 1; i <= n; i++) {
        char token[10];
        scanf("%s", token);
        uint ip = 0;
        int mask = 32;
        char c;
        for(int xi = 0; xi < 4; xi++) {
            uint x;
            scanf("%d", &x);
            ip <<= 8;
            ip = ip | x;
            c = getchar();
        }
        if(c != '\n') {
            scanf("%d", &mask);
        }
        trie->insert(ip, mask, !strcmp(token, "allow") ? true: false, i);
    }
    for(int j = 0; j < m; j++) {
        uint ip = 0;
        char c;
        for(int xi = 0; xi < 4; xi++) {
            uint x;
            scanf("%d", &x);
            ip <<= 8;
            ip = ip | x;
            c = getchar();
        }
        int ans = trie->searchAllow(ip) ;
        if(ans == 1) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

　　时间复杂度O(n*len)