Python解题 - CSDN周赛第32期 - 运输石油（三维背包）

上期周赛因为最后一题出现bug，再加上都是经典的模板题，问哥就懒得写题解了。

本期也是有两道考过的题目，不过最后一题因为考到了背包问题的特殊类型，还是值得拿出来记个笔记。

---

第一题：传奇霸业

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

输入描述：第一行输入a,b,c。(1<=a,b,c<=1000)。第二行输入x,y。(1<=x<=1000,0<=y<c)

输出描述：输出最小操作次数。

示例：

	示例
输入	11 6 100 12 5
输出	2

分析

模拟。但本题出得不是特别好，因为对游戏的流程没有说清楚。不管有没有玩过游戏，读完此题都会有一定程度的迷惑：是先攻击怪物（哥布林）还是先受攻击？是回合制还是即时制（在被攻击前可以无限吃药）？问哥一开始以为是即时制，所以最初的思路是一旦自己的HP小于怪物的攻击力，就不断吃药，直到大于怪物攻击力。。。然后无法通过，才发现原来是回合制。修正思路为：如果自己的HP大于怪物的攻击力，或怪物的HP小于自己的攻击力（一击毙命，没必要浪费回合回HP），则发动一次攻击；否则就吃一次药恢复HP。然后轮到怪物发动一次攻击，自己的HP减去怪物的攻击力，然后循环直到怪物HP小于等于0。最后循环的次数就是答案。

参考代码

a, b, c = map(int, input().strip().split())
x, y = map(int, input().strip().split())
res = 0
while x > 0: # 循环直到怪物体力小于等于0if a > y or b >= x: # 如果自己的HP大于怪物的攻击力，或者怪物的HP小于自己的攻击力x -= b # 选择攻击else:a += c # 选择吃药回复HPres += 1 # 回合加一a -= y # 自己受到怪物的攻击，HP减少
print(res)

---

第二题：严查枪火

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

输入描述：第一行输入整数n.(1<=n<=10000)表示携带违禁物品的人数。以下n行表示违禁物品的名称。

输出描述：输出需要按照私藏枪火来关押的人。

示例：

	示例
输入	3 Dsd ak 232asd
输出	1

分析

第6期考过的老题，以前也写过题解。

没什么好分析的，就是依次检查列表中的字符串是否等于这三种枪火所代表的字符串，最后输出相等的个数即可。

参考代码

n = int(input().strip())
res = 0
for _ in range(n):temp = input().strip()if temp in {"ak", "m4a1", "skr"}:res += 1
print(res)

---

第三题：蚂蚁家族

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

输入描述：第一行输入整数n，m；n为小蚂蚁总数；m为关系数。(1<=n,m<=1000)。以下m行每行m对整数x，y。(代表x与y有联系)

输出描述：输出最少需要新建关系数。

示例：

	示例
输入	4 3 1 2  2 3 3 4
输出	0

分析

第12期考过（好像并不遥远），可以参考以前写的题解。

官方很喜欢考并查集，问哥当初解这道题的时候，是靠着测试用例的缺陷骗分过了。后来又自己琢磨了使用集合的方法，不过这次再次遇到，就可以用已经熟悉的并查集模板来解了。

算法原理还是一样，先定义并查集的查集函数find()，再把每次输入边的顶点合并在一起，都指向同一个“祖先”，最后统计祖先的个数，就表示了现在已存在的连通子图的个数，要把它们连在一起，只需要个数减一条边就可以了。

参考代码

n, m = map(int, input().strip().split())
ants = list(range(n+1))
def find(i):if ants[i] == i: return iants[i] = find(ants[i])return ants[i]
for _ in range(m):a, b = map(int, input().strip().split())ants[find(a)] = find(b)
result = set()
for i in ants[1:]:j = find(i)result.add(j)
print(len(result)-1)

不过比赛中本题的数据有坑，有一个测试数据的节点编号超过了 n，于是在查集的时候报了下标越界的错误， 所以上面的代码要稍微修改一下。只要增加一个节点，最后再判断该节点有没有边即可。

---

第四题：运输石油

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

输入描述：输入第一行包含三个整数n，a，b，分别表示公司的车辆数量和A，B两地车辆所需数量，保证a+b<=n。(1<=n<=1000)。接下来有n行，每行两个正整数x，y，分别表示该车完成A地任务的利润和B地任务的利润。

输出描述：输出仅包含一个正整数，表示最大获得的利润和。

示例：

	示例
输入	5 2 2 4 2 3 3 5 4 5 3 1 5
输出	18

分析

题目本身不太难，难的是对测试数据的优化。

从题干来看，还是背包问题的一个扩展子类：三维背包问题。也就是，存在两个背包（A地和B地，两地需要的车的数量类似于普通背包的容积），怎样分配物品（n辆车，类似于体积）才能得到最优解（最大价值）。

既然是背包问题，就存在状态转移。我们可以用  的三维数组来表示  辆车中有  辆去往A地， 辆去往B地的最大价值。那我们如果增加了一辆车，也就是检查第  辆车的时候， 的值怎样得到呢？这时，我们有三个选择：

1. 不派这辆车，那么 
2. 派这辆车去A地，那么  （因为这辆车去了A地，那么前面  辆车里就少派一辆去A地的车）
3. 派这辆车去B地，那么  （同上，因为这辆车去了B地，那么前面  辆车里就少派一辆去B地的车）

很显然，最终  的值就等于这三项最大值。于是，可以得到状态转移方程如下：

如果熟练掌握了基础背包问题，这里很容易就可以看出：因为在状态转移时只用到了  ，所以可以类似01背包，使用循环数组降低空间复杂度，减去一维。但是同样地，状态转移的时候，需要逆序更新。

降维后的转移方程如下：

所以，到这里我们关于这道题的解法已经很清楚了，代码整理如下：

参考代码一

n, a, b = map(int, input().strip().split())
dp = [[0]*(b+1) for _ in range(a+1)]
for i in range(1, n+1):profit_a, profit_b = map(int, input().strip().split())for j in range(a, -1, -1): # 因为使用了滚动数组优化空间，需要逆序更新for k in range(b, -1, -1): # 同上if j > 0: dp[j][k] = max(dp[j][k], dp[j-1][k]+profit_a)if k > 0: dp[j][k] = max(dp[j][k], dp[j][k-1]+profit_b)
print(dp[a][b])

这里要注意边界问题，也就是当  或  时，无须从  或  的状态更新过来。

然鹅，上面的代码是无法pass这道题的。原因就在于测试数据范围太大，而我们的算法时间复杂度是 ，其中 ，而测试数据的范围在 1e4，计算量级相当于1e12 ()。必须考虑优化。

优化

不幸的是，关于三维背包，问哥并不知道是否存在能够优化时间复杂度到  甚至更低的算法。但是上面的状态转移过程中，很显然存在很多无意义的计算，也就是派往A地和B地的车的数量存在  的限制。于是，可以通过剪枝来进行一定的优化。

在下面两行代码里，、 分别代表派往A地和B地的车的数量，而这两个数量的范围使用了  和  。

for j in range(a, -1, -1): for k in range(b, -1, -1): 

不难发现，当我们只有  辆车的时候：

• 如果  ，我们最多只能派  辆，而不是  辆车，去往A地；
• 如果 ，我们最多也只需要派  辆车去A地。

所以，我们派往A地的车辆数量的上限是  。

同样地，因为我们在  辆车里选择了  辆去A地，那么我们最多只能派  辆车去往B地。所以派往B地车辆数量的上限是  。

我们再来看范围的下限。常识里，下限应该是0，也就是一辆都不派，但真的是这样吗？

本题所谓的下限，也就是在  辆车里最少派多少辆车到两地。以A地为例，因为题目要求一定要派  辆车到A地，那么我们在  辆车里最少要派的  辆车，加上剩下的最多能派往A地的车，必须要等于 。剩下的  辆车里最多也只能派  辆车，也就是全部派往A地，所以最小的  要满足  。显然，如果，也就是说剩下的车辆数量大于等于  的话， 的最小值是 0。于是，可以得到  的下限是 。

再来看B地。同样的道理，题目要求一定要派  辆车到B地，也就是说，我们在  辆车里最少要派的  辆车，加上剩下的最多能派往B地的车，必须要等于 。但是，考虑到剩下的车里至少要保留  辆会派往A地，所以剩下能派往B地的车数量最多只有  辆。于是，最小的  要满足  。展开，可以得到  的下限是  。

而在此上下限范围之外的数据，我们是压根不需要计算的。因为逻辑不合理，它们对最终结果不会产生影响，于是我们可以进行剪枝。 更新代码，最终得到pass代码如下：

参考代码二

n, a, b = map(int, input().strip().split())
dp = [[0]*(b+1) for _ in range(a+1)]
for i in range(1, n+1):aa, bb = map(int, input().strip().split())for j in range(min(i, a), max(0, a-n+i)-1, -1):for k in range(min(i-j, b), max(0, b-n+a+i-j)-1, -1):if j > 0: dp[j][k] = max(dp[j][k], dp[j-1][k]+aa)if k > 0: dp[j][k] = max(dp[j][k], dp[j][k-1]+bb)
print(dp[a][b])

由此可见，虽然算法的渐进时间复杂度没有改变，但是通过剪枝，还是可以通过测试用例，说明测试数据中存在许多干扰的无用数据，想必这也是考点之一吧。