浅谈欧拉路径，欧拉回路 引入前有哈密顿路径，表示经过每个点恰好一次，现有欧拉路径，表示经过每条边恰好一次。 许多题目重要的是建模，往往最浅的建模就是点之间的连边，表示可以到达。如果说需要满足到达每个点一次，这就变成了 $\tt NPC$ 问题。但是我们往往可以将一个信息拆分成若干个信息，变成边之间的关系，这样就有多项式复杂度的解法，同样这个是可以求方案的。 本篇会向读者介绍欧拉路径和欧拉回路以及其判定方法，还有常用的套路。 欧拉图具有欧拉回路的图叫欧拉图，如果只有欧拉路径就叫做半欧拉图。 欧拉路径定义：经过每条边恰好一次，起点和终点不一定相同。 无向图每个点的度数都是偶数，或者只有两个节点度数是奇数。 有向图设一个点的权值 $v_i$ 表示其出度减去入度。 那么存在的欧拉路径的条件是 $v_i = 0$ 或者同时存在一个 $v_i = 1, v_j = -1, i \ne j$。 欧拉回路定义经过每条边恰好一次，起点和终点相同。 无向图每个点的度数都是偶数。 有向图设一个点的权值 $v_i$ 表示其出度减去入度。 那么存在的欧拉路径的条件是 $ ...

浅谈 Wqs 二分 主要是今天写 「九省联考 2018」林克卡特树 的时候遇到了，就学一下。 使用条件 题目中对于一种 $\tt Dp$ 有限制，但是如果没有限制，其复杂度是正确而且很好求的。举个例子来说： 将一棵树划分成 $k$ 条链，我们 $\tt Dp$ 的时候只需要记录当前节点是否被匹配过，以及是否正在被匹配即可，而且我们还要考虑总共有几条链，进行划分。但是如果不考虑链的数量，这个 $\tt Dp$ 显然是 $O(n)$ 的。 对于背包类型的 $\tt Dp$ 来说如果有物品数量的限制，之前常常会有 $O(n^2)$ 不得不枚举的复杂度，我们将其消去常常就可以得到正确的复杂度。 对于限制的依赖，可以考虑限制是 $x$，贡献是 $f(x)$，对于点对 $(x, f(x))$ 其构成一个凸包。 具体实现对于一个凸包考虑枚举斜率进行切割，对于一个上凸包来说斜率是从左到右逐渐递减的。 我们考虑枚举一个斜率 $k$，那么我们的截距是什么呢，显然就是 $f(x) - kx$。 显然对于所有的 $g(x) = f(x) - kx, (x, g(x))$ 同 ...

Tarjan 缩点，强联通分量 @[toc] 引入如果说需要对于一个图上进行 $\tt Dp$，但是同一个环上的点无法进行转移怎么办？ 我们只能做 $\tt DAG$ 上的 $\tt Dp$，但是有环我们该怎么办？ 缩环！缩点！求强联通！ 当然我不是说隔壁的带花树。 虽然说所有的代码都是我随手打的，但是都已经经过测试，请放心阅读。 代码基础定义 dfn[x]表示当前点遍历顺序的编号。 low[x]表示当前点通过其 $\tt dfs$ 的子树以及能通过一条边到达的点，最浅能到达的编号。 强联通分量定义：  有向图中能任意到达的极大点集，被称为一个强联通分量。   对于一张图，我们将其划分成若干个这样的极大点集，每个点集之间的连边关系构成一张 $\color{red}\tt DAG$。 代码实现：  我们遍历每一个弱联通分量，考虑使用一个栈来维护每个点的进入顺序。   每次通过其能到达的点来更新 low[p]。 如果说当前的儿子没有被遍历过，先遍历然后通过 low更新。 如果说当前的儿子在栈中， ...

差分约束浅谈 还是挺难的一个东西。 引入考虑一个限制 $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 ...