校内OJ 2019.3.10 NOIP 模拟赛

Rating 上了一点,考试时本来可以多得五十分的。。

P1  A^B Problem

题面

给出 $A$ 和 $B$,求 $A^B$ ,其中 $A$ 为浮点数,输出也为浮点数。

思路

高精水题,先去掉小数点求幂,再加上即可。

有 Python 打什么高精

P2 猜数游戏

题面

有一个 $n$ 个数的可重集合,小 A 会选择一个数,但不会告诉你这个数,让 B 猜它的最小质因数。B 每次可以选出一些数,问 A 他选择的数属不属于这个集合,A 只回答 “是” 或 “否”。

B 想知道最优方案中,最坏情况下要询问几次,和最小的期望询问次数。

思路

题目问的是最小质因数,所以和集合内的数没关系,直接处理出每个数的最小质因数。

对于最坏情况下的询问次数,即是二分的次数。设最小质因数有 $k$ 种,答案为 $\left \lceil log_2(k) \right \rceil$。

最优情况下,使用贪心策略,在每种质因数个数的集合中每次取两个最大值,累计期望,然后再插入这两个值的和,直到集合还剩下一个元素为止。(类似于合并果子)

代码

P3 洪水 (富金森林公园)

题面

洛谷 P3616 – 富金森林公园

思路

因为高度 $h_i <= 10^9$ 所以先离散化一遍。

然后用线段树维护每个高度贡献。(差分思想)

几乎是照着题解打的,有空要再打一遍。

代码

 

暂无评论

发送评论


				
上一篇
下一篇