原题及翻译
Alex is administrator of IP networks.
亚历克斯是IP网络的管理员。
His clients have a bunch of individual IP addresses and he decided to group all those IP addresses into the smallest possible IP network.
他的客户机有一堆单独的IP地址，他决定将所有这些IP地址分组到尽可能小的IP网络中。
Each IP address is a 4-byte number that is written byte-by-byte in a decimal dot-separated notation “byte0.byte1.byte2.byte3” (quotes are added for clarity).
每个IP地址都是一个4字节的数字，它是以小数点分隔的符号“byte0.byte1.byte2.byte3”逐字节写入的（为了清晰起见，添加了引号）。
Each byte is written as a decimal number from 0 to 255 (inclusive) without extra leading zeroes.
每个字节都写为一个从0到255（包括0到255）的十进制数字，没有额外的前导零。
IP network is described by two 4-byte numbers — network address and network mask.
IP网络由两个4字节的数字（网络地址和网络掩码）描述。
Both network address and network mask are written in the same notation as IP addresses.
网络地址和网络掩码都以与IP地址相同的符号写入。
In order to understand the meaning of network address and network mask you have to consider their binary representation.
为了理解网络地址和网络掩码的含义，必须考虑它们的二进制表示。
Binary representation of IP address, network address, and network mask consists of 32 bits:
IP地址、网络地址和网络掩码的二进制表示由32位组成：
8 bits for byte0 (most significant to least significant), followed by 8 bits for byte1, followed by 8 bits for byte2, and followed by 8 bits for byte3.
8位代表字节0（最高有效到最低有效），8位代表字节1，8位代表字节2，8位代表字节3。
IP network contains a range of 2n IP addresses where 0 n 32.
IP网络包含2N个IP地址范围，其中0 N 32。
Network mask always has32 n first bits set to one, and n last bits set to zero in its binary representation.
网络掩码始终具有在二进制表示中，32个N的第一位设置为1，N的最后一位设置为0。
Network address has arbitrary 32 n first bits, and n last bits set to zero in its binary representation.
网络地址在其二进制表示中有任意的32N个第一位和N个最后位设置为零。
IP network contains all IP addresses whose 32 n first bits are equal to 32 n first bits of network address with arbitrary n last bits.
IP网络包含所有IP地址，其中32个n第一位等于网络地址的32个n第一位，任意n个最后一位。
We say that one IP network is smaller than the other IP network if it contains fewer IP addresses.
如果它包含更少的IP地址，我们说一个IP网络比另一个IP网络小。
For example, IP network with network address 194.85.160.176 and network mask 255.255.255.248 contains 8 IP addresses from 194.85.160.176 to 194.85.160.183 (inclusive).
例如，网络地址为194.85.160.176、网络掩码为255.255.255.248的IP网络包含8个从194.85.160.176到194.85.160.183（含）的IP地址。
Input
输入
The input file will contain several test cases, each of them as described below.
输入文件将包含几个测试用例，每个测试用例如下所述。
The first line of the input file contains a single integer number m (1 m 1000).
输入文件的第一行包含一个整数m（1 m 1000）。
The following m lines contain IP addresses, one address on a line.
下面的M行包含IP地址，一行上有一个地址。
Each IP address may appear more than once in the input file.
每个IP地址可能在输入文件中出现多次。
Output
输出
For each test case, write to the output file two lines that describe the smallest possible IP network that contains all IP addresses from the input file.
对于每个测试用例，向输出文件写入两行，描述包含输入文件中所有IP地址的最小可能IP网络。
Write network address on the first line and network mask on the second line.
在第一行写网络地址，在第二行写网络掩码。
Sample Input
3
194.85.160.177
194.85.160.183
194.85.160.178
Sample Output
194.85.160.176
255.255.255.248
题目理解
可以用一个网络地址和一个子网掩码描述一个子网（即连续的IP地址范围）。其中子网掩码包含32个二进制位，前32-n位为1，后n位为0，网络地址的前32-n位任意，后n位为0。所有前32-n位和网络地址相同的IP都属于此网络。
例如，网络地址为194.85.160.176
（二进制为11000010|01010101|10100000|1011000），
子网掩码为255.255.255.248
（二进制为11111111|11111111|11111111|11111000），
则该子网的IP地址范围是194.85.160.176~194.85.160.183。
输入一些IP地址，求最小的网络（即包含IP地址最少的网络），包含所有这些输入地址。
思路
这道题有两种解法（至少我就只写两种）：
第一种需要一点计算机网络方面的基础知识，知道IP地址、网络地址、子网掩码之间的关系和计算步骤。利用IP差计算子网数，然后根据二进制子网数的位数和IP地址的类别写出子网掩码，最后再转换网络地址。
第二种方法比较简单，利用给出的IP地址的计算出子网的最大和最小IP，然后进行转换，最小IP转换成网络地址，最大IP转换为子网掩码。（这也是我看到一位小哥的思路之后发现很好，才写上的）
代码分析
1.首先，因为题目涉及到二进制与十进制之间的转换，所以先写两个转换函数：
十进制数转换为二进制数
void decimal_number_to_binary_number(IP_address &x)
{
int temp;
memset(x.Binary_format,0, sizeof(x.Binary_format));
for(int i=0;i<4;i++)
{
temp=x.dotted_decimal_format[i];
for(int j=7;j>=0;j--)
{
if(temp==0) break;
x.Binary_format[i][j]=temp%2;
temp/=2;
}
}
}
二进制数转换为十进制数
void binary_number_to_decimal_number(IP_address &x)
{
memset(x.dotted_decimal_format,0,sizeof(x.dotted_decimal_format));
for(int i=0;i<4;i++)
{
for(int j=0;j<8;j++)
{
x.dotted_decimal_format[i]*=2;
x.dotted_decimal_format[i]+=x.Binary_format[i][j];
}
}
}
2.根据第二种方法，程序还需要一个比较函数，来决定最大值和最小值：
bool bigger(IP_address x,IP_address y)
{
for(int i=0;i<4;i++)
{
if(x.dotted_decimal_format[i]>y.dotted_decimal_format[i]) return true;
else if(x.dotted_decimal_format[i]<y.dotted_decimal_format[i]) return false;
}
return false;
}
bool smller(IP_address x,IP_address y)
{
for(int i=0;i<4;i++)
{
if(x.dotted_decimal_format[i]<y.dotted_decimal_format[i]) return true;
else if(x.dotted_decimal_format[i]>y.dotted_decimal_format[i]) return false;
}
return false;
}
3.最后写main（）函数，用于读入和处理数据以及调用一些函数：
int main()
{
int n;
IP_address ip,ip_max,ip_min;
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<4;j++)
{
scanf("%d%*c",&ip.dotted_decimal_format[j]);
}
if(i==0)
{
ip_max=ip;ip_min=ip;
}
else
{
if(bigger(ip,ip_max))
{
ip_max=ip;
}
if(smller(ip,ip_min))
{
ip_min=ip;
}
}
}
decimal_number_to_binary_number(ip_min);
decimal_number_to_binary_number(ip_max);
check(ip_min,ip_max);
binary_number_to_decimal_number(ip_min);
binary_number_to_decimal_number(ip_max);
printf("%d.%d.%d.%d\n",ip_min.dotted_decimal_format[0],ip_min.dotted_decimal_format[1],ip_min.dotted_decimal_format[2],ip_min.dotted_decimal_format[3]);
printf("%d.%d.%d.%d\n",ip_max.dotted_decimal_format[0],ip_max.dotted_decimal_format[1],ip_max.dotted_decimal_format[2],ip_max.dotted_decimal_format[3]);
}
return 0;
}
完整代码
#include <cstdio>
#include <iostream>
#include <cctype>
#include <cmath>
#include <cstring>
using namespace std;
struct IP_address
{
int dotted_decimal_format[4];
char Binary_format[4][8];
};
bool bigger(IP_address x,IP_address y)
{
for(int i=0;i<4;i++)
{
if(x.dotted_decimal_format[i]>y.dotted_decimal_format[i]) return true;
else if(x.dotted_decimal_format[i]<y.dotted_decimal_format[i]) return false;
}
return false;
}
bool smller(IP_address x,IP_address y)
{
for(int i=0;i<4;i++)
{
if(x.dotted_decimal_format[i]<y.dotted_decimal_format[i]) return true;
else if(x.dotted_decimal_format[i]>y.dotted_decimal_format[i]) return false;
}
return false;
}
void decimal_number_to_binary_number(IP_address &x)
{
int temp;
memset(x.Binary_format,0, sizeof(x.Binary_format));
for(int i=0;i<4;i++)
{
temp=x.dotted_decimal_format[i];
for(int j=7;j>=0;j--)
{
if(temp==0) break;
x.Binary_format[i][j]=temp%2;
temp/=2;
}
}
}
void binary_number_to_decimal_number(IP_address &x)
{
memset(x.dotted_decimal_format,0,sizeof(x.dotted_decimal_format));
for(int i=0;i<4;i++)
{
for(int j=0;j<8;j++)
{
x.dotted_decimal_format[i]*=2;
x.dotted_decimal_format[i]+=x.Binary_format[i][j];
}
}
}
void check(IP_address &min, IP_address &max)
{
bool t=false;
for(int i=0;i<4;i++)
{
for(int j=0;j<8;j++)
{
if(t)
{
min.Binary_format[i][j]=0;
max.Binary_format[i][j]=0;
}
else
{
if(min.Binary_format[i][j]!=max.Binary_format[i][j])
{
t = true;
min.Binary_format[i][j]=0;
max.Binary_format[i][j]=0;
}
else
{
max.Binary_format[i][j]=1;
}
}
}
}
}
int main()
{
int n;
IP_address ip,ip_max,ip_min;
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<4;j++)
{
scanf("%d%*c",&ip.dotted_decimal_format[j]);
}
if(i==0)
{
ip_max=ip;ip_min=ip;
}
else
{
if(bigger(ip,ip_max))
{
ip_max=ip;
}
if(smller(ip,ip_min))
{
ip_min=ip;
}
}
}
decimal_number_to_binary_number(ip_min);
decimal_number_to_binary_number(ip_max);
check(ip_min,ip_max);
binary_number_to_decimal_number(ip_min);
binary_number_to_decimal_number(ip_max);
printf("%d.%d.%d.%d\n",ip_min.dotted_decimal_format[0],ip_min.dotted_decimal_format[1],ip_min.dotted_decimal_format[2],ip_min.dotted_decimal_format[3]);
printf("%d.%d.%d.%d\n",ip_max.dotted_decimal_format[0],ip_max.dotted_decimal_format[1],ip_max.dotted_decimal_format[2],ip_max.dotted_decimal_format[3]);
}
return 0;
}