最新第十一届蓝桥杯软件类Python组（试题回忆+部分个人解答）( 三 ) _宝珠

文章插图
输出格式：一行一个整数，代表划分区域的个数。
输入样例：
1 1
2 2
3 3
输出样例：
解题思路：把这些直线一条一条的加入平面来进行分析，计算当前新加入的直线与之前已加入的直线集合会产生多少个交点，如果产生了k个交点，则划分的区域就会增加 k+1 个（见图所示），在计算交点的时候，需要去重，k个交点的去重时间复杂度大致为O(k*logk)，共有N条直线，所以整体时间复杂度为O(N*N*logN)，（题目中给出N最大为1000，只能保佑不超时了
参考代码：

n = int(input())line = []for _ in range(n):tmp = [int(a) for a in input().split(' ')]line.append(tuple(tmp))line = list(set(line)) #去重n = len(line)judge = lambda pos1,pos2 : abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1]) < 1e-12#判断两个点是否为同一个点ans = 2for i in range(1,n):k1,b1 = line[i]sec = []for j in range(i):k2,b2 = line[j]if k2 == k1: continuepos_x = (b2-b1)/(k1-k2); pos_y = k1*pos_x + b1#计算交点的坐标sec.append((pos_x,pos_y))m = len(sec)tmpans = m+1#交点的数量小于等于1if m < 2:ans += tmpanscontinue#交点的数量大于等于2，需要去重处理sec = sorted(sec,key=lambda x:x[0]) #对交点集合按x轴进行排列for i in range(1,m):if judge(sec[i-1],sec[i]):tmpans -= 1#有重复的，产生的区域数就减一ans += tmpansprint(ans)

第十题. （标题忘了）
（以下题干是我根据自己的理解写的，官方的题干一堆变量名，当时看了有15分钟才明白是啥意思）
问题：在怪物猎人游戏中，玩家可以通过在装备上镶嵌宝珠来获得收益，一共有六件装备，每件装备上都有一定数量的镶嵌孔，每个镶嵌孔都有各自的等级，而宝珠也有等级，镶嵌孔只能镶嵌比自己等级低的宝珠。关于宝珠的说明，宝珠有系列划分，同系列的宝珠没有区别，每个系列的宝珠镶嵌到一定数量时，都会获得一定的收益，如下面举例：
A系宝珠等级是1级，镶嵌数量是 1，2，3，4，5 时，获得的收益分别是 1，2，3，6，7 。镶嵌数量超过5个时，收益仍然为7，镶嵌数量上限为5 。
B系宝珠等级是2级，镶嵌数量是 1，2，3，4 时，获得的收益分别是 2，5，8，15 。镶嵌数量超过4个时，收益仍然为15 。镶嵌数量上限为4，以下同理
C系宝珠等级是2级，镶嵌数量是 1，2，3，4 时，获得的收益分别是 4，7，9，13 。
D系宝珠等级是3级，镶嵌数量是 1，2，3，4 时，获得的收益分别是 5，10，14，21 。
可以看到，你在每个系列上的收益只与你在这个系列上花费的镶嵌孔数量有关，例如对A系宝珠而言，镶嵌3颗时，单位镶嵌孔收益为3/3 = 1，镶嵌4颗时，单位收益为6/4 = 1.5，镶嵌5颗时，单位收益为7/5 = 1.4 。等级越高的宝珠系列单位收益越高（通常而言是这样），而同等级的宝珠系列（例如B系和C系）的单位收益则显得不相上下。现在需要你找出一套镶嵌方案使总收益最大，只输出这个最大收益值即可。
输入格式：前六行代表装备上的镶嵌孔，每行第一个数代表当前装备的镶嵌孔数量，后面的数依次为镶嵌孔的等级。第七行一个整数n，代表有n个系列宝珠，接下来n行，每行代表一个系列，每行的第一个数代表当前系列宝珠的等级，第二个数代表镶嵌数量上限，接下来几个数从低到高依次代表可达到的收益。
数据限制：镶嵌孔和宝珠的等级L不超过4，每个系列的镶嵌数量上限不超过7，系列的数量不超过10000，镶嵌孔的总数不超过300 。
输出格式：一个整数，代表最大收益。
输入样例：

最新 第十一届蓝桥杯软件类Python组（试题回忆+部分个人解答）( 三 )

最新第十一届蓝桥杯软件类Python组（试题回忆+部分个人解答）( 三 )