P7418 [USACO21FEB] Counting Graphs P题目大意： 给定一张图，对于另一张合法的图，当且仅当两张图 $(u, v)$ 之间所有的路径长度相同。统计所有合法的图的数量。注意路径不一定是简单路径。 看到路径不一定是简单路径基本上就可以猜到做法了。因为是复杂路径一条边重复走是增加 $2$ 的贡献，所以只要任意两点之间最短奇偶路径相同即可。我们可以找出这样的路径。我们任意找一个起点，之后可以得到 $n$ 个数对。我们为了方便钦定 $(x, y), x < y$。 我们考虑一条边可以产生贡献而且是合法的是什么情况。对于一个 $(x, y)$ 来说之前的点对 $ + 1$ 必须保证 $x_1 +1 - x\equiv 0\pmod 2, y$ 同理。然后我们不一定每一个点都要考虑，直接继承就好了。 所以总共有 $3$ 种点。 (x - 1, y - 1)是 $A$ 类边，点个数为 $a$。 (x - 1, y + 1)是 $B$ 类边，点个数为 $b$。 (x + 1, y - 1)是 $C$ 类边，点个数为 $c$。 (x, y)是当前的点对，点个数为 $ ...

CF1534F2发现这是一个 $4$ 联通问题。我们先考虑建图。 我们需要每一个序列都满足条件，那么我们可以选取最低的点然后考虑其被左右两边影响的区间，也就是左右两边任意掉落一个沙子即可将其掉落。 这个可以使用 $dfs$ 解决。然后我们就得到 $n$ 个满足条件的区间。 我们将题目变成了给定 $n$ 个区间，选择最少的点使得每一个区间至少有一个点。我们按照左端点为第一关键字，右端点为第二关键字排序。尽量选右边的点即可。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119#include <bits/stdc++.h>using na ...

CF1305G 可以算说我自己做出来的 $3500$ 题吧。虽然这是很多年前的题。 这个东西我们可以尝试一下建图，也就是如果两个点是朋友关系我们可以使其连边。 然后会发现有很多的联通块，那么我们不妨对于一个联通块来考虑。 我们贪心得想肯定要让小的邀请大的点。然后邀请的情况肯定构成一个树，也就是邀请的边数是点数 $-1$。 因为不能重复邀请。 我们考虑这个树的情况需要使用，会想到最大生成树。然后要如何设置边权？可以发现对于一条边本质上两边都可以使用那么边权就是 $a_u + a_v$。但是每一个点肯定需要一次被加入，那么就需要减去所有点的点权。 但是我们第一个选择的点不知道是谁，总不可能暴力枚举吧，发现可以建立一个 $0$ 节点，链接所有的节点，这样第一个点的贡献也可以计算了。 现在可以保证整张图是联通的，我们计算最小生成树即可。 最小生成树总共有 $3$ 种求法。$prim$ 和 $kruscal$ 都需要预先知道全部的边。那么我们可以使用 $Boruvka$。在计算的过程中我们只需要进行高维前缀和即可。 因为最大的边权可能被计算过了，那么我们维护一个和最大边权所属联通块不同的次 ...

CF980F每一个点都指属于一个环，考虑对于每一个环进行计算答案。 考虑基环树的情况，我们会计算出其余的点，之后对于环上的点单独进行 $Dp$。 这边也是同理，找到每一个点属于的环，钦定一下每一个环的根。 因为计算距离需要使用换根 $Dp$。 我们考虑需要预处理写什么，也就是对于不同环之间的转移，然后对于同一个环内我们需要记录环根的答案。 对于不同环之间的转移，对于每一个点设 $f0_i$ 表示向下，从所属环不同的点到当前环的最小距离。 然后对于环根还要特别记录一下 $f1_i$ 表示考虑环上的情况。 因为环根才可以将之前的节点都考虑到。 之后设 $f_i = \max(f0_i, f1_i)$ 也就是向下走的答案。 之后考虑向上走，设 $g_i$ 表示向上走的答案。 我们这个时候可以将 $f0_i = \max(f0_i, g_i)$ 方便处理。 可以从所属环不同的点进行转移，记录最大最次大值。 之后考虑整个环对于当前点进行转移，也就是 $\min(l, r)$ 左右两边，我们分别对其进行单调队列即可。 可能因为我代码实现问题，我的数组需要多开大几倍。 123456789101 ...

CF865E 首先考虑差的性质，也就是 $S = \sum_{i} a_i - b_i$ 我们会发现如果没有进位这个值就是 $0$，不然如果有进位那么每一位会多出来 $15$ 的贡献，可以发现合法的情况是 $S \equiv 0 \pmod {15}$。 不然就是不合法的。 然后我们需要钦定有多少位是进位的，复杂度是 $\binom{13}{6}$ 可以接受的样子。 又因为 $b$ 是 $a$ 的置换，本质上我们可以看成 $a_i - a_{p_i}$。我们不妨将这种情况连边 $i \to p_i$。可以连接成若干个环。对于每一个点的权值 $w_i = a_i - a_{p_i}$。但是对于每一个环我们统一进行处理会更加方便，也就是将整个环 $-1$ 直到出现 $0$。将两个 $0$ 点进行连边即可。 我们进行计算的时候因为对于图上来说，我们如果钦定了一个开始点，剩余的点本身就是一个差分，我们要还原之前的值就是前缀和。 我们再考虑一下 $S$ 的性质，发现 $15 = 16 - 1$ 也就是说明 $16 \times \frac{S}{15} - \frac{S}{15} = S$ ...

CF1383C观察一下题目的性质，他说了同一种颜色可以有若干个一起变色，那么我们考虑将同一种颜色看成相同的东西。 考虑对于其建图，也就是如果 $A_i$ 变成 $B_i$ 就建立 $A_i \to B_i$ 的边。 然后本质上就是叫我们重新建立一张图满足 $A_i$ 和 $B_i$ 联通，边数最少的图。 本质上每一次变换都是需要一次操作。 但是不仅是如此，如果说 $u \to v$ 的路径是存在的，必须满足其路径上的边的变化时间是递增的。那么就是让我们对于边进行标号，然后满足图上任意路径都是递增的。 我们发现如果任意两个点都能互相到达，边数最少的就是一个环加上一条链。也就是这样的情况。这样我们需要消耗 $2n - 2$ 条边。 但是我们可以更优，也就是考虑对于这个图，找到一个最大的 $DAG$ 进行向链一样连边，然后后面的点进行这样的操作。 这样子肯定是最优的。然后我们考虑通过 $Dp$ 计算这个答案，发现直接计算选了 $S$ 中的点，最大 $DAG$ 的大小不好算。那么我们就找下面链的最少点个数。 我们对于每一个弱连通块分别考虑，设 $f(S)$ 表示考虑了集合 $S$ 中的 ...

CF848D对于一条 $S \to T$ 的路径我们一开始会考虑对于点的标号进行计算，但是事实上我们并不知道哪些点会在左边或者右边。 然后对于最小割我们转化成最大流进行计算，对于某一个中间点使得最大流是 $m$，你们左右两边的最大流的 $\min$ 就是 $m$。 我们发现本质上就是求经过 $n$ 次操作，使得最大流是 $m$ 的图的个数。 然后对于左右两边其实分成了一个子问题。 那么设 $f(n, m)$ 表示经过 $n$ 次操作，最大流是 $m$ 的图的个数。 然后进行转移的时候，设 $g1(n, m)$ 表示最大流大于等于 $m$ 的图的个数，$g(n, m)$ 是最大流恰好为 $m$ 的图的个数。 对于 $f$ 进行后缀和为 $F$。 那么 $g(n, m) = \sum_{i = 1} ^ {n - 1} F(i, m) \times F(n - i -1, m)$ 之后因为每一条路径本质只会贡献一次，所以 $g(n, m) = g1(n, m) - g1(n, m + 1)$ 。 这个和二项式反演不同，那个是同一条路径贡献多次。 然后我们考虑计算 $f$。 然后因为每一 ...

CF830E题目已经很简洁了，我们考虑对于样例进行分析。 首先不用脑子就能想到的就是环的情况，有环直接全部填 $1$ 就好了。 我指的是环所在的连通块。 之后研究样例发现对于树的情况也是有解的，然后我们会想到菊花的情况，对于菊花，也就是 $\exist i, deg_i \ge 4$ 就是有解的，中间填 $2$，周围填 $1$。 我们发现 $\forall i, deg_i \le 2$ 是无解的。 然后我们发现只有一个 $deg_i = 3$ 的情况不好算，我们先看两个的情况。也就是有两个度数为 $3$ 的点连在一起了，我们直接对于两个点赋值 $2$，其他为 $1$ 即可。 一开始我是想着两条链之间的点赋值 $2$，后面发现 $1$ 也是可以的，这样就很简洁了。 然后我们开始讨论只有一个 $deg_i = 3$ 的情况。本质上就是一个点，三条链的情况发现我们可以对于每一条链进行单独考虑。我们不妨设这样一条链从头到尾是 $a_1 \sim a_n$ 其中 $a_1$ 是图中的 $1$ 号节点。之后我们考虑使这个贡献最大，也就是使这个函数最大。$$- \sum_{i = 1 ...