CCF CSP认证历年题目自练Day51

本文主要是介绍CCF CSP认证历年题目自练Day51，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

此题又丑又长可以直接从题目分析（个人理解）部分看

题目

试题编号： 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

题目分析（个人理解）

先读题，真的恶心啊，题目那么长谁都不想读，其实这种题应该先从题目描述部分开始读；而不是题目背景；我这个傻子题目背景看了半天（至少1小时）当看到样例输入的时候那个打点的加粗的，表示都是标准输入；也就是你如果先看题目背景那一坨根本没啥用；应该先看题目描述，这样心态会好一些，其实真正要做什么题目描述给的很清楚；就是输入一堆ip地址称之为前缀列表，我们要做的就是找到与之等价的包含IP前缀数目最小的前缀列表。
关于IP前缀，我们需要处理的有三种情况。第一种是标准型，第二种是省略后缀型，第三种是省略长度型。只需要分步求解即可。因此我们做题的流程应该是读完题目描述，分析出来究竟要做什么，然后再根据这些小任务点去到题目背景找自己理解不了的地方。（不找也行）
第一步，我称之为标准化排序。将省略后缀型和省略长度型全部转化为标准型。那么到底怎么样转化就要去题目背景里面找相应的对应关系。主要是题目背景中IP地址及其表示部分和IP前缀与前缀列表部分。其实如果大家学过计算机网络就很好理解。如果没学过那就仔细读题，一定要理解题意。
到底如何做其实可以直接看题目提示去做，将所有IP前置进行排序以及IP地址为第一关键字，以前缀长度为第二关键字从小到大排序形成一个列表。根据这个提示直接选择列表存储。之后用点进行切分，使用split方法实现。对于标准化我分为三个步骤实现，第一步切分之后放到新的列表里。第二步补零。第三步补len。以此实现将ip地址全部转化为标准型。
第二步，从小到大合并。其实就是关键的步骤是判断前者和后者是不是子集的关系。怎样判断前者是不是后者子集是个关键，这里我们需要先读屏幕背景当中的IP地址和IP前缀的匹配关系部分。判断谁是谁的子集的关系的对象是ip前缀匹配集（牵扯到一点离散数学集合论的知识）我们可以先找到匹配集的最大值，利用int类型直接进行大小判断谁是谁的子集的问题。再看提示中的第二步，从小到大合并。那么我只需要便利这个标准化之后的列表。如果前者是后者的子集，直接删除后者一直做递归即可，此步结束我们可以得到此时的列表没有子集的关系。
第三步，同级合并，第一步先判断，如果a与b的前缀长度相同，则设a‘为一个新的IP前缀，其IP地址与a相同，而前缀长度比a少1。第二步再判断a’是否合法且a的匹配集与b的匹配集的并集等于a’的匹配集，则将a与b从列表中移除，并将a‘插入到列中原来a.b的位置，与上一步不同的是，如果a’之前存在元素，则接下来应当从a’的前一个元素开始考虑，否则继续从a’开始考虑。以此实现同级合并。
如果还是不明白可以看一下我写的注释。上代码！！！

#先别看这部分，从标准化输入看起
#第二步关于判断子集关系的一个函数
def compare(ipa, ipb):#比较判断是不是子集关系for i in range(4):#总共就四个（用.切分后）if (ipa[i] < ipb[i]):#后面的比前面大是子集return -1#返回-1elif (ipa[i] > ipb[i]):#不是子集关系返回1return 1else:#ip相同的情况if (i == 3):return 0
#第三步关于同级合并的两个函数
def iszero(a):#判断是不是0if ((a[0] * 16777216 + a[1] * 65536 + a[2] * 256 + a[3]) % (2 ** (32 - a[4] + 1)) == 0):return 1else:return 0def difone(a, b):aend = a[5] * 16777216 + a[6] * 65536 + a[7] * 256 + a[8]#a结束bbeg = b[0] * 16777216 + b[1] * 65536 + b[2] * 256 + b[3]#b开始if (aend + 1 == bbeg):return 1else:return 0#首先先标准化存储
n = int(input())
cidr = []#存放标准化之后的所有IP前缀#是个二维列表
for i in range(n):string = input()b = []if (len(string.split('/')) == 1):  # 省略长度型temp = list(map(int, string.split('.')))#判断长度为几段；temp长度为4则为32；3则为24；依次类推k = len(temp)#记录“len”具体数值#按照题目定义：例如：/32 /24 /16 /8即为“len”for j in range(k):#把省略时的字符串先存入b.append(temp[j])for j in range(4 - k):#标准化第一步（补零）b.append(0)b.append(k * 8)#标准化第二步（补“len”）else:  # 省略后缀型与标准型t = string.split('/')te = int(t[1])#记录“len”tem = list(map(int, t[0].split('.')))#省略时的字符串存放；利用map函数映射成int类型；为用数值直接排序做准备；tem.append(te)temp = temk = len(temp)last = temp[-1]
#关于省略后缀型只有如下情况：/32 /24 /16 /8按数值补零for j in range(k - 1):#先记录省略时的字符b.append(temp[j])for j in range(4 - k + 1):#补零b.append(0)b.append(temp[k - 1])cidr.append(b)
#第一步排序
cidr.sort(key=lambda x: (x[0], x[1], x[2], x[3], x[4]))
#第二步：从小到大合并
for x in cidr:#遍历每一个IP前缀（从头到尾扫描）adder = 2 ** (32 - x[4]) - 1#因为为满足ip的低（32-len）二进制为0；为了确定最大匹配集的值，又因为最大不超过255所以减1；#注意题目背景中的关于IP地址和IP前缀匹配的描述，以下代码都是为了根据len确定匹配集a = adder % 256#逐个确定增加量b = (adder // 256) % 256c = (adder // 65536) % 256d = (adder // 16777216) % 256x.append(d + x[0])#逐个确定匹配集最大IP地址；并添加在列表x；方便后续合并子集做准备x.append(c + x[1])x.append(b + x[2])x.append(a + x[3])
cidr1 = []#存放合并之后的CIDR；不会存在谁是谁的子集的情况#实现方法看下面的代码
while len(cidr) > 1:#标准化后合法的（其实都是合法的）：if (compare(cidr[0][5:], cidr[1][5:]) < 0):#判断前者是不是后者子集关系；如果是cidr1.append(cidr[0])#把范围大的追加cidr.pop(0)#删除范围小的前者else:#如果前者不是后者子集cidr.pop(1)#还是一样把范围小的删掉
cidr1.append(cidr[0])#写入cidr1
#第三步同级合并
cidr2 = []
while len(cidr1) > 1:#如果长度合法即存在ip；也就是扫描列表if (iszero(cidr1[0]) == 0):#判断lencidr2.append(cidr1[0])cidr1.pop(0)elif (cidr1[0][4] != cidr1[1][4]):#a与b的前缀长度不同的时候cidr2.append(cidr1[0])cidr1.pop(0)elif (difone(cidr1[0], cidr1[1]) == 0):cidr2.append(cidr1[0])cidr1.pop(0)else:#a与b的前缀长度相同cidr1[0][4] -= 1#前缀长度少1cidr1[0][5:] = cidr1[1][5:]#ip地址与a相同cidr1.pop(1)#该删删
cidr2.append(cidr1[0])#该加加for x in cidr2:#按要求输出即可print('.'.join(map(str, x[0:4])), end='')print('/', end='')print(x[4])