TuringJudge monthly 图灵姬月赛 2020.2【解题报告】

Zeratul 2020-02-10 3:19:53 2020-02-10 15:41:22

A

答案是11。

B

按题意模拟即可,题目中连伪代码都给出来了。

C

只需读取所有的字符,统计B的个数就可以了。

D

首先在双方的生命/攻击/防御都确定的情况下,Zeratul是否可以击败怪物和剩余多少生命值都是可以O(1)计算的。

只需枚举加多少次攻击,然后根据Zeratul受到攻击的次数计算剩下的强化次数是加防御合算还是加生命合算。如果怪物每次对Zeratul的伤害大于等于 4 ,那么加防的收益就固定是受到攻击的次数 \times 4 ,而加血的收益固定是 800 。如果怪物已经不能对Zeratul造成伤害,那么加防的收益是 0 ,加血的收益仍然是 800 。因此只有3种情况:

1.全都加生命

2.先加防御,如果怪物对Zeratul的伤害变成0之后仍有剩余强化次数,剩下的次数加生命

3.先加防御,如果怪物对Zeratul的伤害小于4之后仍有剩余强化次数,剩下的次数加生命

三种情况都 O(1) 计算出来,比较一下取最大值即可。这样对于每组数据,复杂度为 O(K)

注意:Zeratul最多剩下 0 血时,应输出 -1

思考1(难度:3):是否有时间复杂度更低的做法?

E

贪心。只需按照 \frac{a_i}{b_i} 为第一关键字,编号为第二关键字,从小到大排序即可。注意不能用double比较,这样精度会出问题。直接通分就可以在整数范围内完成比较了。

struct St{
	long long a, b, c, id;
	bool operator <(const St &r) const{
		if (a*r.b != r.a*b) return a*r.b < r.a*b;
		return id < r.id;
	}
}

思考2(难度:1):这个贪心算法的正确性证明。可以参考1998年NOIp提高组的"拼数"一题。

思考3(难度:5):如果存在一些"要击败第 i 个怪物,必须先击败第 j(j<i) 个怪物"这样的限制呢?(Zeratul小声说:其实这才是原本想出的题目)

F

先BFS/DFS/并查集预处理出每个联通块及其大小,然后直接查询每个砖块的四周是否有包含Y的联通块,并且删除这个砖块之后包含Y的联通块是否能够与其他的联通块相连。注意考虑没有砖块的情况。

再给出两组Hack数据:

3 3
YBB
B#B
BBB

5 5
##B##
##.##
B.#.B
##Y##
##B##

大家可以在评论区尝试回答题解中的3个思考,也可以畅所欲言如果真的有人评论的话

恭喜下面选手

共 5 条回复

FanRLZ

D题只要枚举能干死怪物的不同交手次数就可以了 通过交手次数反推攻击力 可以减小复杂度

E题这个精度卡得我不要不要的

Zeratul

其实不只是精度,还有除以0的问题

FanRLZ

话说这次月赛有奖品么qvq

cww970329

发你邮件了,回复下收货地址

FanRLZ

思考三可以用优先队列解决?

AMAZE UI
Hello world!