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

Zeratul 2020-01-12 23:13:07 2020-01-15 15:03:41

Zeratul已经哭了,你们呢?

A:Zeratul与三角力量

众所周知,这是一道签到题。

三层循环的暴力枚举即得100分。

B:Zeratul与强连通图

看上去很复杂,实际上是非常简单的一道题。(要不然Zeratul为什么把这个会放到第二题)

仔细观察可以发现,整个图的连通性等价于四个角的连通性,其他的点和边都没什么用。

场上最高得分本来应该是60分,但是因为这位同学写错了YES和NO的大小写所以爆零,大家引以为戒。

C:Zeratul与A+B Problem

平方暴力可以得到50分,O(nlogn)的经典做法可以得到80分。

O(n)的做法是使用一个bool数组标记,但是32MB的内存限制开不下10^8的bool数组。因此可以使用bitset模拟bool数组,以满足题目的空间要求。

另有一种基于Hash的做法可以水过此题,同学们可以自行研究。

D:Zeratul与塔防游戏

最小值最大的问题,显然是二分答案。

二分答案后,从左到右枚举每个点,如果发现该点的防御值小于答案就要强化这个点所在的防御塔。如果这个点被多个防御塔覆盖,一定会取右端点最大的防御塔。强化防御塔是一种区间更新操作,可以使用线段树等数据结构进行更新,这样得到80分。

进一步分析发现,区间更新可以直接使用差分数组维护。(想一想,为什么?不是说差分数组不能支持动态修改和查询吗?)这样复杂度省下了一个log,就可以拿到100分了。

发奖

共 1 条回复

foreignbill

前排支持!

AMAZE UI
Hello world!