题解

问题理解

我们需要找到一个最小的 IP 网络，使得所有给定的 IP 地址都属于这个网络。IP 网络由网络地址和网络掩码组成，网络掩码决定了网络的大小。我们的目标是找到一个网络掩码，使得所有给定的 IP 地址都在这个网络中，并且这个网络尽可能小。

解决思路

1. IP 地址转换：

   • 将每个 IP 地址转换为一个 32 位的无符号整数，方便进行位操作。

2. 确定网络掩码：

   • 网络掩码的二进制表示中，前导位为 1，后导位为 0。我们需要找到一个网络掩码，使得所有给定的 IP 地址在这个掩码下属于同一个网络。
   • 遍历所有可能的网络掩码（从 32 位全 1 到 32 位全 0），找到一个最小的网络掩码，使得所有 IP 地址在这个掩码下属于同一个网络。

3. 计算网络地址：

   • 对于找到的网络掩码，计算网络地址。网络地址的二进制表示中，前导位与 IP 地址的前导位相同，后导位为 0。

代码实现

以下是完整的 C++ 代码实现：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 将 IP 地址转换为 32 位无符号整数
unsigned int ipToUint(const string &ip) {
    unsigned int a, b, c, d;
    sscanf(ip.c_str(), "%u.%u.%u.%u", &a, &b, &c, &d);
    return (a << 24) | (b << 16) | (c << 8) | d;
}

// 将 32 位无符号整数转换为 IP 地址
string uintToIp(unsigned int x) {
    unsigned int a = (x >> 24) & 0xFF;
    unsigned int b = (x >> 16) & 0xFF;
    unsigned int c = (x >> 8) & 0xFF;
    unsigned int d = x & 0xFF;
    return to_string(a) + "." + to_string(b) + "." + to_string(c) + "." + to_string(d);
}

int main() {
    int m;
    cin >> m;
    vector<string> ips(m);
    for (int i = 0; i < m; ++i) {
        cin >> ips[i];
    }

    // 将所有 IP 地址转换为 32 位无符号整数
    vector<unsigned int> ipInts(m);
    for (int i = 0; i < m; ++i) {
        ipInts[i] = ipToUint(ips[i]);
    }

    // 找到最小的网络掩码
    unsigned int mask = 0xFFFFFFFF; // 初始化为全 1
    for (int i = 31; i >= 0; --i) {
        unsigned int currentMask = mask & ~(1 << i); // 尝试将第 i 位设为 0
        unsigned int network = ipInts[0] & currentMask; // 计算网络地址
        bool valid = true;
        for (int j = 1; j < m; ++j) {
            if ((ipInts[j] & currentMask) != network) {
                valid = false;
                break;
            }
        }
        if (valid) {
            mask = currentMask;
        }
    }

    // 计算网络地址
    unsigned int network = ipInts[0] & mask;

    // 输出结果
    cout << uintToIp(network) << '\n';
    cout << uintToIp(mask) << '\n';

    return 0;
}

代码解释

1. IP 地址转换：

   • ipToUint 函数将 IP 地址字符串转换为一个 32 位的无符号整数。
   • uintToIp 函数将一个 32 位的无符号整数转换回 IP 地址字符串。

2. 读取输入：

   • 读取 IP 地址的数量 m 和 m 个 IP 地址。

3. 确定网络掩码：

   • 初始化网络掩码为全 1。
   • 遍历所有可能的网络掩码（从 32 位全 1 到 32 位全 0），找到一个最小的网络掩码，使得所有 IP 地址在这个掩码下属于同一个网络。

4. 计算网络地址：

   • 对于找到的网络掩码，计算网络地址。

5. 输出结果：

   • 输出网络地址和网络掩码。