xuxuxuxuxu

编辑于 2019-07-16 20:02

【题解】牛客小白月赛16 精

A-小石的签到题

我们发现当 $n>1$ 时先手（小石）总是赢。
如何证明：一开始有 $1\sim n$ , $n$ 个数，假设先手必败，那么先手选 $1$ ，后手就进入了必败状态。
所以假设错误，那么先手就不是必败，先手一定有一种方式能赢。

B-小雨的三角形

数据范围给的很小，可以 $O(n^2)$ 暴力构造三角形，预处理出每一行的总和，每个询问把 $x \sim y$ 行的和加起来即可（若预处理出第 $1 \sim i$ 行的和，则可以做到 $O(1)$ 查询）。
更快的做法？每一行的和其实是有规律的，分别为 $1,4,10,22,46,94 \cdots$ ，除了第 $1$ 行的和为 $1$ 外，第 $i$ 行的和为 $6 \cdot 2^{i - 2} - 2$ ，那么第 $1\sim i\ (i > 1)$ 行的和为

$\begin{aligned} & \quad \ 1 + 6 \cdot 2^0 - 2 + 6 \cdot 2^2 - 2 + 6 \cdot 2^3 - 2 + \cdots + 6 \cdot 2^{i - 2} - 2\\[1ex] &= 1 + 6 \cdot \left( 2^{i-1} - 1\right) - 2 \cdot \left( i - 1\right)\\[1ex] &= 6 \cdot 2^{i-1} - 2 \cdot i -3 \end{aligned}$

所以第 $x \sim y$ 行的和就能用前缀和计算了，注意特判 $x = 1,x=2,y=1$ 的情况，这样就能够每次 $O(\log n)$ 查询。

C-小石的海岛之旅

我们按海岛的高度 $h_i$ 从大到小排序。
假设海岛 $i$ 在水位为 $a_i$ 时被淹没，如果海岛 $i-1$ 和海岛 $i+1$ 都已被淹没，那么就少了一块，答案减 $1$ 。
如果海岛 $i-1$ 和海岛 $i+1$ 都没被淹没，那么一块变两块，答案加 $1$ 。
否则答案不变。
由于出题人良心，直接 $N^2$ 是能过的。

D-小阳买水果

我们要发现单调性，如果 $[l,r]$ 这个区间符合条件，那么左端点变为 $l+1$ 的话，
右端点只有变大才有可能可以更新答案。所以就是每次右端点要变成可能中的最大值。
右端点每次从 $r \sim n$ 枚举找最大值不现实，
我们考虑优化，记录一个后缀的 $\max$ 数组，每次跳 $\max$ 即可。

E-小雨的矩阵

送分题，从 $(1,1)$ 爆搜到 $(n,n)$ ，把答案去一下重即可。

F-小石的妹子

我们发现妹子们之间是有拓扑的关系的，比如妹子 $i$ ,她一定只能在 $a_i,b_i$ 都比她大的妹子的后面。
所以 $n^2$ 的做法就是暴力连边，然后拓扑求解， $rk[i]=max\{rk[j]\}+1\ (a_j>a_i \& b_j>b_i)$ 。
满分做法：
这不就是二维数点问题，咋做都对啊。
因为有两维的限制，所以我们先按 $a_i$ 从大到小排一下序，
对于排序后的第 $i$ 个妹子，她的排名就是 $max\{rk[j]\}+1\ (b_j>b_i)$ ，
那么我们把排名 $b_i$ 当成下标，把 $rk_i$ 当成值，用线段树维护一下区间 $\max$ 即可。

G-小石的图形

发现半圆时面积最大（显然）。 $n=\pi R , R=\frac{n}{\pi}$
面积 $S=\frac{\pi R^2}{2}=\frac{n^2}{2 \pi}$

H-小阳的贝壳

区间 $\gcd$ 具有结合律，很容易用线段树维护，考虑如何区间修改。
首先要知道 $\gcd$ 的一个性质： $\gcd(a,b) = \gcd(a,b-a)$
$\gcd(a,b,c) = \gcd(a,b-a,c-b) = \gcd(a,\gcd(b-a,c-b))$
所以我们可以在线段树上建立差分数组，维护区间和与区间 $\gcd$ 。
显然区间 $[l,r]$ 的 $\gcd$ 就是 $\gcd(\sum\limits_{i = 1}^l f_i,\gcd\limits_{i = l + 1}^r f_i)$ ，其中 $f$ 表示差分数组。
至于第 $2$ 个操作完全就是来搞笑的（主要用来引导别人联想到差分），只要维护差分数组的区间 $\max$ 和区间 $\min$ 就行了。最后的答案就是区间 $\max$ 与区间 $\min$ 相反数的较大值。

I-石头剪刀布

简单的 期望DP+高斯消元 。 $f[i]$ 表示从 $i$ 走到 $n$ 的期望步数。 $f[i]=A \times f[i+1]+B \times f[i]+ (1-A-B) \times f[i-1]+1$
$f[n]=0$
直接高斯消元是 $n^3$ ，能过。
但可以有更优秀的做法：
发现 $f[i]$ 之和 $f[i-1],f[i],f[i+1]$ 和一个常数项有关，
是稀疏矩阵，直接手动高消（即不要 $\rm for$ 循环，直接把要消元的消一下即可）

J-小雨坐地铁

考虑分层图最短路。
很容易想到建 $m$ 层图，如果多条地铁线都经过同一个点，则在这些点之间暴力两两连边，这样连边是 $O(nm^2)$ 的，可能会超时。
我们可以多建一层虚点，所有点到它对应的虚点不需要代价，从虚点到它对应的点需要对应的代价，这样就可以优化到 $O(nm)$ 建图。最后跑一边最短路就好了。

2025最新求职资料大礼包领取

大家都在关注

校招日程表笔试日历 ai模拟面试面试宝典剑指offer 知识点专项练习

已采纳

采纳

精彩回帖

精彩

全部评论

(10) 回帖

加载中...

话题同步到我的动态回帖