牛客练习赛94 ABCD 题解

A. 「Nhk R1 A」Initiale Dorimu

Soltuion

题意：给一个 $d$ 构造 $a \oplus b \oplus c = 0$ ，且 $a ∣ b ∣ c = d$ ，要求 $a$ , $b$ , $c$ 都是正整数。

从二进制位上考虑，如果 $d$ 只有一位是 $1$ 的话，由于要求 $a$ , $b$ , $c$ 都是正整数，那么这三个数必须二进制上至少含有一个1。然而由条件 $a ∣ b ∣ c = d$ 知道，这三个数字的二进制上为1的是 $d$ 的子集，所以此时不成立，输出-1，即 $d = 2^{k}$ 时无解。

接下来就很好考虑了，首先因为至少有2个位置为1，那么把 $a$ 设为 $d$ 抠掉第一个1，把 $b$ 设为 $d$ 抠掉第二个1，再把 $c$ 设为包含这两个1的数字即可，最后异或结果一定是0.

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=50143055

B. 「Nhk R1 B」Basement-er Without Wings

Soltuion

题意：给出一个前缀gcd的序列，构造满足题意的排列。

显然当排列到达一定规模的时候，后面一定gcd都是1。
对于排列的第一个数字，一定等于gcd序列的第一个数字。
如果当前的gcd是 $k$ ，只需要随便找个 $k$ 的倍数 $a \cdot k \leq n$ 填上去即可。

那么我们可以用类似于并查集的思想维护一个数字的倍数已经用到哪个了，每次可以近似 $O (1)$ 复杂度找到倍数填上去。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=50143945

C. 「Nhk R1 C」Zet'ubou Another

Solution

题意：给一个迷宫，从左下走到右上， $n, m \leq 10^7$ ，有 $k$ 个陷阱， $k \leq 2000$ 显然对于两个陷阱，如果他们相对位置很远的话，其实中间的距离是没有意义的，如下图：

alt

两个黑色的陷阱相隔很远，我们把右边黑色的陷阱移动到红色的位置。

那么本质上我们可以给这个稀疏图缩点，具体就是进行离散化，如果两个陷阱不相邻，可以在中间多插几个非陷阱点。最后图不会很大，大概是 5000 * 5000的规模，跑一遍bfs即可。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=50156216

D. 「Nhk R1 D」Apocryphal Vir Pulcher

Solution

题意：给一个长度为 $n$ 的序列 $a_{i}$ ，你可以构造无穷个长度为 $n$ 的序列 $c_i \leq 0$ ，要得到 $\sum\limits_{i = 1}^n a_ic_i$ 的第 $k$ 大值， $n \leq 80, k \leq 10^6$ 。

看数据范围显然是 $O (n k)$ 的做法。考虑用 $n$ 个队列来维护每次扩展能得到的最小值。一开始这 $n$ 个队列里全是空的，只有第一个队列为 0，接下来每次找到所有队头的最小值 $M i n$ ，取出来加到 $n$ 个队列中。可以证明这样的队列是单调递增的，并且每次扩展都是当前 $a_{i}$ 加上最小值，能够模拟每次获得的最小值，模拟 $k$ 次即可，注意当前最小值位置为 $p o s$ 时，只需要扩展 $[p o s, n]$ .