CCF历届真题 部分题解 ，点击进入
问题描述
试题编号：201812-3试题名称：CIDR合并时间限制：1.0s内存限制：512.0MB问题描述：
样例输入
2 1 2
样例输出
1.0.0.0/8 2.0.0.0/8
样例输入
2 10/9 10.128/9
样例输出
10.0.0.0/8
样例输入
2 0/1 128/1
样例输出
0.0.0.0/0
def combine1(a,b): if a[0]*16777216+a[1]*65536+a[2]*256+a[3]>>(32-a[4]) ==b[0]*16777216+b[1]*65536+b[2]*256+b[3]>>(32-a[4]): return True else: return False def combine2(a,b): if a[0]*16777216+a[1]*65536+a[2]*256+a[3]>>(32-a[4]+1) ==b[0]*16777216+b[1]*65536+b[2]*256+b[3]>>(32-a[4]+1) and a[4]==b[4]: return True else: return False n=int(input()) nums=[] for i in range(n): s=input() num=[] ip=0 prefix_len=0 if '.' in s: while '.' in s: index=s.index('.') num.append(int(s[:index])) s=s[index+1:] if '/' in s: index=s.index('/') prefix_len=int(s[index+1:]) num.append(int(s[:index])) num+=(4-len(num))*[0] num.append(prefix_len) else: num.append(int(s)) prefix_len=len(num)*8 num+=(4-len(num))*[0] num.append(prefix_len) #num=[1,2,3,4,prefix_len] nums.append(num) #1.排序 nums.sort() #2.从小到大合并 list2=[] flag=nums[0] list2.append(flag) for i in nums[1:]: if not combine1(flag,i): list2.append(i) flag=i #3.同级合并 list3=[0]*len(list2) top=0 for i in list2: list3[top]=i top+=1 while top>=2: if combine2(list3[top-2],list3[top-1]): x=list3[top-2] x[4]-=1 top-=1 list3[top]=x #top-=2 #list3[top]=x #top+=1 else: break for i in range(top): print('.'.join(map(str,list3[i][:4]))+'/'+str(list3[i][4]))
