竞赛讨论区 > 【题解】牛客练习赛91
头像
hx073269
编辑于 2021-11-15 11:47
+ 关注

【题解】牛客练习赛91

前言:
本次比赛题目比较偏向思维,所用到的算法知识点不会太深。
接下来背下锅,很抱歉有人反映C题被卡常。因为std没有任何优化大概500+MS,内测时大家貌似也没有出现被卡常的现象,所以就觉得应该1s足够。没想到比赛期间因为测评机波动,加上可能确实有些算法常数过高,导致了卡常发生,真是抱歉QAQ。

A-神奇天平
考点:数学
对于当前件物品:
①若能整除,则我们分成堆,每堆有件物品。我们把前堆东西放到天平上,如果这堆东西一样重,那说明重的那件物品在最后一堆中,否则天平可以告诉我们,重的那件物品在这堆东西的哪堆中。
②若不能整除,则我们分成堆,前堆每堆有要向下取整)件物品,最后一堆物品数小于等于,可证一定小于等于。我们把前堆东西放到天平上,如果这堆东西一样重,那说明重的那件物品在最后一堆中,否则天平可以告诉我们,重的那件物品在这堆东西的哪堆中。
重复以上过程,最终便可找到重的那件物品,不难发现这个过程本质上就是求(向上取整)的值。
以上是正常的思考过程,实际上打个表找找规律应该就能通过此题(跑
时间复杂度:

B-魔法学院(easy version)
考点:差分、贪心
对于某个字符,我们可以用差分或者贪心的方法处理出他们在上的覆盖区间。然后接着从枚举到,若下标处的字符可以修改为,则令即可。枚举完种字符后,再对字符串统计价值和便可得到最终答案。
时间复杂度:

C-魔法学院(hard version)
考点:并查集、双向链表
我们不妨从高价值字符枚举到低价值字符,那么对于高价值字符覆盖过的区间,低价值字符就没有必要去遍历了。因此遍历时,我们使用并查集或者双向链表对之前覆盖过的区间进行跳跃即可,具体可见代码。
时间复杂度:

D-监狱逃亡
考点:树状数组、线段树
首先预处理出每行的前缀和数组,接着注意到行数只有三,于是我们用表示从第一行下到第二行的下标,用表示从第二行下到第三行的下标,那么问题可以转化成,求满足对数。
我们对上式移项,变为。显然可以类比逆序对,对其离散化后利用树状数组或者线段树进行求解。
时间复杂度:

E-游戏人生
考点:二分、优先队列
显然玩家的初始生命值越多,通关的可能性就越大,因此我们对答案进行二分,那么题目转化成给定玩家初始生命值,判断玩家是否能通关。这个可以使用反悔贪心的方法来实现,具体如下:
①使用两个变量记录到当前回合,使用了多少次普通攻击和狂暴攻击。
②使用一个大根堆保存到当前回合,反悔后玩家能回复的生命值。
③每个回合开始时,首先我们默认使用狂暴攻击,对boss造成点伤害,玩家生命值减,并令
④若玩家的生命值小于等于了,我们进行反悔操作:
1. 如果都为,表示已经无法通过反悔来回复生命值了,因此无法通关。
2. 如果不为,则只能通过将某次狂暴攻击反悔为普通攻击来回复生命值,因此玩家的生命值加,boss的生命值加,并令,
3. 如果不为,则只能通过将某次普通攻击反悔为防御来回复生命值,因此玩家的生命值加堆顶元素,boss的生命值加,弹出堆顶,并令
4. 如果都不为,则判断与堆顶元素的大小,选择回血量更大的操作进行反悔。
⑤接着判断boss生命值是否小于等于,如果是表示能够通关。
⑥然后boss攻击,玩家生命值减少,并将这次反悔后能回复的生命值压入堆。
⑦若玩家的生命值小于等于了,我们进行反悔,具体操作同④。
从内测来看,本题还有线段树的单log做法。
时间复杂度:

F-卡牌大师
考点:思维
的长度是,考虑每个长度为的后缀,某个想和某个相加得到或者,那一个只有一个对应的,所以每个关系,只取一边即可。具体的,对应对应,中点讨论一下,然后算一下分布在四个块里面的数量,每个互斥的块取其中之一。
时间复杂度:

G-区间加
考点:线段树
不算难的数据结构题,主要难度可能在于编程。
考虑某一个普通的数生命历程的所有状态:原数→一直加变成只有→再一直加直到和合并→只有。对于第二个过程,一个数只会最多加次,对于第三个过程,每个数最多只会合并一次,第四个过程之后就相当于每次给这个数乘了。
因此,我们对每个数,如果,那么我们另外开一棵线段树维护,在这棵线段树上,操作都相当于区间乘;否则我们把最高位和其它位分开,记为
对于加操作:等价于给区间的
对于加操作:如果区间存在,我们暴力找到这个,给它加上,直到;否则,操作等价于给区间的
接下来只剩一个问题,就是要把的数合并,并插入到的线段树中。对于这个问题,我们可以维护区间的差的最小值,每次加 ,相当于给区间的,加相当于给区间的。如果区间存在一个,我们就暴力找到这个位置,把合并,插入到另—棵线段树中,并把赋值为
每次询问就是把区间的, ,加起来。
考虑时间复杂度,对于加操作,每个数只会加次,每次需要访问到这个数,这部分总复杂度是;对于合并的操作,每个数只会合并一次,需要访问到这个数,这部分总复杂度是;其它部分总时间复杂度均为。因此这题时间复杂度是
时间复杂度:

全部评论

(3) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐