CCF计算机职业资格考试

201812-3CIDR合并 Python实现（1s内无法实现）

题目参考搜索引擎或者官网
我的Github上有更多CCF-CSP题目的Python实现，可以参考参考。

代码在官网提交是90分，而CCF-CSP的网站限时 1s 是针对C/C++、Java，考试的时候Python限时是 10s ，所以不必担心超时扣分。

思路题目上都给了：

• 排列：利用sorted(key=)函数与参数
• 从小到大合并：e.g. 1011 xxxx的匹配集 $\subset$⊂ 101x xxxx的匹配集
• 同级合并：e.g. 1011 xxxx的匹配集 $\cup$∪ 1010 xxxx的匹配集 == 101x xxxx的匹配集

下面是代码：

# 据悉 用c++同样的思路需要300ms 那么python大概3s左右（最后一个测试点 n <= 10 ** 5）
# 测试网站规定时间1s针对c/c++、java；而考试的时候python时限是10s

def Standardize(primal_ip: str): # 标准化ip地址 ## 代码之后操作都在标准化基础上
    standard_ip = primal_ip
    length = len(primal_ip.split('.'))
    if '/' not in primal_ip: # 省略长度型
        standard_ip = primal_ip + '.0' * (4 - length) + '/' + str(8 * length)
    elif length != 4: # 省略后缀型
        index = primal_ip.index('/')
        standard_ip = primal_ip[: index] + '.0' * (4 - length) + primal_ip[index :]
    return standard_ip

def Info(standard_ip: str) -> (str, int): # 返回ip地址(str)和长度(int)
    index = standard_ip.index('/')
    return standard_ip[: index], int(standard_ip[index + 1:]) # e.g. ('1.2.0.0', 16)

def IpLocation(ip: str) -> {2: str, 10: int}: # 转换ip为二进制、十进制、十六进制
    parts = list(map(int, ip.split('.')))
    Dec = parts[0] * 16777216 + parts[1] * 65536 + parts[2] * 256 + parts[3] # 不用循环以求加快速度
    Bin = bin(Dec)[2 :].rjust(32, '0') # 32位str
    return {2: Bin, 10: Dec}

def Reverse_IpLocation(dec_ip: int) -> str: # 根据十进制返回点分十进制
    parts = []
    for i in range(4):
        parts.append(dec_ip % 256)
        dec_ip = dec_ip // 256
    parts.reverse()
    ip = '.'.join(map(str, parts))
    return ip

def rank(standard_ip: str) -> (int, int): # 配合sorted(key=)使用
    dec_ip = IpLocation(Info(standard_ip)[0])[10] # 转为十进制数字比较 否则会出现 1.10.0.0 < 1.5.0.0
    length = Info(standard_ip)[1]
    return dec_ip, length

def isLegal(standard_ip: str) -> bool: # 判断ip是否合法
    parts = list(map(int, Info(standard_ip)[0].split('.')))
    if len(parts) != 4:
        return False
    elif [(part >= 255) for part in parts] != [True] * 4:
            return False
    elif IpLocation(Info(standard_ip)[0])[2][32-Info(standard_ip)[1] :] != '0' * Info(standard_ip)[1] or \
         Info(standard_ip)[1] > 32:
        return False
    else:
        return True

def isSubset(standard_ip1: str, standard_ip2: str) -> bool: # 判断b匹配集是否是a匹配集的子集
    ip1, ip2, length1, length2 = Info(standard_ip1)[0], Info(standard_ip2)[0], Info(standard_ip1)[1], Info(standard_ip2)[1]
    bin_ip1, bin_ip2 = IpLocation(ip1)[2], IpLocation(ip2)[2]
    min_len = min(length1, length2)
    if bin_ip1[: min_len] == bin_ip2[: min_len]: # e.g. 101x xxxx匹配集包含1011 xxxx匹配集 ## 不用in 必须要前几位相同
        return True
    else:
        return False

def isPeer(standard_ip1: str, standard_ip2: str): # 判断b是否与a同级可合并
    ip1, ip2, length1, length2 = Info(standard_ip1)[0], Info(standard_ip2)[0], Info(standard_ip1)[1], Info(standard_ip2)[1]
    bin_ip1, bin_ip2 = IpLocation(ip1)[2], IpLocation(ip2)[2]
    if length1 == length2 and bin_ip1[: length1-1] == bin_ip2[: length2-1]: # e.g. 1011 xxxx与1010 xxxx合并为101x xxxx
        return standard_ip1[:-1] + str(int(standard_ip1[-1]) - 1)
    else:
        return None

n = int(input())
ips = []
for i in range(n):
    ips.append(Standardize(input()))
    
# 第一步：排序
ips = sorted(ips, key = rank)

# 第二步：从小到大合并
i = 0
while True:
    if isSubset(ips[i], ips[i + 1]):
        del ips[i + 1]
        if i == len(ips) - 1:
            break # 扫描到最后一个
    else:
        if i == len(ips) - 2:
            break # 扫描的最后两个都不匹配
        else:
            i += 1
            
# 第三步：同级合并
i = 0
while True:
    peer = isPeer(ips[i], ips[i + 1])
    if peer: # 同级可合并
        del ips[i]
        del ips[i] # 因为上一句已经删除了一个元素 这句实际上删除的是ips[i + 1]
        ips.insert(i, peer)
        if i != 0: # 让新元素与前一个元素做判断
            i -= 1
        elif len(ips) == 1: # 列表中仅存一个元素
            break
    else:
        if i  == len(ips) - 2:
            break
        else:
            i += 1

for ip in ips:
    print(ip)