2019-07-16 20:02 已编辑 C++

关注

【题解】牛客小白月赛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)$ 建图。最后跑一边最短路就好了。

全部评论

推荐最新楼层

nust

Java

括号里左边应该是从1到L求和吧？

点赞回复

发布于 2019-07-13 20:59

hhhhhhhhh1

门头沟学院电子信息类

有标程吗

点赞回复

发布于 2019-07-12 22:23

阅文集团

校招火热招聘中

官网直投

申屠志刚

Java

什么意思呀

点赞回复

发布于 2019-07-13 08:14

何人听我楚狂声的小迷弟

字节跳动_Tiktok-音乐_客户端开发工程师

what's mean?

点赞回复

发布于 2019-07-13 10:16

Misakas

Java

A题能解释一下吗

点赞回复

发布于 2019-07-13 13:58

bycore

-_-

D题直接二分答案为什么过不了？

点赞回复

发布于 2019-07-13 17:47

萝卜朝天椒

字节跳动_pico_前端

能解释一下这个吗？谢谢发现 f[i]f[i] 之和 f[i−1],f[i],f[i+1]f[i−1],f[i],f[i+1] 和一个常数项有关，

点赞回复

发布于 2019-07-13 22:30

zdragon_

后端

能解释一下I题建矩阵为啥最后一列为1，关系式移项后应该是0吧

点赞回复

发布于 2019-07-14 01:50

qin_peng

百度_后端开发工程师

#include<bits/stdc++.h> using namespace std; const int N=2e6+10; int p[N]={0}; int dp[N],Index[N]; int t=0; int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ int x; scanf("%d",&x); p[i]=p[i-1]+x; } for(int i=0;i<=n;i++){ if(!t||dp[t]>p[i])dp[++t]=p[i],Index[t]=i; } int ans=0; for(int i=n;i>=1;i--){ while(Index[t]>=i)t--; while(t>0&&p[i]-dp[t]>0)ans=max(ans,i-Index[t]),t--; if(t==0)break; } cout<<ans<<endl; } 我D题是建一个单调递减的数组，每次从后面往前面更新，这样就过了，但是我感觉这样做法有点错误。😂😂

点赞回复

发布于 2019-07-16 16:05

ztranscript

Java

楼主，请教一下，C题，先将石块排序了，不会改变水位上涨后，分块的数量吗？emmm....😃

点赞回复

发布于 2019-08-03 16:25