竞赛讨论区 > 牛客练习赛26题解
头像
自为风月马前卒
发布于 2018-09-07 22:04
+ 关注

牛客练习赛26题解

牛客练习赛26题解

A 平面

题意:

平面上有$n$个X型不明物体,问它们最多能把平面分成多少份

Sol:

定理:$n$条直线最多能把空间划分为$\frac{n (n + 2)} {2} + 1$份
我们可以把X型看做两条不相交的直线,因此答案为$\frac{2n
(2n + 1)}{2} + 1$

证明:
对于第$n$条直线,如果使得区域增加$k$个, 当且仅当它与$k - 1$条直线相交
而我们之前已经构造好了$n - 1$条两两相交的直线,且三三不相交的直线,因此第$n$条直线一定可以找到一种方法使得与$n - 1$条直线相交
因此 $ans = 1 + 1 + 2 + 3 + ... + n$
直接上等差数列求和公式
https://paste.ubuntu.com/p/q3wHSzp87G/

B 烟花

题意

$n$个烟花,每个烟花代表着互不相同的颜色,对于第$i$个烟花,它有$p_i$的概率点燃,问产生颜色的期望个数 及 产生恰好产生$k$种颜色的概率

Sol

第一问

由于每个烟花互不相同,因此每种颜色的个数都是$1$

根据期望的定义:$ans = \sum p_i * 1 = \sum p_i$

第二问

设$f[i][j]$表示前$i$个烟花,恰好有$j$个被点燃的概率

转移的时候枚举当前烟花是否被点燃

滚动数组优化

https://paste.ubuntu.com/p/zhkd2sYfTp/

C 城市规划

题意:

$n$个城市,第$i$和第$i - 1$个城市之间有道路连接
给出m个请求,你需要断开一些道路,使得任意$1 ≤ i ≤ m$ ,$x_i不能到达y_i$。
最小化断开桥的数量

Sol:

考虑一个很显然的$O(m \log m)$的做法
首先对所有线段按照右端点排序,然后每次在右端点处切
但是$m$达到了$10^7$级别,所以不能通过此题

由于题目保证所有线段的值域为$1 -n$,我们可以对所有左端点,直接记录出右端点最靠左的位置
同样每次切右端点,扫一遍即可
时间复杂度:$O(m)$

https://paste.ubuntu.com/p/vkRWj3qfV5/

D xor序列

题意:

给出n个数,判断对于给出的的$x,y$,能否将$x$与这$n$个数中的任意多个数异或任意多次后变为$y$

Sol:

性质:若$x \oplus z=y$, 则$x \oplus y=z$
考虑答案一定是$x \oplus {$一坨东西$}=y$
那么$x \oplus y = {$一坨东西$}$
因此问题变为询问序列中是否有$x \oplus y$
->线性基经典操作
时间复杂度:$O(nlogn)$
https://paste.ubuntu.com/p/YmK9Y6RH83/

E 树上路径

题意

给出一个n个点的树,1号节点为根节点,每个点有一个权值
你需要支持以下操作
1.将以u为根的子树内节点的权值加val
2.将(u, v)路径上的节点权值加val
3.询问(u, v)路径上节点的权值两两相乘的和

Sol

结论:

$\sum_{1 \leqslant i, j \leqslant N} a_i * a_j = (\sum a_i) ^2 - \sum{a_i ^ 2}$

证明可以暴力展开

后面的两项都可以通过树剖打标记维护

第一个直接维护和,询问的时候乘起来即可

第二个可以展开

$\sum {(a_i + b)}^2 = \sum a_i^2 + \sum2 a_i b + siz * b^2$

https://paste.ubuntu.com/p/tJ9snSDRcy/

F 作物

题意:

序列长度为$n$,第$i$个植物成熟时间为$p_i$,第$i$个植物与第$i - 1$ 个植物距离为$d_i$
一共有$k$个药农,每个药农将以$1$的速度从位置$1$走到位置$n$, 你可以自由安排每个药农的出发时间,当一个药农走到某个位置时, 若该植物己经成熟,那么将其收获
植物成熟后若未被收获每秒损失$1$的价值,求最小损失价值

Sol

其实这题的标算我都写在题目里了啊qwq

稍有常识的人就应该知道这要考带权二分啊

因为“此题并不难”啊233

把每个植物成熟的时间投射到位置1上, 将$p[i]$减去$\sum_{j = 2}^i d[i]$ , 排序后形成了一个序列。
可以证明,每个药农只会采集一段区间。
题目转化成一个序列分成$k$个区间求最小花费。
花费的计算可以用前缀和来表示,$s_i$ 表示成熟时间前缀和,那么转移方程。
$f[i][j]$表示前$i$个采集完毕,出动了$j$个药农。
那么$$f[i][j] = min(f[i][j - 1] + (i - k) * p[i] - (s[i] - s[k]))$$
推出斜率 若转移到 $i$ 时 $k_1$ 比 $k_2$ 优 那么

$$p[i] < \frac{(f[k_1][j - 1] + s[k_1]) - (f[k_2][j - 1] + s[k_2])}{k_1 - k_2}$$
可以$O(nk)$做了
套上带权二分就 A 了。
注意前缀和可能很多负数(虽然这不符合逻辑) , 我们把绝对大小转换成相对大小, 令$p[1] =0$,其余的都相对 $p[1]$做差,这样结果就都是正数。

时间复杂度:$O(n log \sum p[i])$

https://paste.ubuntu.com/p/WCfJqvfzxp/

全部评论

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

本文相关内容

等你来战

查看全部

热门推荐