目录

最近做的题 ver 2019.12

弹指一挥间实习五个月了,虽然经常很忙,但偶尔也能抽出时间想一想做几个题。感觉最近也比较摸,不记一下真就快忘光了,还是写一下实习以来做的题的简单题解,防止手生吧。

Codeforces 1265E

期望 DP。话说回来我期望 DP 好像没做过几个题,感觉还是不大懂,有机会补一下。

题目很简单,Cretnx 面前有 $n$ 面镜子,每天会有 $p_i$ 的概率通过这面镜子,有 $1-p_i$ 的概率无法通过。通过了镜子第二天前往下一面镜子,没通过则回到第一面镜子,问通过所有镜子(最后一面镜子也得通过,相当于到达不存在的第 $n+1$ 面镜子)的期望天数。

考虑每面镜子是一个点,每个点有 $p_i$ 的概率转移到下一个点,有 $1-p_i$ 的概率回到第一个点,那就变成了一个常见的模型:有向图路径长度期望 DP。

我们同样设计状态:假定最终目标是点 $n+1$,$f_i$ 定义为从点 $i$ 出发到 $n+1$ 这个点的期望天数,那么我们倒序 dp,答案就是 $f_1$,$f_{n+1}=0$。类比有向图的转移方程,我们很容易写出来现在转移方程: $$ f_i = p_i f_{i+1}+(1-p_i)f_1+1 $$ 解释应该是很简单的,我们从点 $i$ 出发,有 $p_i$ 的概率走到下一个点,有 $1-p_i$ 的概率返回第一个点,那么我们期望到终点的天数就是这两种情况之一。而我们怎么选都要多一天,所以要加 1。

这个转移也可以通过全期望公式 $E(X) = E[E(X|Y)]$,那么就是给定我到了点 $i$,前往后两个点的期望的和,根据线性性,1 被提出来,答案符合上式。

但是很尴尬的是,我们看 $f_1=p_1f_2+(1-p_1)f_1+1\implies f_1=f_2+\frac{1}{p_i}$。嗯?我们所有的递推式都需要 $f_1$,但是 $f_1$ 依赖了 $f_2$,这不就循环依赖了,高斯消元?

让我们再推几个式子:$f_1=f_3+\frac{1}{p_1p_2}+\frac{1}{p_2}$,$f_1=f_4+\frac{1}{p_1p_2p_3}+\frac{1}{p_2p_3}+\frac{1}{p_3}$,……

最终我们极易得到 $f_1=f_{n+1}+\sum_{i=1}^n\prod_{j=1}^i\frac{1}{p_{n-i+1}}$。注意到 $f_{n+1}=0$,这个题就做完了。把所有值读进来然后倒序求一个倒数后缀积就行,逆元需要注意一下,复杂度 $\mathcal{O}(n)$(求逆元是个常数)。

SPOJ KGSS

给定 $n$ 长度的序列 $\{a_i\}$,$q$ 次操作,处理下面两种事件:

  • 更新 $a_i$ 的值为 $x$。
  • 求 $\max\{a_i+a_j\}, i\ne j, i, j\in[l, r]$。

这种一眼看出来就是线段树,第二个操作显然是区间最大和区间次大,然后第一个事件只有单点修改还不传标记,维护难度大大降低。

这个题区间次大的维护有点说法,考虑左右两个区间的值合并,你有四个数,四个数里面求一个最大和求一个次大然后更新当前节点,查询的时候也是查出来四个数再合并。注意到对于某个点我们只有一个值,不存在次大,所以某个点的次大值应该是 $-1$ 而不是这个值本身。然后这个题做完了。

Project Euler 183

定义 $P(n,k)=(\frac{n}{k})^k, k\in\mathbb{N}^+$,$M(n)=\max P(n,k)$,$D(n) = n$ 如果 $M(n)$ 是一个有限小数,否则 $D(n)=-n$,求 $\sum_{n=5}^{10000}D(n)$。

看看 $P(n,k)$,掏出来 WolframAlpha,立即可得 $k=\frac{n}{e}$ 时最大,即 $M(n)=P(n, \frac{n}{e})=e^{\frac{n}{e}}$。然后呢,这东西是不是有限小数怎么整?

注意到要求,我们可以确定 $k$ 是最接近 $\frac{n}{e}$ 的整数,另一个观察是,有限小数的有限倍幂一定是有限小数。所以,我们问题就变成了求 $\frac{n}{k}$ 是不是有限小数了。 假设它是,则考虑小数形式下共有 $d$ 位,则乘 $10^d$ 次方一定为一个正整数,也就意味着 $k|(10^d\cdot n)$。我们对分子分母求一下 $\gcd$,易得 $k=2^{\alpha}5^{\beta}p$,则一定有 $p|n$。所以,我们贪心的干掉 $k$ 里面的 $2$ 和 $5$ 因子,再判断一下最后结果能不能被 $n$ 整除就可以了。

Codeforces 77E

学了个新科技,圆的反演变换。具体怎么反演的网上应该有很多教程,找个博客看看就行,还是挺简单的。

题意比较清晰,给定一个大圆和两个小圆,两个小圆在大圆内部,三圆圆心共线且两两相切,问往第二个小圆上方不断添加与第一个小圆,外侧大圆以及前一个圆相切的圆,第 $n$ 个圆的半径是多少。

直接以第一个小圆和外侧大圆切点为反演中心,任意反演半径反演三个圆,极易画出下面的图:

img/recent-problem-2019-12-13/1.png
图 1

假设反演半径为 $1$,那么很容易得到 $|OA|\cdot|OA'| = |OB|\cdot|OB'|=1$,极易解出 $|OA'|$ 和 $|OB'|$。设反演后的圆半径为 $r'$,则 $r'=\frac{|OA'|-|OB'|}{2}$。然后就能得到 $|OO_1|=|OB'|+r'$,而 $|O_1O_n|=2nr'$,则 $|OO_n|$ 就很好求了,勾股定理一下。之后立刻就有 $|OP'|=|OO_n|+r', |OQ'|=|OO_n|-r'$,按照 $|OP|\cdot|OP'|=|OQ|\cdot|OQ'|=1$ 反演出来 $|OP|$ 和 $|OQ|$,那么第 $n$ 个圆的半径就是 $\frac{|OQ|-|OP|}{2}$,这个题就做完了。每个圆求解只需要 $\mathcal{O}(1)$,所以总复杂度 $\mathcal{O}(t)$。

要注意反演圆的圆心不是原先圆的圆心反演,这个东西我上来以为是对的然后推了三个式子发现各自不等啊,直接拉闸。

还有个后续题,HDU 6158,其实就是同样的过程然后反演一下就行。选个合适的反演半径化简一下式子,然后注意到不需要枚举到 $n$,枚举到对答案没有贡献即可。注意一下精度就变成套路了。

杂题

  • HihoCoder 1142:我没写过三分,都是我队友写的,所以我也写一下三分。我写了,一发 A 了,有什么好说的?

  • Project Euler 258:给定 $$ \begin{cases} f_i=1,&0\le i\le1999 \\f_i=f_{i-2000}+f_{i-1999},& 2000\le i \end{cases} $$ 求 $f_{10^{18}}\ \text{mod}\ 20092010$。有经验的选手肯定就是一个 $\mathcal{O}(k^3\log n)$ 的矩阵快速幂,然后发现 $k=2000$ 拉闸。
    这个题标准做法是用 Cayley-Hamilton 定理优化线性递推成一个 $\mathcal{O}(k^2\log n)$ 的过程再求。我在这里写不是因为我会这个方法,而是我去搜了一个 dls 的 BM 板子,枚举了 4000 项一发就莽过去了。 这件事教育我们,出题不要出线性递推,不然你死都不知道怎么死的。