竞赛讨论区 > 题解-牛客练习赛82

题解-牛客练习赛82

头像
Bazoka13
编辑于 2021-05-09 22:54:54 APP内打开
赞 4 | 收藏 1 | 回复3 | 浏览1023

Huge thanks to those who helped make this round possible:

  • 对于题目解决方法和顺序给出意见的验题人。
  • 参与内测并给予反馈的验题人和学弟。
  • 清楚姐姐等工作人员出色的帮助。
  • Nowcoder 平台。

由于经验不足,对于题面描述不够清楚的问题深表歉意。

A

设一个位置 () 是匹配的当且仅当 ,可以在 的时间内求出所有的匹配位置。

考虑将所有匹配的位置排序后得到序列 ,如果 则无解,否则答案即为 ,同样可以在 的时间内求出。

B

注意到 ,从而

无论进行多少次操作 1 或操作 2, 始终是 的倍数,因此恒有 ,对于所有操作 3 直接输出 即可。

C

首先,对于相同的 ,对应的 必然相同,否则无解。

接下来,处理出每个数所在位置的最小值

遍历每个位置 ,同时维护一个小根堆保存当前可以放但是还没放的数:

  • 如果不存在 ,那么直接从小根堆中拿出最小的数放在该位置即可。

  • 否则,放置的数 必须满足 ,容易发现这样的数必然有 。因此考虑集合 ,如果该集合为空,说明无解;否则将该集合中最小的数放到该位置上,其它数全部加入小根堆。

    这种情况的选择只涉及 ,与之前的选择完全独立,因此不会影响贪心的正确性。

时间复杂度为

D

如果 ,答案即为 ,如果 ,答案即为

下面考虑 的情况。可以证明每次将未被发送的 个数据包全部发送是最优策略。

是最优策略下发送 个数据包的期望代价,,当 时恒 ,下面使用数学归纳法证明:

  • 时,显然有 。对于 个数据包,考虑每次把未被发送的数据包全部发送,设这样做的代价为 ,则有如下等式:

    得到 ,分母恒为正,当 因此分子恒为负,从而

  • 时,假设当 恒成立。考虑对于前 个数据包按照 个数据包的最优策略选择是否发送,同时选择发送最后一个数据包,显然这一次发送的花费相比 个数据包的最优策略的一次发送花费更少。同时,每一种前 个数据包的发送情况都可以等概率地对应 个数据包对应策略中的一种情况,且因为最后一个数据包有可能发送失败,所以剩余数据包数量不减,根据归纳假设发送剩下数据包的期望代价不会增加,从而

另一方面,类似上述过程,对于 个数据包的最优发送策略即为在 个数据包最优发送策略的基础上添加发送最后一个数据包,从而每次将未被发送的 个数据包全部发送即为最优策略。

因此有如下递推式:

将右侧 的系数移项后即可 求解。

E

假设有恰好 对手套被执行第二种操作,一人分走一双,那么这 双手套的选择有 种方案,将这 双手套分给两个人又有 种方案,而剩下 双手套被执行第一种操作,一人分走一只,方案唯一。因此总方案数即为:

给出的 不是质数,一些数的逆元可能不存在。设 ,其中 均为质数,可以求出方案数对每个 取模的结果再使用中国剩余定理进行合并。

下面以求解方案数对 取模为例,其中 是质数。

对于正整数 ,其中 , 令

意义下的逆元,

试除 每个数中的质因子 就可以得到 ,总试除次数不超过

通过前缀积和前缀和即可得到 ,使用一次扩欧求逆元可以得到 ,再倒着进行递推即可得到其余的

方案数对 取模的结果即为:

对于每个 ,上述过程时间复杂度为

的不同质因子的个数,中国剩余定理合并中还需进行 次求逆元,因此总时间复杂度不超过 ,足够通过本题。

F

切痕存在两种情况:

  • 一端在端点上

对于这种情况,我们可以利用双指针遍历多边形上的端点,同时维护两个双指针及其之间的点组成多边形的面积,如果当前维护的多边形面积超过了总面积的一半,我们就可以确定出另一端所在的边,之后我们可以计算出超出的面积,利用叉积等操作计算出另一端在边上的位置,从而更新答案。

  • 两端都不在端点上

这种情况同样可以使用双指针计算,只不过遍历的对象变成了多边形的边,如何找到合法边对在此不再赘述,仅阐述如何处理合法边对计算答案。

如图,延长 延长线于 。设
图片说明

我们有 ,而注意到 ,又有 ,因此 是定值。由基本不等式,我们很容易知道, 时, 取极小值;并且 没有极大值。

之后我们可以利用三角形面积公式计算出 的长度。

时间复杂度为

STD:
A题:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47754605
B题:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47754628
C题:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47754634
D题:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47754641
E题:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47754624
F题:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47754591

3条回帖

回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐