HJ18. 识别有效的IP地址和掩码并进行分类统计

题目描述

统计 A、B、C、D、E 类地址数量、错误 IP/掩码数量、私有 IP 数量。每行输入一条 "IP~掩码"。

规则：

• 五类地址按首段划分：A:1-126，B:128-191，C:192-223，D:224-239，E:240-255。
• 私有地址：10.x.x.x；172.16-31.x.x；192.168.x.x（与类别分别累计）。
• 合法掩码：四段拼接的 32 位二进制必须是连续的 1 后跟连续的 0，且不能全 0 或全 1。
• 首段为 0 或 127 的 IP 为特殊地址，整行跳过（无论掩码是否合法，优先级最高）。
• 其余：IP 格式非法或掩码非法 → 错误数 +1；否则按类别计数（可能同时计私有）。

输入格式

• 多行 "IP~掩码"，读到文件结尾。

输出格式

• 一行七个整数：A B C D E 错误数 私有数。

示例

示例 1

输入：

10.70.44.68~1.1.1.5
1.0.0.1~255.0.0.0
192.168.0.2~255.255.255.0
19..0.~255.255.255.0

输出：

1 0 1 0 0 2 1

说明：

• 10.70.44.68~1.1.1.5：掩码 1.1.1.5 非法 → 错误数 +1
• 1.0.0.1~255.0.0.0：A 类 → A +1
• 192.168.0.2~255.255.255.0：C 类，且为私有 → C +1，私有 +1
• 19..0.~255.255.255.0：IP 格式非法 → 错误数 +1

示例 2

输入：

0.201.56.50~255.255.255.0
127.201.56.50~255.255.111.255

输出：

0 0 0 0 0 0 0

说明： 两行首段分别是 0 和 127，属于特殊 IP，整行跳过，不计任何类别。

---

解题思路

第一步：理解问题本质

这是一道纯粹的模拟 + 分类题目。每一行输入独立处理，需要依次做三个判断：

1. 是否特殊 IP（首段 0 / 127）——优先级最高，直接跳过整行。
2. IP 与掩码是否都合法——任一非法则错误数 +1。
3. 合法则按首段分类，并判断是否为私有地址。

第二步：暴力解法（逐项判断）

最直接的做法就是逐项判断：解析 IP、解析掩码、分类、判断私有。逻辑清晰但容易遗漏边界。

问题：掩码合法性的判断容易出错——必须保证 32 位二进制是"连续 1 后连续 0"，且不全 0 不全 1。如果只用"每段是否为合法掩码段"的局部判断，会漏掉跨段的非法情况。

第三步：优化解法（拼接后整体判断掩码）

把四段掩码拼成一个 32 位二进制字符串，再检查是否满足"连续 1 后连续 0"。判断方法：拼接结果中一旦出现 01 子串（即 0 后面又出现 1），就说明不满足连续 1 后连续 0；同时若全 0 或全 1 也非法。

第四步：最优解法（模拟 + 整体判断）

用一个长度为 7 的计数数组，依次处理每行：

1. 用 split('~') 拆出 IP 和掩码，取 IP 首段判断是否特殊地址，是则 continue。
2. 分别调用 valid_ip 和 valid_mask，任一非法则错误数 +1。
3. 按首段 classify 分类累加，再判断是否私有。

def valid_mask(mask: str) -> bool:
    parts = mask.split('.')
    if len(parts) != 4:
        return False
    bits = ''
    for p in parts:
        if not p.isdigit() or not (0 <= int(p) <= 255):
            return False
        bits += format(int(p), '08b')
    if '0' not in bits or '1' not in bits:   # 全 0 或全 1 非法
        return False
    return '01' not in bits                  # 一旦出现 0 不能再出现 1

---

完整代码实现

算法可视化 · 逐帧回放这道题的代码156 帧 · 录制输入

import sys


def valid_ip(ip: str) -> bool:
    """判断 IP 是否合法（四段数字，每段 0~255）"""
    parts = ip.split('.')
    if len(parts) != 4:
        return False
    for p in parts:
        if not p.isdigit() or not (0 <= int(p) <= 255):
            return False
    return True


def valid_mask(mask: str) -> bool:
    """判断掩码是否合法：32 位二进制为连续 1 后连续 0，且不全 0 不全 1"""
    parts = mask.split('.')
    if len(parts) != 4:
        return False
    bits = ''
    for p in parts:
        if not p.isdigit() or not (0 <= int(p) <= 255):
            return False
        bits += format(int(p), '08b')
    if '0' not in bits or '1' not in bits:   # 全 0 或全 1 非法
        return False
    return '01' not in bits                  # 一旦出现 0 不能再出现 1


def classify(a: int) -> int:
    """按首段返回类别：0:A 1:B 2:C 3:D 4:E，返回 -1 表示不落入五类"""
    if 1 <= a <= 126:
        return 0
    if 128 <= a <= 191:
        return 1
    if 192 <= a <= 223:
        return 2
    if 224 <= a <= 239:
        return 3
    if 240 <= a <= 255:
        return 4
    return -1


def solve() -> None:
    """主求解函数"""
    counts = [0, 0, 0, 0, 0, 0, 0]   # A B C D E 错误 私有

    for line in sys.stdin:
        line = line.strip()
        if not line:
            continue
        ip, mask = line.split('~')

        # 特殊 IP（首段 0 或 127）：优先级最高，整行跳过
        first = ip.split('.')[0]
        if first in ('0', '127'):
            continue

        # IP 或掩码非法 → 错误
        if not valid_ip(ip) or not valid_mask(mask):
            counts[5] += 1
            continue

        # 分类
        parts = ip.split('.')
        a = int(parts[0])
        c = classify(a)
        if c != -1:
            counts[c] += 1

        # 私有地址
        if parts[0] == '10':
            counts[6] += 1
        elif parts[0] == '172' and 16 <= int(parts[1]) <= 31:
            counts[6] += 1
        elif parts[0] == '192' and parts[1] == '168':
            counts[6] += 1

    print(' '.join(map(str, counts)))


if __name__ == "__main__":
    solve()

---

示例推演

以示例 1 为例，四行输入逐行处理：

第 1 行：10.70.44.68~1.1.1.5

• 首段为 10，非特殊地址。
• IP 合法，但掩码 1.1.1.5 拼接为 00000001 00000001 00000001 00000101，其中出现 01 子串，掩码非法。
• 错误数 +1。计数：[0,0,0,0,0,1,0]

第 2 行：1.0.0.1~255.0.0.0

• 首段 1，A 类，IP 合法。
• 掩码 255.0.0.0 为 11111111 00000000 00000000 00000000，连续 1 后连续 0，合法。
• A 类 +1。计数：[1,0,0,0,0,1,0]

第 3 行：192.168.0.2~255.255.255.0

• 首段 192，C 类，IP 合法，掩码合法。
• C 类 +1，且 192.168.x.x 为私有 → 私有 +1。计数：[1,0,1,0,0,1,1]

第 4 行：19..0.~255.255.255.0

• IP 为 19..0.，拆分为 ['19','','0','']，存在空段且不足 4 段数字，IP 非法。
• 错误数 +1。计数：[1,0,1,0,0,2,1]

最终输出： 1 0 1 0 0 2 1

---

复杂度分析

解法	时间复杂度	空间复杂度	说明
暴力逐项判断	O(L)	O(1)	L 为行数，逻辑易遗漏边界
拼接后整体判断掩码	O(L)	O(1)	掩码判断一次到位

L 为输入行数

---

易错点总结

1. 特殊地址优先级最高

首段为 0 或 127 的 IP 无论掩码是否合法都要整行跳过，不能先判掩码再跳过。

2. 掩码不能全 0 或全 1

0.0.0.0 和 255.255.255.255 都不是合法掩码，必须排除。

3. 掩码要跨段判断

掩码合法性必须看完整的 32 位二进制，不能只判断每一段。例如 255.0.255.0 每一段单独看都是"合法段"，但拼接后有 01 出现，整体非法。

4. IP 格式校验

IP 每段必须是纯数字且范围 0~255，且必须恰好 4 段。空段（如 19..0.）、非数字（如 1.a.0.1）都要判为非法。

5. 私有地址与类别分别累计

私有地址计数和 A/B/C/D/E 类别计数是独立的，一条记录可能同时计入类别和私有。

---

扩展思考

• 掩码本质是"前缀连续 1"，可用位运算一次性判断：mask & (mask + 1) == 0 且 mask 非 0 非全 1，等价于连续 1 后连续 0。
• 分类判断可抽象为区间映射表，配合二分查找处理更通用的类别区间。

---

相关题目

• HJ33. 整数与IP地址间的转换