NOIP2019模拟赛(二)03.10

T1

题意

题面

给定两个数$a$,$b$求出$b$个$a$相乘的结果。

数据范围

保证$a \leq 99.9999 ,b \leq 25$且$a$的有效数字不超过$6$位。

思路

对于20%的数据

你开$long\quad double$就好了呀。

对于100%的数据

你写高精度就好了呀。
说得很轻巧,但是打比赛的时候花了30分钟。。。
差不多分两个步骤:
1. 把$a$的小数转化为整数,并且求出$a^b$
2. 然后再点一个小数点就好了
坑:0.52要输出成.52。
其他没啥了。

T2

题意

有两个人很无聊地在玩猜数游戏。某个人想出来一个$n$个正整数的集合,然后选择一个数,让另外一个人猜他选的数的最小质因子。
问:在最优的方案中,最坏情况下需要询问几次,以及最小的询问期望次数?
注:询问期望次数是所有数需要的询问次数的平均值,最坏情况的询问次数为所有数的询问次数的最大值。

思路

很显然这道题和小学奥数题很像。就比如说问有$1$~$n$的数,怎样询问能最少?
显然是$log2$次。
就像这样:↓↓↓

那么对于第二个询问呢?和Luogu的合并果子很像。
Luogu 合并果子
其实就是利用哈夫曼树的原理,每次寻找最小的两个像上面一样$log2$地合并起来就好了。
可以使用$priority$_$queue$的小根堆。
注意:这道题会卡时,所以需要预处理出素数。

T3

题意

这和Luogu某题很像

题面

有$n$块石头,有$m$个询问。首先给出这$n$块石头的高度。然后对于每一次的询问有两种:
1. 读入一个整数$x$,询问大于或等于的连续的石头的部分的个数。
2. 读入两个整数$x,y$,表示将第$x$块石头的高度修改为$y$。

样例输入

5 4
8 6 3 5 4
1 5
2 4 1
1 5
1 3

样例输出

2
1
2

样例解释

第一次询问时,洪水高度为$5$ ,露出水面的岩石的编号为${1,2,4}$连续的部分为${1,2}$和${4}$,答案是$2$ 第二次询问时,洪水高度为$5$,露出水面的岩石的编号为${1,2}$连续的部分为${1,2}$,答案是$1$ 第三次询问时,洪水高度为$3$,露出水面的岩石的编号为${1,2,3,5}$连续的部分为${1,2,3}$和${5}$,答案是$2$

思路

对于50%的数据

我们可以采用暴力~(废话)~
所以我们就对于每个查询询问暴力。
结果真的只有50分。。。~(出题人也太狠了吧)~

对于100%的数据

通过观察,我们可以发现,对于每一个询问$Q$,其实就是寻找满足:$h[i-1]<Q \leq h[i]$的个数。
那么我们就可以先暴力预处理出如果$h[i-1]<h[i]$那么$(h[i-1]+1,h[i])$这个答案区间就可加$1$。而对于每一个询问,只需要输出答案区间内的$Ans[Q]$即可。对于每一个修改,影响到的只有$h[i-1]$与$h[i+1]$所以,再重新分别判断一次即可。
注意:每一次的修改需要先清空上一次对于该点的修改。

暂无评论

发送评论


				
上一篇
下一篇