[IOI2018] werewolf 狼人 [IOI2018] werewolf 狼人 可以考虑到每一条边能否通过对于人形态来说，取决于两点的最小值，对于狼形态来说取决两点的最大值。 那么我们不妨考虑将两条边的边权定为上述两者，这样就有两张联通的无向图，我们考虑既然不考虑路程的限制我们一个肯定是需要考虑最大生成树另外一个就是最小生成树。 使用 $\tt Kruscal$ 重构树建立两棵树，一个是大根堆另一个是小根堆。 对于两个 $x, y$ 能否到达取决于是否存在一个点同时是两者的儿子。 我们考虑维护 $\tt dfs$ 序，通过可持久化线段树来判断。 但是题目中还有 $L, R$ 的限制，我们考虑到对于一条路径我们其实对于树上一个点还能向上走，我们考虑倍增跳到一个最高的合法的位置进行上述判断即可。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757 ...

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 ...

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 < ...

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) \t ...

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)\ ...

[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$。 发现数据范围很小，我们直接进行高斯消元即可。 之后对于边的期望经过次数进行贪心即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091 ...