Hdu6355 Fireflies Hdu6355 Fireflies 发现网上没有什么题解 $\dots$ 题目描述 在一个 $n$ 维度的超立方体，每一维度的大小是 $p_i$。你可以在任意位置放一个萤火虫，萤火虫每次只能在一个维度移动一个单位，对于 $x_i \to y_i$ 需要保证 $x_i + 1 = y_i$，而且不能超过超立方体。 求最开始最少放多少个，才能保证存在一种方案，对于每一个单位空间都有一个萤火虫遍历它。 我们考虑一下，这个是一个覆盖问题，是否可以用上 $dilworth$ 定理。显然最小链覆盖就是最大的反链。考虑对于一个 $n$ 种元素的集合，能选择最多多少个元素两两不包含。 这个问题很简单就是 $\dbinom{n}{\lfloor\dfrac{n}{2}\rfloor}$。 $Sperner$ 定理。 对于这个定理我们其有一个推论就是对于多重集 $S$ 偏序是 $\subseteq$，每个元素出现 $a_i$ 次。最大反链的个数就是大小是 $\dfrac{\sum{a_i}}{2}$ 的集合数量。 我们考虑上面的问题，也就是选择一个集 ...

话说这个专题网上的讲解都没有很全，窝就将他们的总和一下。 如果有问题请私信，评论。 首先说一下最小链覆盖定理，这个本质上是有点抽象的。 $\color{red} \text{偏序集}$的概念： 我们设当前的全集为 $X$。也就是一个 $\color{red}\text{偏序集}$，因为其元素部分可以比较大小。 链对于 $X$ 的一个子集满足其是全序集，及其所有的元素可以比较大小。 反链对于 $X$ 的一个子集，满足其任意非空子集都不是全序集， 即所有的元素不能比较大小。 链覆盖若干个链的并集为 $X$，且两两交集为 $\empty$。 反链覆盖若干个反链的并集为 $X$，且两两交集为 $\empty$。 最长链所有链中元素最多的集合（可以有多个）。 最长反链所有反链中元素最多的集合（可以有多个）。 偏序集高度最长链的元素个数。 最长反链最长反链的元素个数。 狄尔沃斯定理($Dilworth’s theorem$) 最小链覆盖 $=$ 最长反链长度 $=$ 偏序集宽度 最小反链覆盖 $=$ 最长链长度 $=$ 偏序集高度 emmm，其实本质上对于链的定义可以靠自己，但是基本上按照 ...

P4719 【模板】"动态 DP"&动态树分治 P4719 【模板】”动态 DP”&动态树分治 先不考虑修改，可以想到 $\tt Dp$： 设 $f(i, 0/1)$ 表示当前的点是否选择，那么转移可以得到：$$\begin{aligned}f(u, 0) &= \sum_{v \in son_u} \max(f(v, 0), f(v, 1))\f(u, 1) &= \sum_{v \in son_u} f(v, 0)\end{aligned}$$发现每一次进行修改的时候影响的是一条链上的信息，我们不妨将其树链剖分一下，设 $g(u, 0/1)$ 表示亲儿子对应的信息。$$\begin{aligned}g(u, 0) =& \sum_{v \in sonlight_u} \max(f(v, 0), f(v, 1)) \g(u, 1) =& \sum_{v \in sonlight_u} f(v, 0)\end{aligned}$$我们可以把转移变成矩阵：$$\left[\begin{matrix}f(v, 0) & f(v, 1)\ ...

CF1197E Culture Code CF1197E Culture Code 显然 $\tt Dp$ 肯定是不能依赖于体积的。我们考虑选择当前位置的方案。 容易发现每个点能选择的对象构成了一个 $\tt DAG$。 设 $f(i)$ 表示选择了点 $i$ 的最小剩余体积，显然 $f(i) = -in(i) + \min_{j} f(j) + out(j)$，后面的东西直接使用前缀维护即可。 对于方案数我们可以同样维护一个前缀和，但是其代表的是考虑了点 $i$ 得到最终答案是 $f(i)$ 的最小方案。 设 $g(i)$ 表示最终最小值是 $f(i)$ 的时候，考虑了 $1 \sim i$ 的答案。 显然这个东西包含了之前的所有合法方案。 因为如果当前点是终止点，之后不会让其贡献重复叠加。 如果当前点不是终止点，那么其贡献还可能更新到之后的点改变。 但是我们需要保证 $out$ 的合法性，直接按照 $out$ 排序，之后二分得到即可。 本题比较难处理的就是 $\tt Dp$ 的边界，但是知道这个是拓扑图了之后肯定就没有问题了。 起始点，显然其 $in < \mi ...

P5298 [PKUWC2018]Minimax $2021.10.8$ 重新自己写出这题。 其实不要想太复杂就好了，别忘了看题面。 先给一个提示吧，为什么这题的 $Dp$ 不用融斥掉中间的部分，题目已经说出来了：没有重复权值的叶子。 首先考虑对于每一个节点的值最多只有 n 个，所以肯定需要离散化。之后考虑实际上每一个节点的值都是从其子树的叶子节点中转移过来的。 所以考虑树形 Dp 设 $f[i][j]$ 表示在树上点 $i$ 其值为 $j$ 的概率。 当然是离散化之后的值。 我们考虑转移，根据题意是取 $\min, \max$ 来转移的，所以我们考虑左右两个儿子的大小关系。具体来说就是如果让左边的儿子产生了贡献，右边的儿子的值就一定比左边儿子小 ( 如果是取 $\min$ 的话 )。 就可以写出方程 这里设左边的儿子为 l 右边的儿子为 r $$\begin{aligned}f[i][j] &= f[l][j] \times (p_i \times \sum_{k = 1} ^ {j - 1} f[r][k] + (1 - p_i) \times \sum_ ...

P3412 仓鼠找sugar II P3412 仓鼠找sugar II 根据期望的线性性质我们考虑对于每一条边进行计算贡献。 我们可以考虑先算方案数再除以总的点对。 根据期望的定义本质上就是平均数，那么对于一条边 $u \to v$ 的贡献次数就是 $(n - siz(u)) \times siz(u)$。 我们考虑一条边有两种情况： 向上 向下 我们钦定点 $u$ 表示 $fa(u) \to u$ 的边。 设 $up(u)$ 表示这条边从下走到上 $u \to fa(u)$。 设 $dn(u)$ 表示这条边从下走到上 $fa(u) \to u$。 $up(u)$ 一共有两种情况： $u \to v \to u \to fa(u)$ $u \to fa(u)$。 $$\begin{aligned}up( u) &= \frac{1}{deg(u)} + \sum_{v \in son(u)} \frac{up(v) + up(u) + 1}{deg(u)}\&= deg(u) + \sum_{v \in son(u)} up(v)\end{aligne ...

[HNOI2013]游走 [HNOI2013]游走 考虑每一条边的单独贡献，发现这个不是很好计算，而且边数其实很多。 我们考虑对于一条 $u \to v$ 的边，其贡献是 $\dfrac{f(u)}{deg(u)} + \dfrac{f(v)}{deg(v)}$。 其中 $f(i)$ 表示点 $i$ 期望被经过的次数，别忘了一开始点 $1$ 就被经过一次了。 考虑走到别的点之后再走回来更新这个点：$$f(u) = \sum_{v \in son(u)} \frac{f(v)}{deg(v)}$$如果 $u = 1$ 还要 $+ 1$。 发现数据范围很小，我们直接进行高斯消元即可。 之后对于边的期望经过次数进行贪心即可。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495#i ...

[HNOI2015]亚瑟王 [HNOI2015]亚瑟王 根据期望的线性性质，我们考虑每一张牌的贡献。也就是每一张牌被使用的概率。 显然第一张牌使用的概率就是 $1 - (1 - p_1) ^ r$。 但是发现之后的牌的使用依赖于前面的牌的使用，因为如果前面有 $j$ 张牌被使用了，相当于有 $j$ 轮对于当前牌是无效的。 我们考虑进行 $\tt dp$，设 $f(i, j)$ 表示前 $i$ 张使用了 $j$ 张牌的概率。$$f(i, j) =\begin{cases}f(i - 1, j) \times \left(1 - p_i\right)^{r - j} \f(i -1, j - 1) \times \left[1 - (1 - p_i)^{r - j + 1}\right]\end{cases}$$ $$F(i) =\begin{aligned}\sum_{k \le i} f(i - 1,k) \times \left[1 - (1 - p_i)^{r -j}\right]\end{aligned}$$ 12345678910111213141516171819202 ...