01-28模拟赛

01 / 28 / 2020 | 最后修改于 01 / 28 / 2020

「Splay」

题目描述

给一棵Splay，只要求rotate操作，定义每个节点的权值为子树内权值和，求任意节点子树内的权值积。

题解

考虑Splay的性质：rotate不影响中序遍历。

具体来讲，每次rotate实际只影响两个点的子树和，以中序遍历为下标用线段树维护区间积，每次rotate单点修改，区间查询。

「进化序列」

题目描述

Abathur 采集了一系列 Primal Zerg 的基因样本，这些基因构成了一个完整的进化链。为了方便，我们用 $A_0,A_1,\cdots,A_{n-1}$ 这 $n$ 个正整数描述它们。 一个基因 $A_x$ 可以进化为序列中在它之后的基因 $A_y$ 。这个进化的复杂度，等于 $A_x|A_{x+1}|\cdots|A_{y-1}|A_y$ 的值，其中 $|$ 是二进制或运算。 Abathur 认为复杂度小于 $M$ 的进化的被认为是温和的。它希望计算出温和的进化的对数。

题解

做法其实很多，这里采用了来自 STDquantum 的ST表+二分的做法。

用ST表做到 $O(1)$ 查询区间或，枚举每个右端点，二分最靠左的可行端点统计答案。

「饥饿的小鸟」

题目描述

一群饥饿的小鸟，要到河对岸吃东西。河的宽度为 $N$ 米，小鸟每飞行 $L$ 米就必须在一片荷叶上休息一下，才能够继续飞行。当然，小鸟们也可以选择没飞够 $L$ 米就先休息一下，但不能一次飞超过 $L$ 米。距离小鸟们出发的河岸一侧距离为 $i$ 的荷叶共有 $A_i$ 片，每片荷叶在有小鸟停于上方休息后，就会沉入水底，不能够再供其他小鸟休息。现在想要知道，至多有多少只小鸟能够抵达对岸。

题解

贪心乱搞。一只鸟一定跳到能跳到的最远的地方最优。注意实现的时候要一堆一堆的跳。

「旅行」

题目描述

给定一棵树。将1号节点作为整棵树的根。 每个节点有一个旅游热度 $A_i$ 和影响力 $D_i$ 。每个节点设置了一个向往值 $f_i$ ，它等于所有的 $A_j$ 之和，满足 $i$ 点在 $j$ 点向根节点走 $D_j$ 步的路径上（经过一条边算一步，$i=j$ 也会 被统计，如果 $D_j$ 步超过了根节点，则超出部分不用管）。每条边将有一定的概率出现。现在他有 $Q$ 个询问，每次询问某个节点所在的联通块中所有节点的 $f_i$ 值的和的平方的期望（对998244353取模）

题解

第一步先求出每个点的 $f_i$ ，这个可以用栈维护一个点到根路径上的所有点，树上差分一下就好了。 第二步考虑求期望，先考虑以1为根，树形DP一下

$$E_x = \sum_{v \in son_x} E_v \cdot w$$

最后换根DP一下，平方的话套公式就好了

E_