竞赛讨论区 > 【题解】牛客练习赛43
头像
RainAir
编辑于 2022-01-07 11:59
+ 关注

【题解】牛客练习赛43

因为上次小白月赛被喷毒瘤,这次我被迫放了更多的水题。
CDF 出题人 @_Qingyu

A.School

简单的枚举题。

直接 枚举每对人判断是否成立即可。

注意到输出的字符串为 YE5N0 即可通过此题。
通过代码

B.Probability

简单的模拟题。

题目等价于求分数 的小数点后 位的所有数字。

直接暴力模拟除法过程是肯定会 T 的,但是我们发现我们不用从头开始模拟,只需要从 位开始模拟就可以了。

直接通过快速幂+取模算出第 位的数字。然后我们发现 ,所以暴力枚举除法过程就可以。

时间复杂度
通过代码
前两题太良心了吧,题解这么短。

C. Review

简单的图论题。

首先,我们考虑最简单的情况,即。然后,为了判定答案是否合法,我们考虑求出学完所有知识点的最小用时。考虑到一个知识点只能被下列两种途径学会:

  • 单独学习这一个知识点,耗时
  • 从某个已经学会的知识点中学习得来,耗时

如果我们新建一个“虚拟知识点”,并假设它刚开始便已经学会。那么,我们可以将第一种方案转化为第二种方案,即。而学会所有知识点,本质上就是将所有知识点联通,即求出原图的最小生成树即可。

下面,我们再考虑。我们可以再次使用虚拟节点,如果这个知识点初始时就已经学过,则只需要将其向虚拟节点连接一条边权为0的边,即可达到要求。

时间复杂度

当然这时肯定会有人怒斥出题人“你的题怎么卡常啊”。

std写道这一步已经通过了,但考虑到一些选手可能没有写读入优化的习惯,因此我们可以进一步优化。

  1. 注意到每条边的边权在以内,因此我们可以将Kruskal算法中的快速排序改为计数排序,砍掉排序的一个log,
  2. 结合并查集的路径压缩与启发式合并,可以解决此题。
  3. 注意到如果在计算某一条边时,你所消耗的时间已经超过了 ,那么可以直接跳过。
  4. 同理,注意到 ,但是如果 超过了 , 答案一定为 Yes

实际只需要第2个优化,便可以轻松通过此题。
通过代码

D.Sequence

简单的贪心题。最后一个测试点专门卡了一下可能让部分dalao的体验极差……出题人在此谢罪qwq

题目的含义其实是可以从中选出若干个数,选择一个数代价为,你的利益为你利益中的最小值。最大化你的利益。

我们记,答案为

一个显然的贪心策略,是将两个序列从大到小排序,然后考虑中较小的那一个,从它所对应的序列(对应,对应)中选出最大的没有被选的一个数,将它选中,直到我们找不到一个大于的数。

下面我们来考虑这种贪心的正确性。假设我们在中选择了个数中选择了个数,记这种取数方案为,其中。由于地位均等,因此我们不妨设

假设另有一种取数方案更优,则显然有。为什么?若存在一个下标,使得,则其一定选择了一个中没有的,使得,这与我们在选取中“直到我们找不到一个大于的数”矛盾。同理,可证

那么,由上可得,对应的方案,一定是从对应的方案中,将一些选择的数删去,使得答案更优。

  1. 若删去中的某个数

    则会使减少1,减少,答案会增加,但根据我们的取数方案,,因此答案会变得更差,与更优矛盾

  2. 若删去中的某个数

    则会使减少1,减少。根据我们的取数方案,我们每次都是从最小的收益对应的序列中选择的数,删去后,不可能有。为什么?考虑到我们从大到小选取中的每一个数,且当且仅当时,才会选择中的数。显然,若删去,则我们不可能选择中的数,更不可能选择。因此,必有。但考虑到我们选取时,序列中均为整数,因此显然有,这使得至少减少了,因此答案反而至少减少了,因此答案不会变得更优。

综上,我们的贪心策略时正确的。
通过代码

E.Dream City

简单的网络流题。

抛开要求时间的限制,我们直接考虑如何判断这些废水是否可以被处理。我们把每户人家看做一个点,发现限制主要是在点而不是在边,我们就可以很自然地将每个点 拆成两个点 ,建立源点 和汇点 ,对于每一个 ,我们建立源点到 的弧,容量为该点一开始拥有废水的数量 连向 一条容量为废水处理数量 的弧。对于原图的每一条边 ,连接 一条容量为无限大的弧。 该网络的最大流等价于最大能处理的废水数量。

现在我们要求能处理前提下的最短时间,发现是让所有安排方案中花费时间最大的方案花费时间最小,我们发现「最大的时间花费最小」是一个经典的带有单调性的问题。首先跑 确定任意两点间的最短路径,二分最大值 后直接对于每对最短距离 的点对直接建立上述的边就可以了。
通过代码

F.Game

简单的数学题。

首先,你需要注意到题面种“若存在 ,则会使的你的血量减少 ”这句话的含义,是“如果存在,那么血量减1”,因此无论有多少个 满足 ,你的血量都只会减少

考虑时,你开局就死了,因此答案一定为QAQ

考虑,即你不能选择任何会触发反击魔咒的武器,即你能够选择的数,不是中任何一个数的倍数。当 时,注意到我们不需要考虑任何情形。否则,考虑任意一个数,若其不为素数,则其一定有真素因子,若,则,因此我们只需要考虑的全体素数构成的集合,不妨记其为,则显然答案为:
$P=\prod_{j\in \mathbb P_m} j\forall j \in \mathbb P_mj \nmid x(P, x)=1$,反之亦然。

结论1:

证明:必要性是显然的。

充分性:假设,那么一定有,设,则一定存在使得,即,与条件矛盾。

因此,我们便可以计算出我们能造成的总伤害
预处理出,这个式子就可以通过枚举的因子计算完成。由于个不同素数的乘积,因此它的因子个数为。时间复杂度,考虑到可以轻松通过此题

考虑,我们会发现,我们可以使用次会触发反击魔咒的武器,因此总伤害即为(要对 取min的原因是每种武器只能用1次,最多只能造成 点伤害)

最后,我们只需要判定输出Yes,否则输出No即可
通过代码

全部评论

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