Whisper-6's Blog!

题意：对一棵 的线段树等随机进行 次区间覆盖（在 个区间中等概率随机），问最终产生的有标记节点的期望个数。

，，时限 。

题意：维护线段树集合 。初始时， 中只有一颗 的线段树。

支持下列操作：

• 将每棵线段树复制两份，其中一份执行区间覆盖。

• 查询目前所有线段树中，有标记的节点个数。

，时限 。

题意：给出一张 个点的无向图，求将点集划分为一个独立集和一个团（均非空）的方案数。

，时限 。

题意 ： 给出一张 个点 条边的无向图，边有边权，可正可负。

两人轮流对点染色，先手将点染成黑色，后手将点染成白色，每个点只能被染色一次。

记 为点集 的导出子图的边权和。

设最终黑色点的集合为 ，白色点的集合为 ，则这轮游戏的得分为 。

先手想最大化这个值，后手想最小化这个值，若两人均采用最佳决策，问最终游戏的得分。

，，时限 。

题意：给定一棵 个点的有根树，以 为根。

树用如下方式给出：给出 ，保证 ，将 与 连边形成一棵树。

接下来有 次操作，操作有两种： - 1 l r x 令 。 - 2 u v 查询在当前的 数组构成的树上 的 LCA。

，时限 。

题意： 给出一张无向连通图，删除一个既不是空集又不是全集的点集，使得剩下的点度在 下不变。或指出无解。

多组数据，，时限 。

题意：给出平面上的 条直线，定义可重点集 包含所有直线两两的交点。如果某个点作为交点出现了多次，其在 中也会出现多次。

给出询问点 ，定义 为 中各个点到 的距离，求 中前 大的元素和。

，，时限 。

题意：在一个 的矩阵中有 个点，求至少含有 个点的子矩阵个数。

，，时限 。

题意：给出一棵 个节点的树，以 为根。

树上有若干个果实，第 个果实位于节点 ，且会在第 天成熟，若收获可以获得 单位的果汁。保证每个节点上最多只有一个果实。

收获的方式是断掉树上的一条边 ，其中 是 的父亲。此举会收获所有 子树内恰好在当天成熟的果子。

在这之后，断开的整颗子树都会被丢弃。

求最多可以获得多少单位果汁。

，时限 。

题意：一条无限长的管道中有 个粒子，第 个粒子的位置为 。

一次实验开始时，第 个粒子会获得 的初速度并匀速运动，有 的概率向右移动， 的概率向左移动。

当任意两个粒子移动到相同位置的时候会发生碰撞。

设该实验所消耗的时间为第一次发生碰撞的时间。若不会发生碰撞，则认为这次实验耗费的时间为 。

求一次实验期望耗费的时间，对 取模。

，时限 。