IP Networks

也可以看这里个人博客

题目链接

题目大意：一共有若干组输入，每组给出一个数m和m个IP地址，求这些IP地址的网络段号和子网掩码。

其实看到这个题之后不是很明白怎么求解，去网上百度了一番之后发现可以先用IP地址求子网掩码，求出子网掩码之后再用子网掩码与任意一个IP地址按位与就能得出网络段号。

假设有两个IP地址，我们先从左往右，查看这四位当中的哪一位不相同，找到之后，这位之前的都变成255，这位之后的都变成0，再将这一位上的数转成二进制寻找最长相同前缀即可得到子网掩码

代码：

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;
const int dir[] = { 0 , 128 , 192 , 224 , 240 , 248 , 252 , 254 , 255};
//dir是一个映射表，用于快速查找该位上的子网掩码是多少

int m;
int ips[4][N] , mask[5] , minIP[5];

inline void init()//初始化
{
    memset(ips , 0 , sizeof ips);
    memset(mask , 0 , sizeof mask);
    memset(minIP , 0 , sizeof minIP);
}

int main(void)
{
    while(scanf("%d",&m) != EOF)
    {
        init();
        
        for(int i = 0 ; i < m ; ++ i)
            scanf("%d.%d.%d.%d",&ips[0][i] , &ips[1][i] ,&ips[2][i] , &ips[3][i]);
        
        for(int i = 0 ; i < 4 ; ++ i)
        {
            sort(ips[i] , ips[i] + m);//每次对这一行排序
            
            int minv = ips[i][0] , maxv = ips[i][m - 1];//找到最大的和最小的
            
            if(minv != maxv)//如果是当前这一位不同
            {
                for(int j = i + 1 ; j < 4 ; ++ j) mask[j] = 0;//将此位之后的都变成0
                
                for(int j = 0 , k = 128 ; j < 8 ; ++ j , k >>= 1)//利用二进制查找最长相同前缀
                {
                    if((minv & k) != (maxv & k))
                    {
                        mask[i] = dir[j];
                        break;
                    }
                }
                break;
            }
            else mask[i] = 255;
        }
        
        
        for(int i = 0 ; i < 4 ; ++ i) minIP[i] = ips[i][0] & mask[i];//由子网掩码求出网络段
        
        printf("%d.%d.%d.%d\n",minIP[0],minIP[1],minIP[2],minIP[3]);
        printf("%d.%d.%d.%d\n",mask[0],mask[1],mask[2],mask[3]);
    }
    return 0;
}