牛客OI周赛13题解

0还是1

30分做法

爆搜。

60分做法

对于最后一个运算为异或的情况，不管前n个组成了什么，都可以通过最后一个数字调节为1。所以答案就是 $2^n$

100分做法

用 $f[i][0/1]$ 表示进行了前 $i$ 次运算之后，得到0,1的方案数。

如果当前位置的运算符为&。那么运算后为 $1$ ，只能从 $f[i-1][1]$ 转移过来，并且当前位必须为1。

运算后为0，那么可以从 $f[i-1][1]$ 转移过来，也可以从 $f[i-1][0]$ 转移过来，而且从 $f[i-1][0]$ 转移时，当前位置填0或1都是可以的。所以需要乘上2。所以转移方程就是
$ $f[i][0]=f[i-1][0]*2+f[i-1][1]$ $f[i][1]=f[i-1][1]$ $

如果当前位置的运算符为|,与&类似，只是需要将 $f[i-1][1]$ 乘2，转移方程就是
$ $f[i][0]=f[i-1][0]$ $f[i][1]=f[i-1][1]*2+f[i-1][0]$ $

如果当前位置的运算符为^,那么不管前面的运算结果是什么，当前位置都只有一种填的方式将他调整为想要的。转移方程就是:
$ $f[i][0]=f[i][1]=f[i-1][0]+f[i-1][1]$ $

摆动数列

10分做法

爆搜

50分做法

分奇数位较大和奇数位较小两种情况考虑。下面以奇数位较大为例，奇数位较小同理。

首先将所有数字离散化。

显然我们需要将所有满足 $x>y$ 的二元组选出来。用 $f[i][j]$ 表示前i个二元组选出的最后一个二元组的y小于等于j最多可以选出二元组的数量。
转移方程就是 $f[i][y_i]=\max\limits_{j=1}^{i-1}f[j][x_i-1]$

100分做法

观察50分做法，发现其实只需要用个树状数组维护单点修改和前缀最大值即可。

星球大战

简化题意

有一棵树。每次可以攻击树上的某棵子树，然后这棵子树上的每条边有 $\frac{1}{2}$ 的概率消失。定义若攻击以 $x$ 为根的子树，深度 $ht(x)$ 为 $x$ 子树剩余点(与 $x$ 连通)的最大深度。共 $q$ 次操作，两种： $1\ x$ .新建一个节点，其父节点为 $x$ 。 $2\ x$ .询问若攻击以 $x$ 为根的子树， $x$ 子树的期望深度。 $q\leq 5\times10^5$ 。允许有一定精度误差。

记 $size[x]$ 为 $x$ 的子节点个数。

Subtask2(10pts)： $H\leq 2$ ，即 $fa[x]=1(x\neq 1)$

由期望的线性性，考虑计算 $\sum_{h=1}^{MAX\_H}h*p(h)$ 。
我们先考虑这个数据， $H=2$ 好像比较好推。
若询问 $x(x\neq 1)$ 节点，答案为 $0$ ；若询问 $1$ ，z则答案为 $0*p(0)+1*p(1)$ 。 $1$ 子树中任意存在一条边则深度为 $1$ ，所以 $p(1)=1-(\frac{1}{2})^{size[1]}$ 。
复杂度 $O(q)$ 。

Subtask1(20pts)： $Q\leq 21,H\leq 3$

因为深度足够小，假设攻击节点 $1$ ，我们 $2^{size[1]}$ 枚举其子节点的状态（到 $1$ 的边是否保留），所有状态出现的概率都为 $2^{size[1]}$ ；然后对于所有保留了边的子节点 $x$ ，再 $2^{size[x]}$ 枚举 $x$ 子节点的状态...然后求每种状态的状态的深度。
好像不太好写。但我们发现若当前节点只有一层子节点，这和 $Subtask2$ 是一样的；若有两层，则枚举第一层后，这棵子树深度是1还是2的概率同样可以直接算。
复杂度 $O(2^{q})$ 。

Subtask3(10pts)：树退化为链

链的话，路径唯一，若树深为 $h$ 当且仅当子树中连向 $x$ 的 $h$ 条边都存在，第 $h+1$ 条边不存在。即答案为 $\sum_{h=1}^{MAX\_H-1}h*\frac{1}{2^h}*\frac{1}{2}+MAX\_H*\frac{1}{2^{MAX\_H}}$

$MAX\_H$ 为 $x$ 子树最大深度。
复杂度 $O(q*MAX\_H)$ 。

Subtask4(20pts)： $H\leq70$ ，所有询问在1操作之后

放弃枚举，考虑DP。
对于询问，只要 $x$ 有一个子树的深度为 $h$ 且其它子树深度不超过 $h$ ，就可以用 $p(h)*h$ 更新答案。
所以记 $f[x][h]$ 表示以 $x$ 为根， $dep[x]\leq h$ 的概率。则答案为 $\sum_{h=1}^{MAX\_H}h\times(f[x][h]-f[x][h-1])$

考虑如何从 $f[son_x][h-1]$ 转移。每个子节点 $v=son_x$ 有两种情况，一是存在边，对 $f[x][h]$ 贡献 $\frac{1}{2}\times f[v][h-1]$ 的概率；二是不存在该边，概率为 $\frac{1}{2}$ 。
类似多项式，把 $size[x]$ 项乘在一起，即 $f[x][h]=\prod_{v=son_x}(\frac{1}{2}+\frac{1}{2}f[v][h-1])$
（比如，深度为0，对应 $\frac{1}{2}\times\frac{1}{2}\times\ldots\times\frac{1}{2}=\frac{1}{2^{size[x]}}$ ；深度为1，对应 $size[x]-1$ 个 $\frac{1}{2}$ 与一个 $\frac{f[v][h-1]}{2}$ ......）
复杂度 $O(q*MAX\_H)$ 。

Subtask5(10pts)： $H\leq70$

如果新建节点 $v$ ，则影响的点有 $fa[v],fa[fa[v]]\ldots$
因为深度不超过 $70$ ，所以暴力向上更新即可，也就是除掉之前的项，乘上新的项。
复杂度 $O(q*MAX\_H)$ 。

正解：

$h$ 小了我们是可以做的。
事实上，我们不需要考虑很大的深度。假如 $h=100$ ，需要一条长 $100$ 的链，即至少同时存在 $100$ 条边，概率为 $\frac{1}{2^{100}}$ ，非常小。设需考虑的最大高度 $MAX\_H=60$ ，则做法同 $Subtask5$ 。
复杂度 $O(q*MAX\_H)$

对于 $MAX\_H$ 的取值，你可能会认为 $30$ 就足够了，因为 $\frac{1}{2^{30}}$ 已经足够小。事实上，考虑一个菊花图，从根节点延伸出 $\frac{n}{31}$ 条路径，且每条路径长度为 $31$ 。那么以 $1$ 为根树深为 $31$ 的概率为： $1-(1-\frac{1}{2^{31}})^{\frac{n}{31}}$
这是大于 $10^{-6}$ 的。