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;
}