首页 > ACM题库 > HDU-杭电 > HDU 4760-Good Firewall-线段树-[解题报告]HOJ
2015
09-17

HDU 4760-Good Firewall-线段树-[解题报告]HOJ

Good Firewall

问题描述 :

Professor X is an expert in network security. These days, X is planning to build a powerful network firewall, which is called Good Firewall (a.k.a., GFW). Network flows enter in the GFW will be forwarded or dropped according to pre-established forwarding policies.

Basically, a forwarding policy P is a list of IP subnets, {ip_subnet_1, …, ip_subnet_n}. If P is enabled in GFW, a network flow F with source and destination IP address both located in P can be accepted and forwarded by GFW, otherwise F will be dropped by GFW.

You may know that, an IP address is a 32-bit identifier in the Internet, and can be written as four 0~255 decimals. For example, IP address 01111011.00101101.00000110.01001110 can be expressed as 123.45.6.78. An IP subnet is a block of adjacent IP address with the same binary prefix, and can be written as the first IP address in its address block together with the length of common bit prefix. For example, IP subnet 01111011.00101101.00000100.00000000/22 (123.45.4.0/22) is an IP subnet containing 1024 IP addresses, starting from 123.45.4.0 to 123.45.7.255. If an IP address is in the range of an IP subnet, we say that the IP address is located in the IP subnet. And if an IP address is located in any IP subnet(s) in a policy P, we say that the IP address is located in the policy P.

How will you design the GFW, if you take charge of the plan?

输入:

The input file contains no more than 32768 lines. Each line is in one of the following three formats:

E id n ip_subnet_1 ip_subnet_2 … ip_subnet_n
D id
F ip_src ip_dst

The first line means that a network policy Pid (1<=id<=1024) is enabled in GFW, and there are n (1<=n <=15) IP subnets in Pid. The second line means that policy Pid (which is already enabled at least once) is disabled in GFW. The last line means that a network flow with source and destination IP address is entered in GFW, and you need to figure out whether GFW is going to forward (F) or drop (D) this flow:

1. If the source and destination IP address both are located in one of enabled policy group Pid, GFW will forward this flow.

2. Otherwise GFW will drop this flow. That is, if the source or destination IP address is not located in any of enabled policy group, or they are only located in different enabled policy group(s), GFW will drop it.

IP subnets can be overlapped. An IP address may or may not be located in any policy group, and can also be located in multiple policy groups.

In the global routing table, most of the IP subnets have at least 2^8 IP addresses, and at most 2^24 IP addresses. In our dataset, every IP subnet has a prefix length between 8 and 24.

输出:

The input file contains no more than 32768 lines. Each line is in one of the following three formats:

E id n ip_subnet_1 ip_subnet_2 … ip_subnet_n
D id
F ip_src ip_dst

The first line means that a network policy Pid (1<=id<=1024) is enabled in GFW, and there are n (1<=n <=15) IP subnets in Pid. The second line means that policy Pid (which is already enabled at least once) is disabled in GFW. The last line means that a network flow with source and destination IP address is entered in GFW, and you need to figure out whether GFW is going to forward (F) or drop (D) this flow:

1. If the source and destination IP address both are located in one of enabled policy group Pid, GFW will forward this flow.

2. Otherwise GFW will drop this flow. That is, if the source or destination IP address is not located in any of enabled policy group, or they are only located in different enabled policy group(s), GFW will drop it.

IP subnets can be overlapped. An IP address may or may not be located in any policy group, and can also be located in multiple policy groups.

In the global routing table, most of the IP subnets have at least 2^8 IP addresses, and at most 2^24 IP addresses. In our dataset, every IP subnet has a prefix length between 8 and 24.

样例输入:

E 1 2 123.45.4.0/22 123.45.8.0/22
F 123.45.4.1 123.45.8.1
F 123.45.8.1 123.45.4.1
E 2 1 123.45.6.0/24
D 1
F 123.45.6.123 123.45.6.234
F 123.45.8.1 123.45.4.1

样例输出:

F
F
F
D

转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents    by—cxlove

题意:问两个IP是否在同一组中。。。每一组有若干个IP段。

http://acm.hdu.edu.cn/showproblem.php?pid=4760

又一次被题意玩坏了,被带成了线段树区间覆盖的节奏。。。

因为给出的一IP段,子网掩码限制了前缀是固定的,后缀部分给出一个下界。

所以前缀加入到Trie树,后缀用vector存一下。

对于每一次查询,先把第一个IP到 Trie查一遍,由于IP段是固定前缀,所以按Trie确切地走就行了。

对于每一个结点,都比较一下后缀中是否有合法的。合法的要求就是当前IP的后缀不小于Trie中的后缀,且当前ID是可行的。

那么把ID标记一下,表示当前组满足第一个IP。

然后再跑一遍第二个IP,形式一样。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#define pii pair<int,LL>
using namespace std;
typedef long long LL;
const int N = 100005;
struct Trie {
    Trie *next[2];
    vector<pii> a;
}*root , s[N << 2];
char ope[10];
int tot = 0 , can[N] , ok[1025] , idx = 0;
LL ip (int a , int b , int c , int d) {
    LL ret = 0;
    ret |= (LL)a << 24;
    ret |= (LL)b << 16;
    ret |= (LL)c << 8;
    ret |= d;
    return ret;
}
Trie *newnode () {
    Trie *t = &s[tot ++];
    t -> next[0] = t -> next[1] = NULL;
    t -> a.clear();
    return t;
}
void insert (Trie *p , LL ip , int l , int id) {
    for (int i = 0 ; i < l ; i ++) {
        int c = (ip >> (31 - i)) & 1;
        if (p -> next[c] == NULL)
            p -> next[c] = newnode ();
        p = p -> next[c];
    }
    LL num = ip & ((1 << (32 - l)) - 1);
    p -> a.push_back (make_pair (id , num));
}
void down (LL ip) {
    Trie *p = root;
    for (int i = 31 ; i >= 0 ; i --) {
        int c = (ip >> i) & 1;
        if (p -> next[c] == NULL) return ;
        p = p -> next[c];
        for (int j = 0 ; j < p -> a.size() ; j ++) {
            if (can[p -> a[j].first] && p -> a[j].second <= (ip & ((1 << (i - 1)) - 1)))
                ok[p -> a[j].first] = idx;
        }
    }
}
bool up (LL ip) {
    Trie *p = root;
    for (int i = 31 ; i >= 0 ; i --) {
        int c = (ip >> i) & 1;
        if (p -> next[c] == NULL) return false;
        p = p -> next[c];
        for (int j = 0 ; j < p -> a.size() ; j ++) {
            if (can[p -> a[j].first] && p -> a[j].second <= (ip & ((1 << (i - 1)) - 1)) && ok[p -> a[j].first] == idx)
                return true;
        }
    }
    return false;
}
int main () {
    #ifndef ONLINE_JUDGE
        freopen ("input.txt" , "r" , stdin);
        // freopen ("output.txt" , "w" , stdout);
    #endif
    root = newnode ();
    while (scanf ("%s" , ope) != EOF) {
        if (ope[0] == 'E') {
            int id , k , a , b , c , d , u;
            scanf ("%d %d" , &id , &k);
            for (int i = 0 ; i < k ; i ++) {
                scanf ("%d.%d.%d.%d/%d" , &a , &b , &c , &d , &u);
                insert (root , ip (a , b , c , d) , u , id);
            }
            can[id] = 1;
        }
        else if (ope[0] == 'D') {
            int id;scanf ("%d" , &id);
            can[id] = 0;
        }
        else {
            idx ++;
            int a , b , c , d;
            scanf ("%d.%d.%d.%d" , &a , &b , &c , &d);
            down (ip (a , b , c , d));
            scanf ("%d.%d.%d.%d" , &a , &b , &c , &d);
            puts (up (ip (a , b , c , d)) ? "F" : "D");
        }
    }
    return 0;
}       

参考:http://blog.csdn.net/acm_cxlove/article/details/12141863