【题解】牛客练习赛43

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

A.School

简单的枚举题。

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

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

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即可
通过代码