2022-01-20 11:25 已编辑美团_后端开发

关注

【题解】牛客小白月赛30

A

题目描述黑白边

使得 n 个点，两两联通，那么就是一棵树，只需要 n - 1 条边就可以了。

由于要很少的白边，贪心的思想，先把所有的黑边加上，然后再添加白边。

用并查集维护有效边的个数，有效边即这个边连接了两个不同的联通块。

如果有效边的个数不是 n - 1，输出-1，否则输出有效边里面白边的个数。

B

题目描述最好的宝石

线段树操作，区间最大值，多了一个询问，就是求最大价值的宝石有多少个。

这个只需要再线段树合并的时候手动判断就可以了。

C

题目描述滑板上楼梯

每次跳三阶不能连续，所以就是一阶，三阶交替的跳。

x = n / 4;

y = n % 4;

如果 y < 3 , 那么答案就是 2 * x + y，因为最后是恰好跳上去。所以最后跳 y 次一阶就可以了。

否则答案就是 2 * x + 1

D

题目描述 GCD

牛牛有一个集合 $S$ 包含 $1$ 至 $n$ 所有的数，现在他想让你找一个最小的数 $k$ ，使得在 $S$ 中任意找一个子集 $T$ ， $T$ 集合中的元素个数为 $k$ ， $T$ 中都存在两个数 $x$ ， $y$ ，且 $gcd(x,y) > 1$ . 如果找不到满足题目条件的 $k$ ，就输出 $-1$ ,否则输出 $k$ .

$gcd(x, y)$ 为求 $x$ $y$ 的最大公约数。

当 n < 4 的时候，找不到答案，所以输出 -1

当 n > 4 的时候，如果选取 n 以内所有的素数还有 1，那么找不到两个数x y, 使得他们的 gcd > 1, 然而在添一个数，就可以满足题目的条件了。

所以答案就是 n 以内所以素数的个数 + 2

E

题目描述牛牛的加法

模拟就可以了，注意不要有前导0

F

题目描述石子合并

贪心的想，每次找最大的石子堆，让他和相邻的合并，然后小的石子堆就被移除了。所以最大的石子堆会用 n - 1次，非最大的石子堆会用一次，

x = $max(a[i])$ , sum = $\sum_{i=1}^n a[i]$

所以答案就是 x * (n-1) + sum - x

G

题目描述滑板比赛

因我牛牛知道了牛妹的动作顺序，所以可以排序。

分别对 a 和 b 进行从小到大排序。然后倒序遍历。用 a 数组的最大值A和 b 数组的最大值B进行比较。

如果 A 大，代表 A 可以匹配 b 数组剩下的所有值，贪心的想，就匹配 b 中的最大值 B。那么答案加一，AB匹配。进行下一次比较。

如果 B 大，那么找 A 中最小的动作和 B 进行匹配， A 可以用来下一次的匹配。

H

题目描述第 k 小

维护一个大根堆

大根堆的容量是 k，维护的是前 k 小的数。剩下的元素扔了就行。

每次加一个元素的时候，放到大根堆里面，如果大根堆的元素个数大于 k，就不断的弹出元素。

询问的时候去大根堆的堆顶就可以了，如果堆里面的元素不够 k，输出 - 1.

I

题目描述区间异或

有一个长度为 $n$ 的数组 $a[i]$ , 有 $m$ 次询问，每次询问给一个值 $x$ ，找出一个最短的区间，使得这个区间的异或和 $\ge x$ , 输出区间长度。如果找不到输出 $-1$

由于数组元素为 3000 左右，所以可以 $n^2$ 的预处理，处理出来每个长度区间异或的最大值。

得到每个区间长度的异或最大值。

然后从前往后取 max，得到一个非递减的数组。

每次询问在这个数组里面二分一个最小的位置，且这个位置的值大于等于 x。

J

题目描述小游戏

有一个长度为 $n$ 的数组 $a[i]$ , 每一步能拿走一个数，比如拿第 $i$ 个数， $a[i] = x$ ，得到相应的分数 $x$ ，但拿掉这个 $x$ 后， $x+1$ 和 $x-1$ (如果有 $a[j] = x+1$ 或 $a[j] = x-1$ 存在) 就会变得不可拿（但是有 $a[j] = x$ 的话可以继续拿这个 $x$ ）。求最大分数。