Whisper-6's Blog!

题意 ： 一颗 个节点的二叉树，每个节点要么有两个儿子要么没有儿子。边有边权。

第一天，你从 号节点出发，走到一个叶子节点。然后每一天，你可以从当前点走到另一个叶子。

最后一天需要回到 号节点。要求到过所有叶子并且每条边经过恰好两次。

每天的路费是你走过的路径上的边权和，你的公司会为你报销大部分路费，除了你旅行中所用路费最高的，且行走路线是从叶子到叶子的那一天的路费。

求你自己最少要付多少路费？

，时限 。

题意 ： 给出一个 个点的有向图，每个点都有恰好一条出边。

保证每个点都能到达 号点，现在要修改一些出边的目的地，使得从任意点出发走 步都恰好到达 。

问至少需要修改多少次出边。

，时限 。

题意：给定一个长为 的序列 ，定义中位数序列 如下 ：

• 的中位数。

给出序列 ，可以将其任意打乱，问能产生多少个本质不同的 。

答案对 取模，，时限 。

题意：有一个长为 的杆，上面有 条绳子，每条绳子可以让蜗牛从 爬到 （中途不能离开），保证 各不相同。蜗牛也可以自然下落。

现在有 次询问，询问 出发，途中高度不能低于 或高于 ，问最高能爬到的位置。

允许离线，，时限 。

题意 ： 给定一棵 个节点的树，边有黑白两色和权值。

求满足黑白边的比例在 内的路径边权乘积的乘积。

答案对 取模。

，时限 。

题意：定义一个长度为 的序列 的权值为： 其中 是在 的区间 中，「所有在该区间内出现过的元素出现次数的乘积」再乘上「区间内所有元素的乘积」。

对于所有长度为 的，值域为 的序列，求权值的期望。

答案对 取模，，，时限 。

题意：一个长度为 的序列 的权值 定义为：

• 时为 。

• 时为它所有子区间的权值之和，也就是

给定一个序列 ，求它的的权值。这个序列非常长，是这样生成的：输入序列 ，令 。

答案对 取模，，，时限 。

题意 ：给出一棵 个节点的树与 条路径（定义为点的集合），问这些路径组成的独立集方案数。

答案对 取模。

，时限 。

题意：给出一个长度为 的排列 。

建立一张无向图，若 为一组逆序对，则在 之间连一条边。

求该图的独立覆盖集数目。（独立覆盖集指即是独立集，又是覆盖集）

数据保证答案不超过 。

，时限 。

题意：给定一个 的排列 ，接下来有 次操作，操作共两种：

1. 交换操作：给定 ，将当前排列中的第 个数与第 个数交换位置。
2. 询问操作：给定 ，请你求出当前排列经过 轮冒泡排序后的逆序对个数。

，时限 。