朝田诗乃 的博客

朝田诗乃 的博客

[LnOI2019]长脖子鹿省选模拟赛 题解

posted on 2019-03-07 08:14:35 | under 未分类 |

T1 [LnOI2019SP]快速多项式变换

这是一道签到题。想必各位dalao都AC了吧。

对于100%的数据,将m带入此多项式,

$$f(m)=a_0+a_1m+a_2m^2+a_3m^3+ \cdots +a_nm^n$$

不难发现,设 $a_na_{n-1}\cdots a_2a_1a_0$ 是一个 $m$ 进制数,将此数转换为10进制即为 $f(m)$ 的值。因此只需要倒序输出 $f(m)$ 在 $m$ 进制下每一位的值即可。

总复杂度 $O(logn)$

题解By 朝田诗乃

T2 [LnOI2019]加特林轮盘赌

说这个题目的 $n$ 是 $10^4$ ,当 $n=0$ 和 $n=1$ 的时候答案是显然的,然后我们考虑两个人的情况。比方说两个参赛者,一个yyy,一个雪碧。先崩yyy,如果他 $P_0$ 的概率崩死了,那yyy没了,剩一个雪碧,雪碧赢了;如果他 $(1-P_0)$ 的概率没死,那么游戏要继续呀。雪碧来到了第一位,yyy相当于到了第二位。其实这个局面,和开枪前没有区别,只不过是yyy和雪碧互换了位置罢了。

//以上题解由 $X$ 口述,朝田诗乃记录。

这样,我们设 $F[2][1]$ 表示第一个人最终幸存的概率, $F[2][2]$ 表示第二个人最终幸存的概率。

$$ F[2][1] = P_0 * 0 + (1-P_0) * F[2][2] $$

作为一个二元一次方程,我们还需要一个等式才能解出他们,不难想到:

$$ F[2][1] + F[2][2] = 1 $$

K个人呢?头两个式子我们可以抄上面的啊!

$$ F[n][1] = (1-P_0) * F[n][n] $$

$$ F[n][1] + F[n][2] + ... F[n][n] = 1 $$

当前我们在崩第1个玩家,这个时候排在第k位玩家的概率会是怎么样的呢?

概率 $1-P_0$ :如果第一个玩家没被崩死,所有人都向前走了一步!

$$F[n][k] -> F[n][k-1]$$

概率 $P_0$ :如果第一个玩家被崩死,所有人还是都向前走了一步!

$$F[n][k] -> F[n-1][k-1]$$

不过因为死了一个,所以总人数也少了一个。

故:

$$ F[n][k] = P_0 * F[n][k-1] + (1-P_0) * F[n-1][k-1] $$

这一共能给你 $n$ 个等式。

由于最后有且仅有最后一个幸存者,所以有

$$\Sigma_{k=1}^{n}F[n][k] = 1$$

解n元一次方程,高斯消元能拿10pts。

手动消元就能100pts了。

最后要特判一下 $P_0=0$ 的情况。

总复杂度 $O(n^2)$

题解By X

//朝田诗乃:居然被那么多人水过了QAQ

T3 [LnOI2019]东京夏日相会

这题可能是全比赛最水的一题,果然诗乃还是比较菜

考虑将圆拆成点。我们在圆上均匀取点。设此时处理的圆半径为 $r$ ,每隔 $d$ 度圆心角取一个点。可以证明当 $d ≤ acos(1-0.005/r)$ 时所得的答案与标准答案差距不超过 $0.01$ .证明是初中基础数学请各位自己推一下。

剩下就是解决最小圆覆盖点的问题了。请移步P1742

总复杂度期望 $O(n)$

随机/退火本来想卡一下的,但后来还是放宽了精度限制QAQ

题解By 朝田诗乃

T4 [LnOI2019]第二代图灵机

对于20%的数据,对于每个Q操作,用 $O(n)$ 的复杂度在 $[l,r]$ 之间进行尺取(若熟悉尺取法可跳过):

对于3操作,

定理1 :若一个合法区间 $[l_1,r_1]$ 被另一个合法区间 $[l_2,r_2]$ 包含,则 $[l_2,r_2]$ 一定不是最优解。

由于数字都是正整数,证明显然。

定理2 :若一个区间 $[l_1,r_1]$ 是合法区间且 $[l_1,r_1]$ 内不包含其他合法区间,则 $[l_1+1,r_2](l_1+1 ≤ r_2 ≤ r_1)$ 一定不是一个合法区间。

这好像是废话

因此我们可以枚举左端点和与其对应的最优右端点,记为 $f(l)$ ,则 $f(l)$ 单增,枚举复杂度 $O(n)$ 。

对于4操作,尺取,过程与3几乎没有任何区别这里不在赘述。

对于100%的数据:

使用珂朵莉树(ODT,又称老司机树)维护颜色序列,由于数据随机,可将所求区间 $(l,r)$ 中的节点个数降到 $log$ 级别(证明百度,我也不记得为什么了),同20%做法进行暴力尺取。使用线段树维护区间数字和以更新答案。特别的,对于4操作,直接尺取可能丢失某些情况,因此我们还需要维护区间数字最大值。(这个实现的时候就会知道了)

在随机数据情况下,总复杂度 $O(nlog^2n)$

题解By 朝田诗乃

数据与标程下载:点这里

提取码:f2c4

hanabi0和hanabi8是错误数据,忘记更新包了,实际测试时用hanabi1和hanabi9分别替代了,大家当没看见就好惹