牛客小白月赛(16)

发布于 2019-07-13  404 次阅读


牛客小白月赛(16)的题解

认真写的自己写着玩玩而已

导航

A.小石的签到题

B.小雨的三角形

C.小石的海岛之旅

D.小阳买水果

E.小雨的矩阵

F.小石的妹子

G.小石的图形

小石的签到题

这是一道困难(划掉)简单的签到题,不过当时我做的时候脑抽了,搞复杂了!!!!!

题目

    小石和小阳玩游戏,一共有n个数,分别为1∼n。两人轮流取数,小石先手。对于每轮取数,都必须选择剩下数中的任意一个数x,同时还要取走x,\dfrac{x}{2},\dfrac{\dfrac{x}{2}}{2}… 如果某个数不存在,就停止取数(不能一个数都不取)。谁取走最后一个数,谁就输了。小石想知道自己能否获胜。 如果小石能赢,输出 “Shi”,否则输出 "Yang”(均不输出引号)。

时间限制:C/C++ 1秒,其他语言2秒。空间限制:C/C++ 262144K,其他语言524288K。1 \leq n \leq 10^9

样例

输入

 1(共一行,输入一个数)

输出

 Yang(共一行,输出 "Shi""Yang"(不输出引号)。

代码

说明

题目很简单,不要想复杂一定可以做的出来,当n>1的时候,小石一定会赢,无论如何,小石一定会拿掉1,所以小阳也要拿,但此时1不存在所以游戏结束,小石赢。

小雨的三角形

如果你像我一样,大致看了题目就开始写的话,肯定(划掉)应该不会犯和我一样的错误,期初我以为这是个杨辉三角,毕竟给的说明有点像。它是这样的:

题目

小雨手上有一个填满了数字的三角形。这个三角形一共有 n层,其中第i层共有i个数,且第1个数和第 i个数均为i。其余的数中,第j个数是上一层中第j−1个数和第 j个数的和。小雨想知道这个三角形第x层到第y层所有数的和,一共有m个询问。
时间限制:C/C++ 1秒,其他语言2秒。空间限制:C/C++ 262144K,其他语言524288K。1 \leq n \leq 10^3 1 \leq m \leq 10^3 1 \leq x \leq y \leq n

样例

输入

第一行两个正整数,m,表示这个三角形的层数和询问个数。接下来m行,每行两个正整数x,y,表示一次询问。

 5 3
 1 2
 1 5
 3 5

输出

输出共m行,每行一个整数,表示一组询问的答案,对10^9+7取模。

 5
 83
 78

代码

 

说明

这个题我们可以爆算(划掉)先通关推到求出第x~y层的和是多少,然后直接算和即可。当然我们还需要写一个次方函数方便我们取模计算。(注:每行的和的公式是:3*2^{n-1}-2,而x~y行的和为:3*2^{n-1}*(2^{m-n+1}-1)-2^{m-n+1})

小石的海岛之旅

小石啊小石好好旅游不好吗,观察什么水位啊!!!!!!!!!!!

题目

暑假到了,小石和小雨到海岛上玩。
从水平方向看海岛可以看成n个小块,每一个小块都有一个高度h_i,水位一开始为0,随着水位的上升,海岛分成了若干块。m个询问,求当水位为a_i时,海岛会分成多少块。

时间限制:C/C++ 1秒,其他语言2秒。空间限制:C/C++ 262144K,其他语言524288K。1 \leq n,m \leq 10^3 1 \leq h_i \leq 10^3 1 \leq a_i \leq a_{i+1} \leq 10^3

样例

输入
第一行输入两个正整数n,m,分别表示海岛小块个数和询问个数。第二行输入 n 个整数 h_i,表示每一块的高度。第三行输入 m个整数 a_i,表示每一个询问,保证输入的 a_i 单调递增。

7 3
1 2 3 1 2 1 3
1 2 3

输出
共 m 行,分别对应 m 个询问的答案。

3
2
0

代码

说明

这个题我只能想到直接暴力了,>a_i让判断开关k为真,如果小于且k是真,那就+1,然后再重置k就行。

小阳买水果

买个水果真麻烦,难道自己不喜欢的水果就不吃了????(划掉),不吃自己不喜欢的水果很正常,但这个老板的售卖方式很奇葩。不过像我这样看成只买喜欢的水果的人没多少了吧!

题目

水果店里有 n个水果排成一列。店长要求顾客只能买一段连续的水果。小阳对每个水果都有一个喜爱程度 a_i,最终的满意度为他买到的水果的喜欢程度之和。如果和为正(不管是正多少,只要大于 0 即可),他就满意了。小阳想知道在他满意的条件下最多能买多少个水果。你能帮帮他吗?

时间限制:C/C++ 1秒,其他语言2秒。空间限制:C/C++ 262144K,其他语言524288K。1 \leq n \leq 2*10^6,|a_i| \leq 10^3

样例

输入
第一行输入一个正整数 n,表示水果总数。第二行输入 n 个整数 a_i,表示小阳对每个水果的喜爱程度。

5
0 0 -7 -6 1

输出
一行一个整数表示结果。(如果 1 个水果都买不了,请输出 0)

1

代码

说明

(一个数组用来记录前缀和,一个用来记录位置,对一段水果喜欢程度求和,记录最大值,不断更新即可,如果没有喜欢程度>0的,直接出0,即可。

小雨的矩阵

啊!!!!!!!!1好小的数字,好宽裕的时间,爆算开始;

题目

小雨有一个 n×n 的矩阵,起点在(1,1),终点在(n,n),只能向下或向右走,且每次只能走 1 步。矩阵上每个点都有一个点权 a_{i,j} 。求走到终点的路径有多少不同的点权和。

时间限制:C/C++ 1秒,其他语言2秒。空间限制:C/C++ 262144K,其他语言524288K。1 \leq n \leq 8,0 \leq a_{i,j} \leq 50</span

样例

输入
第一行,输入一个正整数 n 。接下来 n+1 行,每行 n 个数,表示 a_{i,j}

2
1 5
2 4

输出
共一行,输出有多少不同的点权和。

4

代码

说明

暴力遍历,从(1,1)到(n,n),输出有多少种就好

小石的妹子

这个题划掉,我没有妹子,不做

题目

小石有 n 个妹子,每个妹子都有一个细心程度 a_i 和一个热心程度 b_i ,小石想给她们一个重要程度 ti(重要程度为 1 表示最重要,重要程度越小表示越重要)。如果一个妹子 i 的细心程度和热心程度都比妹子 j 大,那么妹子 i 的重要程度要大于妹子 j 的重要程度,即妹子 i 比妹子 j 重要。
流程如下:每次从所有没有重要程度的妹子中,找到若干妹子。对于这些妹子的任意一个,需要保证没有其他妹子比她更重要。然后把她们的重要程度标为 1 。下一次再从剩下没有重要程度的妹子中找到若干妹子,依然符合上述条件,然后把她们的重要程度标为 2,……,重复直到所有妹子都有自己的重要程度。
由于妹子太多,小石忙不过来,请你帮帮他。

时间限制:C/C++ 1秒,其他语言2秒。空间限制:C/C++ 262144K,其他语言524288K。1 \leq n \leq 10^5,1 \leq a_i,b_i \leq 10^9

样例

输入

接下来 n 行,每行两个正整数 a_i,b_i,描述每个妹子的细心程度和热心程度。 a_i 两两不等,所有的 b_i 两两不等。

5
1 4
2 2
3 3
4 1
5 5

输出
共 n 行,第 i 行输出一个正整数 t_i表示第 i 个妹子的重要程度。

2
3
2
2
1

代码

 

说明

小石的图形

又是一道不用动脑子的题,公式即可。

题目

小石想在一面墙旁边建造一段长度为 n 的篱笆来围出一块地(如图)。求最大的地的面积。

时间限制:C/C++ 1秒,其他语言2秒。空间限制:C/C++ 262144K,其他语言524288K。0 \leq n \leq 10^3

样例

输入
共一行,输入一个整数 n 。

1

输出
共一行,输出最大面积,保留 3 位小数。

0.159

代码

说明

我们不难发现:半圆时面积最大(显然)。 n=πR,R=\dfrac{n}{π},面积S=\dfrac{πR^2}{2}=\dfrac{n^2}{2π}

未完待续


Σσ(・Д・;)我我我什么都没做!!!