[字符串處理][模擬]OI練習題：IP網絡管理員 networkip

【問題描述】

Alex 是一個 IP 網絡管理員。他的顧客擁有一堆私人 IP 地址，他想把這些 IP 地址組成一個最小的 IP 網絡。

每個 IP 地址是由 4 個 byte 類型數順次由 3 個 dot 連接而成，形如 'byte0.byte1.byte2.byte 3' （不計引號）。每個 byte 類型數是一個 0 至 255 （包括 0 和 255 ）的首位不爲零的十進制整數。

IP 網絡由網絡地址和網絡掩碼來描述，他們的描述方式與 IP 地址相同。爲了準確的理解 IP 地址、網絡地址和網絡掩碼的意義，你需要把它們按照二進制表示寫出。他們的二進制表示都由 32 bits 組成： 8 bits 描述 byte0 、然後 8 bits 描述 byte1 、然後 8 bits 描述 byte2 、最後 8 bits 描述 byte3 。

特定的 IP 網絡包含 2^n 個 IP 地址。它的網絡掩碼的前 32-n 個 bits 爲 1 ，後 n 個 bits 爲 0 ；其網絡地址的前 32–n 個 bits 爲 0 或者 1 ，後 n 個 bits 爲 0 。這個 IP 網絡包含了所有前 32–n 個 bits 與其網絡地址相同且後 n 個 bits 任意的所有 IP 地址，總共 2^n 個。我們說一個 IP 網絡比另一個 IP 網絡小，當且僅當它包含更少的 IP 地址。

比如，網絡地址和網絡掩碼分別爲 194.85.160.176 和 255.255.255.248 的 IP 網 絡包含了從 194.85.160.176 至 194.85.160.183 的 IP 地址。

【輸入格式】

第一行一個正整數 m （ 1 <= m <= 1000 ）表示 Alex 的 IP 地址數。然後 m 行每行描述一個 IP 地址。

【輸出格式】

兩行，分別表示能夠包含所有 IP 地址的最小 IP 網絡的網絡地址和網絡掩碼。

【輸入輸出樣例】

networkip.in

3

194.85.160.177

194.85.160.183

194.85.160.178

networkip.out

194.85.160.176

255.255.255.248

【分析】

這題看著很難，其實很簡單，就是一個簡單的字符串處理問題。

首先是IP地址的讀入，用scanf讀入會很方便的。

然後統計這N個IP地址二進制表示 從前面開始的 最長的公共部分，記為S，即這N個IP地址二進制表示 從前面數S個數都是相同的。

根據題意：把子網掩碼的 前S位置為1，後32-S位為0。

 把IP地址的後32-S位置為0，然後再轉換為10進制輸出即可。

例如樣例：
這三個IP地址的二進制表示為：
194.85.160.177   11000010 01010101 10100000 10110001 194.85.160.183   11000010 01010101 10100000 10110111 194.85.160.178   11000010 01010101 10100000 10110010 
可以看出，這三個IP地址的二進制表示有29位是相同的。


根據題意，把子網掩碼的 前S位置為1，後32-S位為0：
Subnet Mark：11111111 11111111 11111111 11111000 


把IP地址的後32-S位置為0，即為最小IP地址：
 IP Adress：11000010 01010101 10100000 10110000

然後把Subnet Mark和IP Address轉換為10進制輸出即可。

 11111111 11111111 11111111 11111000 =>255.255.255.248


11000010 01010101 10100000 10110000 =>194.85.160.176

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

class IPAddress
{
public:
    int b[5];
    char B[5][10];
    IPAddress()
    {
        for (int i=1;i<=4;i++)
            memset(B[i],'\0',sizeof(B[i]));
    }
}IP[1001];

int N;
int Same=0;
char Sam[5][10];

int power(int base,int index)
{
    int l=1;
    for (int i=1;i<=index;i++)
        l*=base;
    return l;
}

void num2str(int num,char *s,int base)
{
    char map[] = {"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"};
    char dst[64];
    int i=0,n;
    while(num)
    {
        dst[i++]=map[num%base];
        num/=base;
    }
    dst[i]='\0';
    n=i;
    for(i=n-1;i>=0;--i)
    {
        s[n-1-i]=dst[i];
    }
    s[n]='\0';
}

void init()
{
    for (int i=1;i<=4;i++)
        memset(Sam[i],'\0',sizeof(Sam[i]));
   
    scanf("%d\n",&N);
    char tmp[10];
    for (int i=1;i<=N;i++)
    {
        scanf("%d.%d.%d.%d\n",&IP[i].b[1],&IP[i].b[2],&IP[i].b[3],&IP[i].b[4]);
        for (int j=1;j<=4;j++)
        {
            memset(tmp,'\0',sizeof(tmp));
            num2str(IP[i].b[j],tmp,2);
            int len=strlen(tmp);
            int top=0;
            for (int k=0;k<8-len;k++)
            {
                IP[i].B[j][k]='0';
                top++;
            }
            for (int k=0;k<len;k++)
            {
                IP[i].B[j][top]=tmp[k];
                top++;
            }
        }
    }
}

void work()
{
    for (int k=1;k<=4;k++)
    {  
        for (int i=0;i<8;i++)
        {
            //bool ok=true;
            //int tmp=IP[1].B[k][i];
            for (int j=2;j<=N;j++)
            {
                if(IP[j].B[k][i]!=IP[1].B[k][i])
                    return;
            }
            Sam[k][i]=IP[1].B[k][i];
            Same++;
        }
    }
}


void computer()
{
    /*Subnet Mask*/
    char SM[5][10];
    for (int i=1;i<=4;i++)
    {
        for (int j=0;j<8;j++)
        {
            SM[i][j]=Sam[i][j];
            if(SM[i][j]!='\0')
                SM[i][j]='1';
            else
                SM[i][j]='0';
        }
    }
   
    /*IP Address*/
    char AD[5][10];
    for (int i=1;i<=4;i++)
    {
        for (int j=0;j<8;j++)
        {
            AD[i][j]=Sam[i][j];
            if(AD[i][j]=='\0')
                AD[i][j]='0';
        }
    }
   
 
   
    for (int i=1;i<=4;i++)
    {
        int T=0;
        for (int j=0;j<8;j++)
        {
            T=T+(AD[i][j]-'0')*power(2,7-j);
        }
      
        if(i<4)
            cout<<T<<".";
        else
            cout<<T<<endl;
    }
   
   
    for (int i=1;i<=4;i++)
    {
        int T=0;
        for (int j=0;j<8;j++)
        {
            T=T+(SM[i][j]-'0')*power(2,7-j);
        }
            if(i<4)
            cout<<T<<".";
        else
            cout<<T<<endl;
    }
   
}

int main()
{
    freopen("networkip.in","r",stdin);
    freopen("networkip.out","w",stdout);
    init();
   
    work();

    computer();
   
    return 0;
}


【評測結果】
正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.000 s	347 KB	0
2	正确	10	0.000 s	347 KB	0
3	正确	10	0.000 s	347 KB	0
4	正确	10	0.000 s	347 KB	0
5	正确	10	0.001 s	347 KB	0
6	正确	10	0.002 s	347 KB	0
7	正确	10	0.002 s	347 KB	0
8	正确	10	0.002 s	347 KB	0
9	正确	10	0.002 s	347 KB	0
10	正确	10	0.000 s	347 KB	0

运行完成
运行时间 0.010 s
平均内存使用 347 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!