微软2016校园招聘4月在线笔试2-403 Forbidden

Love The Way You Lie 2022-07-26 04:16 81阅读 0赞

时间限制: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

感觉关键是输入和后面的逻辑判断，比较繁琐的样子，下面的只能过那几个测试用例，不知道提交会怎么样，之前提交因为数组越界RE……..又提交了一下，WA。。。。。

#include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <stack>
    #include <cmath>
    #include <string>
    #include <set>
    #include <cstring>  //memset
    #include <vector>
    #include <algorithm>
    #include <map>
    
    using namespace std;
    
    typedef struct{
    int bit;
    char num[4];
    int mask;
    }one;
    
    
    char judge[8] = {
    0X00,
    0XFE,
    0XFC,
    0XF8,
    0XF0,
    0XE0,
    0XC0,
    0X80
    };
    
    int main()
    {
        int N,M;
        while(scanf("%d %d", &N, &M) != EOF)
        {
            vector<one> vone;
            string str1, str2;
            one tmp;
            int a,b,c,d,mask;
            char ch;
            for(int i = 0; i < N; i++)
            {
                cin>>str1;
                scanf("%d.%d.%d.%d", &a,&b,&c,&d);
                int mask_flag = 0;
                ch = getchar();
                if(ch == '/')
                {
                    scanf("%d", &mask);
                    mask_flag = 1;
                }
                else
                {
    
                }
                //printf("%d.%d.%d.%d/%d\n",a,b,c,d,mask);
                if(str1 == "allow")
                {
                    tmp.bit = 1;
                    tmp.num[0] = a;
                    tmp.num[1] = b;
                    tmp.num[2] = c;
                    tmp.num[3] = d;
                    if(mask_flag)
                    {
                        tmp.mask = mask;
                    }
                    else
                    {
                        tmp.mask = -1;
                    }
                }
                else
                {
                    tmp.bit = 0;
                    tmp.num[0] = a;
                    tmp.num[1] = b;
                    tmp.num[2] = c;
                    tmp.num[3] = d;
                    if(mask_flag)
                    {
                        tmp.mask = mask;
                    }
                    else
                    {
                        tmp.mask = -1;
                    }
                }
                vone.push_back(tmp);
            }
            char cur[4] = {
       0};
            for(int j = 0; j < M; j++)
            {
                scanf("%d.%d.%d.%d", &a,&b,&c,&d);
                cur[0] = a;
                cur[1] = b;
                cur[2] = c;
                cur[3] = d;
    
                int i;
                for(i = 0; i < vone.size(); i++)
                {
                    if(vone[i].mask == -1)
                    {
                        int j =0;
                        for(j = 0; j < 4; j++)
                        {
                            if(vone[i].num[j] != cur[i])
                            {
                                break;
                            }
                        }
                        if(j == 4)
                        {
                            if(vone[i].bit == 1)
                            {
                                printf("YES\n");
                                break;
                            }
                            else
                            {
                                printf("NO\n");
                                break;
                            }
                        }
                    }
                    else
                    {
                        if(vone[i].mask == 0)
                        {
                            if(vone[i].bit == 1)
                            {
                                printf("YES\n");
                            }
                            else
                            {
                                printf("NO\n");
                            }
                            break;
                        }
    
                        int iii = (32 - vone[i].mask) % 8;
    
                        unsigned char zhongjian = judge[iii];
                        int index = vone[i].mask/8;
    
                        unsigned char tmp1 = vone[i].num[index];
                        int res = 0;
                        for(int k = 0; k < index; k++)
                        {
                            res = vone[i].num[k] ^ cur[k];
                        }
                        tmp1 &= zhongjian;
                        cur[index] &= zhongjian;
                        res ^= (tmp1 ^ cur[index]);
                        if(res == 0)
                        {
                            if(vone[i].bit == 1)
                            {
                                printf("YES\n");
                                break;
                            }
                            else
                            {
                                printf("NO\n");
                                break;
                            }
                        }
                    }
                }
            }
        }
    }