CSDN 竞赛 32 期

1、题目名称：传奇霸业

传奇霸业，是兄弟就来干。 小春(HP == a)遇到了一只黄金哥布林(HP == x)。 小春每次能对哥布林造成b点伤害，哥布
林每次能对小春造成y点伤害。 作为玩家的小春怎么可能随便让哥布林打死呢！他有治疗神药，每次能恢复c点HP。 HP无
上限。 小春需要操作多少次才能打死哥布林？（治疗+攻击）

又一个水多加面，面多加水的问题，这个没什么好说的

class Solution:def __init__(self) -> None:passdef solution(self, a, b, c, x, y):result = None# TODO: 请在此编写代码n = 0while True:if b >= x:n += 1breakif y >= a: # 补血的回合n += 1a = a - y + ccontinuen += 1x -= ba -= y # 别忘记怪物会攻击小春result = nreturn result

2、题目名称：严查枪火

X国最近开始严管枪火。 像是“ak”,“m4a1”,“skr”。都是明令禁止的。 现在小Q查获了一批违禁物品其中部分是枪支。
小Q想知道自己需要按照私藏枪火来关押多少人。 （只有以上三种枪被视为违法）

开始，老顾以为是包含这些关键字的都需要关押，结果一运行，0%通过率，纳闷了，用 js 版本的正则测了下用例， /ak|m4a1|skr/gi.test()，还是 0%，改成/^(ak|m4a1|skr)$/gi.test() 结果100%了。。。

得了，这要严格相等啊，忽略大小写那种，至于用例中有没有大写的，我没专门测试，顺手就忽略大小写了

class Solution:def __init__(self) -> None:passdef solution(self, n, vector):result = None# TODO: 请在此编写代码result = 0for i in range(n):vector[i] = vector[i].lower()if vector[i] in ['ak','m4a1','skr']:result += 1return result

3、题目名称：蚂蚁家族

小蚂蚁群是一个庞大的群体，在这个蚂蚁群中有n只小蚂蚁 ，为了保证所有蚂蚁在消息传送的时候都能接收到消息，需要
在他们之间建立通信关系。就是要求小蚂蚁都可以通过多只或者直接联系到其他人。 已知几条小蚂蚁之间有通信关系，请
问还需要再新建至少多少条关系？

这明显就是要合并集合了，开始老顾是以为 n 只蚂蚁就是 1 到 n，结果有个用例，有个蚂蚁超出 n 这个数字了。。。。结果老顾第一版生成蚂蚁序列 {x:set() for x in range(n)} 在记录蚂蚁的关系时，索引溢出了。。。有一个用例，蚂蚁数量是 665 ，他部分蚂蚁的数字，是666。。。。真是个老六，坑人呢。

不知道其他人是怎么解决的这个问题，老顾干脆的使用最土的办法，所有出现在关系里的蚂蚁才进行记录，之后再用总数减去出现的蚂蚁数量，得到偷懒的蚂蚁数量。

另外，这个是情急下写得，没有优化过，效率就那么回事，大家看看就好

class Solution:def __init__(self) -> None:passdef solution(self, n, m, vector):result = None# TODO: 请在此编写代码if m == 0:return n - 1s = {} # 准备放集合的字典for i in range(m): # 根据关系，分别创建字典主键及集合x,y = vector[i]if x not in s:s[x] = set()if y not in s:s[y] = set()s[x].add(x)s[x].add(y)s[y].add(x)s[y].add(y)while True: # 对集合进行合并b = Trueks = [x for x in s.keys()] # 获取所有字典主键for i in ks:if i not in s: # 如果主键不存在就跳过continuearr = list(s[i]) # 获得主键下的所有集合for j in arr:if j != i and j in s: # 把集合内存在的主键都合并到一起s[i] = s[i].union(s[j])del s[j]    # 被合并的主键删掉b = Falseif b:  # 如果有合并动作，则继续循环，否则跳出breakresult = len(s) - 1 # 需要添加的关系为剩余主键数量减1f = set() # 最后，修正一下，万一某个蚂蚁没有任何关系，那么就需要补回来for i in s:f = f.union(s[i])result += n - len(f) # len(f) 为所有出现在关系中的蚂蚁数量，n为总数量，他们的差就是没有出现在关系中的蚂蚁数量return result

4、题目名称：运输石油

某石油公司需要向A、B两地运输石油。两地的需求量不同，而一辆车只能装载一定量的石油。经过计算A地需要a辆车，B
地需要b辆车运输才能满足需求。现在一共有n辆车分布在各地，每辆车前往A、B两地运输石油均可以获得一定不等的利
润。 现在请你安排a辆车前往A地，b辆车前往B地运输石油，使得在满足A、B两地石油需求的前提下，获得最大的利润。
每辆车只能前往一地运输石油。

这个题目，老顾只有70%的通过率，没有思路啊，纯暴力猜测的结果

老顾的思路是这样 n 辆车，到 a 地利润减去到 b 地利润，按这个利润差排序，

a - b 大的去 a 地，a - b 小的去 b 地，很简单的做法，后边应该能优化出来，但老顾没再继续优化，需要从 n - a - b 剩余的部分，挑选各自到 a 利润高的和到 b 利润高的进行替换原排序中的内容

class Solution:def __init__(self) -> None:passdef solution(self, n, a, b, vector):result = None# TODO: 请在此编写代码result = 0vector.sort() # 按 a 地利润排序arr = [[x[0] - x[1]] + x for x in vector] # 生成利润差数组arr.sort() # 按利润差排序result = sum([x[2] for x in arr[:b]]) + sum([x[1] for x in arr[-a:]]) # 利润差是从小到大排序的，所以选取前 b 个作为去b 的，后a 个是去 a 的，计算这些车辆的利润和return result

小结

前两题都是水题。

第三题见过类似的，好像前两期竞赛有类似题目，当时老顾没有做出来，合并集合有遗漏，这次就上心了。

第四题是真不会了。。。这个思路也不知道对不对，等后边刷 leetcode 或每日一练碰到这个题目的时候再进行补全的验证

ps： 题外话
这次竞赛，好像大佬不多啊，一共才5个满分的，这又是运气好，碰到大佬出去玩了。

答题选择使用 python 是数组操作，集合操作都比较简单，简直就是答题最方便的环境了。