二零一五年百度之星程序设计大赛 - 资格赛1003

2015年百度之星程序设计大赛 - 资格赛1003

IP聚合

 
 Accepts: 786
 
 Submissions: 1787
 Time Limit: 2000/1000 MS (Java/Others)
 
 Memory Limit: 65536/65536 K (Java/Others)
Problem Description

当今世界,网络已经无处不在了,小度熊由于犯了错误,当上了度度公司的网络管理员,他手上有大量的 IP列表,小度熊想知道在某个固定的子网掩码下,有多少个网络地址。网络地址等于子网掩码与 IP 地址按位进行与运算后的结果,例如:

子网掩码:A.B.C.D

IP 地址:a.b.c.d

网络地址:(A&a).(B&b).(C&c).(D&d)

Input

第一行包含一个整数T1T50代表测试数据的组数,

接下来T组测试数据。每组测试数据包含若干行,

第一行两个正整数N1N1000,1M50,M。接下来N行,每行一个字符串,代表一个 IP 地址,

再接下来M行,每行一个字符串代表子网掩码。IP 地址和子网掩码均采用 A.B.C.D的形式,其中ABCD均为非负整数,且小于等于255。

Output

对于每组测试数据,输出两行:

第一行输出: "Case #i:" 。i代表第i组测试数据。

第二行输出测试数据的结果,对于每组数据中的每一个子网掩码,输出在此子网掩码下的网络地址的数量。

Sample Input
2
5 2
192.168.1.0
192.168.1.101
192.168.2.5
192.168.2.7
202.14.27.235
255.255.255.0
255.255.0.0
4 2
127.127.0.1
10.134.52.0
127.0.10.1
10.134.0.2
235.235.0.0
1.57.16.0
Sample Output
Case #1:
3
2
Case #2:
3
4



#include<iostream>
#include<vector>
#include<map>
#include<string>
using namespace std;


int main()
{
    int T,N,M;
    int i,j,k=0;
    string str;
    char tmp[5],reschar[50];
    map<string,int>mymap;
    map<string,int>::iterator it;
    map<string,int>resmap;
    vector<int>tmp_int,map_int;
    cin>>T;

    for(i=1;i<=T;i++)
    {
        cin>>N>>M;
        k=0;
        mymap.clear();
        while(N--)
        {
            cin>>str;
            mymap[str]=1;
        }
        cout<<"Case #"<<i<<":"<<endl;
        while(M--)
        {
            cin>>str;    
            tmp_int.clear();
            resmap.clear();    
            for(j=0;j<str.size();j++)
            {
                if(str[j]!='.')
                {
                    tmp[k]=str[j];
                    k++;
                }
                else
                {
                    tmp[k]=0;
                    tmp_int.push_back(atoi(tmp));
                
                    k=0;
                }
            }
            if(j==str.size())
            {
                tmp[k]=0;
                tmp_int.push_back(atoi(tmp));
                k=0;
            }

            for(it=mymap.begin();it!=mymap.end();++it)
            {
                map_int.clear();

                memset(reschar,0,sizeof(reschar));
                //cout<<it->first<<" "<<it->second<<endl;
                for(j=0;j<it->first.size();j++)
                {
                    if(it->first[j]!='.')
                    {
                        tmp[k]=it->first[j];
                        k++;
                    }
                    else
                    {
                        tmp[k]=0;
                        map_int.push_back(atoi(tmp));
                    
                        k=0;
                    }
                }
                if(j==it->first.size())
                {
                    tmp[k]=0;
                    map_int.push_back(atoi(tmp));
                    k=0;
                }
                for(j=0;j<map_int.size();j++)
                {
                    itoa(map_int[j] & tmp_int[j],tmp,10);
                    strcat(reschar,tmp);
                    strcat(reschar,".");
                }
                //cout<<reschar<<endl;
                resmap[reschar]=1;

            }
                cout<<resmap.size()<<endl;
        }
    }
    return 0;
}