hiho1289 403 Forbidden （微软笔试，字典树解决掩码问题）

1289 : 403 Forbidden

时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
Little Hi runs a web server. Sometimes he has to deny access from a certain set of malicious IP addresses while his friends are still allow to access his server. To do this he writes N rules in the configuration file which look like:

allow 1.2.3.4/30
deny 1.1.1.1
allow 127.0.0.1
allow 123.234.12.23/3
deny 0.0.0.0/0
Each rule is in the form: allow | deny address or allow | deny address/mask.

When there comes a request, the rules are checked in sequence until the first match is found. If no rule is matched the request will be allowed. Rule and request are matched if the request address is the same as the rule address or they share the same first mask digits when both written as 32bit binary number.

For example IP “1.2.3.4” matches rule “allow 1.2.3.4” because the addresses are the same. And IP “128.127.8.125” matches rule “deny 128.127.4.100/20” because 10000000011111110000010001100100 (128.127.4.100 as binary number) shares the first 20 (mask) digits with 10000000011111110000100001111101 (128.127.8.125 as binary number).

Now comes M access requests. Given their IP addresses, your task is to find out which ones are allowed and which ones are denied.

输入
Line 1: two integers N and M.

Line 2-N+1: one rule on each line.

Line N+2-N+M+1: one IP address on each line.

All addresses are IPv4 addresses(0.0.0.0 - 255.255.255.255). 0 <= mask <= 32.

For 40% of the data: 1 <= N, M <= 1000.

For 100% of the data: 1 <= N, M <= 100000.

输出
For each request output “YES” or “NO” according to whether it is allowed.

样例输入
5 5
allow 1.2.3.4/30
deny 1.1.1.1
allow 127.0.0.1
allow 123.234.12.23/3
deny 0.0.0.0/0
1.2.3.4
1.2.3.5
1.1.1.1
100.100.100.100
219.142.53.100
样例输出
YES
YES
NO
YES
NO

题目给出了N条规则，然后询问M个IP是允许访问还是拒绝访问。每个IP的判断规则是按顺序依次对比每一条规则，按第一条匹配上的规则处理。所谓匹配上，就是询问的IP在规则的范围里。如果N条规则都没匹配上，就按允许处理

allow是允许访问，deny是不允许访问。后面这个1.2.3.4/30表示的是一个IP段，也就是允许或者不允许的IP范围。具体是哪个范围呢？我们先看IP1.2.3.4，我们知道一个IP由ABCD4段组成，中间用点分开。每一段的范围都是0~255，可以用8个二进制位表示，所以整个IP可以由32个二进制位表示。比如128.127.4.100就对应这个32位的二进制串：
10000000011111110000010001100100
而如果一个IP，前20位与128.127.4.100的前20位相同，那么这个IP就在128.127.4.100/20的范围里。具体来说，就是
10000000011111110000000000000000到
10000000011111110000111111111111

要通过所有的数据我们就要用到Trie。对于一条规则，比如128.127.4.100/20，我们就把128.127.4.100的二进制01串的前20位插入到Trie中。而我们处理询问一个IP的时候，就在Trie中查找这个IP，看看沿途经过哪些终结点。显然经过的每个终结点都对应的是一条能匹配上的规则。但是我们要找的是这些规则中最早的一条。所以我们给终结点加一个序号，表示是第几条规则，然后在沿途的终结点中找序号最小的就可以了。

AC code

/* hiho1289  ip子掩码匹配*/
#define _CRT_SBCURE_NO_DEPRECATE
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>

#define maxn 3300010
#define maxm 2
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
using namespace std;
typedef long long ll;

int trie[maxn][maxm] = {0};
int color[maxn];
int n, m, k=1, b[32], ans;
char action[10], s[100];
struct Rule{
    ll ip;
    int digit;
    bool allow;
}rules[100000];

void update(int p, int r){ 
    if(color[p]==-1){// 按最早出现的规则匹配 
        color[p]=r;
    }
}
void insert(ll x, int d, bool allow, int r){
    if(d==0){ // 子掩码为0，则肯定可以匹配
        update(0,r); 
        return; 
    } 
    for(int i=31; i>=0; --i){
        b[i] = x&1;
        x >>= 1;
    }
    int p = 0;
    for(int i=0; i<d; i++){ // 插入前d位 
        int c = b[i];
        if(!trie[p][c]){
            trie[p][c] = k;
            k++;
        }
        p = trie[p][c];
    }
    update(p, r); // 更新p节点 
}
int search(ll x){
    int r = color[0]; // 子掩码位数为0的情况
    for(int i=31; i>=0; i--){
        b[i] = x&1;
        x >>= 1;
    }
    int p = 0;
    for(int i=0; i<32; i++){
        int c = b[i];
        if(!trie[p][c]) break; // 匹配不到了就断了退出
        p = trie[p][c];
        if(color[p]!=-1 && (r==-1 || r>color[p])) r=color[p]; 
        // 如果该节点是子掩码的终点，
        // 并且找到了一个更早出现的能匹配得上的子掩码节点，r==-1表示还没匹配成功, 更新节点 
    } 
    return r;
}

// 字符串处理 
Rule resolve(const char *address, bool allow=true){
    Rule ret;
    ret.ip = 0;
    ret.allow = allow;
    const char* ptr = address;
    // ip
    int cur_sect = 0;
    ll token = 0;
    while(*ptr != 0 && *ptr != '/'){ // 结果或者以'/'结尾退出 
        if(*ptr == '.'){
            ret.ip |= token << ((3-cur_sect)*8);
            cur_sect++;
            token=0;
        }else{
            token = token * 10 +(*ptr - '0');
        }
        ptr ++;
    }
    ret.ip |= token<<((3-cur_sect)*8);
    // digit
    int digits = 0;
    if(*ptr == 0){
        digits = 32; // 没有'/'子掩码位数32 
    }else{
        ptr++; // 跳过'/'
        while(*ptr != 0){
            digits = digits * 10 + (*ptr-'0');
            ptr++;
        } 
    }
    ret.digit = digits;
    return ret;
}

int main(){
    memset(color, -1, sizeof(color)); // 初始化为-1表示没有匹配到 
    scanf("%d%d", &n, &m);
    for(int i=0; i<n; i++){
        scanf("%s%s", action, s);
        rules[i] = resolve(s, action[0]=='a');
        insert(rules[i].ip, rules[i].digit, rules[i].allow, i); // 插入第i条规则 
    }
    for(int i=0; i<m; i++){
        scanf("%s", s);
        Rule r = resolve(s);
        ans = search(r.ip);
        if(ans==-1 || rules[ans].allow) printf("YES\n"); // 没有规则能匹配或者匹配到allow的输出yes 
        else printf("NO\n");
    }
    return 0;
}