牛客小白月赛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

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

为求 的最大公约数。

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

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

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

E

题目描述 牛牛的加法

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

F

题目描述 石子合并

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

x = , sum =

所以答案就是 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

题目描述 区间异或

有一个长度为 的数组 , 有 次询问， 每次询问给一个值 ， 找出一个最短的区间， 使得这个区间的异或和 , 输出区间长度。如果找不到输出

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

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

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

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

J

题目描述 小游戏

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

先处理出来每个数出现的多少次。

每个数的大小很小， 所以可以 dp，

代表取到 i 这个数的时候得到的最大分数。