差分约束浅谈 还是挺难的一个东西。 引入考虑一个限制 $A_i \le x_i + C_i$ 其中 $x_i$ 是一个给定的值。 $A, C$ 表示两个位置之间的关系。 发现对于同一个 $A_i$ 总共有若干个限制，那么也就是意味着 $A = \min_i(x_i + C_i)$。 发现这个东西就是最短路的更新。 我们换一种角度来思考，对于每一个 $C_i$ 其对应的限制就是 $C_i \ge A_i - x_i$ 也就是意味着 $C_i = \max(A_i - x_i)$ 这个就是最长路了。 所以说在题目没有给一些限制的时候我们可以将最长路和最短路相互转换。 实现常说这个东西是需要使用 $\tt SPFA$ 的，事实上 $\tt Floyd, Dijkstra$ 也是完全可以的，最主要的问题是 $\tt Bellman-Fold$ 这类算法是可以判断负环的，我们可以清楚得知是否有解。 当然如果说跑最长路也是可以的。 负环如果说一个点入队次数超过所有点的次数，那么肯定是存在环了。 不妨考虑其所在的路径的长度是 $ct_i$，有更新 $ct_u + ...

AT2062 [AGC005D] ~K Perm Counting AT2062 [AGC005D] ~K Perm Counting 一个有趣的做法。 发现合法的情况直接算是不好算的，我们考虑进行二项式反演，也就是钦定有多少个是不合法的。 考虑一个位置 $i$ 可以向 $i\pm k$ 连边。 我们不妨考虑左边是排列，右边是位置的二分图。 那么本质上钦定 $i$ 个不合法的就是对于这样的二分图满足其匹配是 $i - 1$。 对于匹配是 $i$，长度是 $j$ 的链，方案数就是 $\dbinom{i + j - 1}{i}$。 $\tt update\ on \ 2022.4.22$ 讲一下方案数是怎么算的，我们考虑钦定从上到下进行选择边，如果合法地选择了当前边那么下面的一条边就是不能选择的，我们可以考虑将这两条边绑一起选。 考虑最后一条边是没有绑的，我们枚举其是否选择，考虑 $a$ 条边，选择 $b$ 条。$$\binom{a - b}{b} + \binom{a - 1 - (b - 1)}{b - 1} = \binom{a - b + 1}{b}$$考虑总共链 ...

AT2000 [AGC002F] Leftmost Ball AT2000 [AGC002F] Leftmost Ball 感觉转移还是挺难的。$\color{white} Orz\ AK_STAR$ 我们不妨考虑随便染色，对于一种合法的染色肯定是对于任意前缀和白色的数量都大于等于颜色的数量。 那么我们不妨考虑通过白色来计数，我们不妨钦定每次填一种颜色的时候直接匹配最靠左没有匹配过的白色点。 设 $f(i, j)$ 表示填了 $i$ 个白色的球，填了 $j$ 种颜色。 我们转移考虑枚举当前位置填的是哪种颜色的球。 白色球，直接从 $f(i - 1, j)$ 进行转移。 颜色球，首先需要知道是哪个颜色的球 $n - j + 1$ 还要知道有哪些位置是可以填的 $n \times K - i - 1 - (j - 1) \times (K - 1)$，之后我们发现已经钦定了一个白球作为颜色的开始，而且当前位置又必须填一个球，所以剩下 $K - 2$ 个球来填。 那么转移系数就是 $(n - j + 1) \times \dbinom{n\times K - i - 1 - ...

Kruscal 重构树浅谈 这个算法本质上就是通过 $\tt Kruscal$ 重构树的过程将边权变成点权之后建立一个堆。 具体来说就是每次选择一条合法的边，将边权变成点权之后连接原来边两边的节点。 这个是生成树上的性质，有些大佬说可以类比成笛卡尔树，不过那个是序列上的满足堆和 $\tt Bst$ 的性质的树。 可能性质还笛卡尔树更多一点。 常用解法 跳父亲找到符合条件的最小点。 维护 $\tt dfs$ 序判断点是否在内。 结合动态规划和数据结构维护书上信息等。 常用的一个写法 这种写法是特别针对将一条边的边权定做和相邻点的 $\tt min, max$ 相关的快速写法。 举个例子：维护 $\tt min$ 的最大生成树。 考虑加边的时候肯定是从权值最大的边开始加，我们考虑从大到小枚举点，钦定当前点代表当前权值的边。也就是另外一个点是比其大的。然后能加边就加边。 123456789for(i = 1; i <= n; ++ i) fa[i] = i;for(i = n; i >= 1; -- i) { for(int j = head[i] ...

[NOI2018] 归程 [NOI2018] 归程 讲一下科技 $\tt Kruscal$ 重构树的做法。 考虑到积水的问题，我们肯定是贪心选择积水深度最大的边进行建立重构树。那么这个就是一个小根堆。 之后考虑我们如何回答询问，对于一个询问的水深度，跳父亲。同时维护一下每个点的子树距离 $1$ 节点距离最小的点即可。 对于 $\tt Kruscal$ 重构树，每次根据 $\tt Kruscal$ 的过程选出边，但是将边权变成点权之后链接原来边的两个点即可。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241 ...

[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，其实本质 ...