Problem - 1060F - Codeforces 考虑每个数如果被选择为最终的答案，要么是操作没有选择与其相连的边，要么是操作了这个边用 $\frac{1}{2}$ 的概率活下来了。 首先总边数是每次减少 $1$ 的，一个点被选择的概率只和该点周围连接了几条边有关。 设 $f(u, j)$ 表示在 $u$ 的子树中，对于所有删边顺序只对最后 $j$ 条边选择存活节点，根节点的编号仍然是 $u$ 的概率，节点 $u$ 的答案是 $\frac{f(u, n-1)}{(n-1)!}$。 考虑合并 $(u, v)$，我们只需要考虑 $u$ 还有 $v$ 的子树，我们同样设边的状态为 $g(i)$ 和上文相同。 枚举 $(u, v)$ 在什么时候被删除。 如果 $j \le i$ 意味着边收缩完成之后，新的编号已经确定，所以必须选择 $u$ 概率为 $\frac{1}{2}$，同时因为 $(u, v)$ 已经合并，所以最后的 $j -1$ 条边都需要选择 $u$，也就是选择 $v$。转移为： $g_i \leftarrow f(v, j - 1) \times \frac{1}{2}$。 ...

Problem - 1310E - Codeforces 考虑倒推，每个数具体是啥是不知道的，但是我们可以知道数的种类。 本质上对于集合中的每一个元素，就代表一种不同的元素。 如果进行一次逆变换，元素种类就会变成原来集合 $\sum a_i$。 一开始是有限定的，集合大小小于等于 $n$。 先处理 $k = 1$ 的情况：划分数 $\tt Dp$。 $k = 2$ 的情况，就是考虑需要倒推两次，不妨考虑当前集合是 $c$，考虑 $b$ 中出现次数为 $c_i$ 的数是 $v_i$，可以得到 $\sum c_i v_i \le n$。 我们只需要考虑其存在性即可，我们不妨让 $c_i$ 递减，之后 $v_i = i$。这样可以取到最小值。 所以我们只需要满足 $\sum c_ii \le n$ 即可，考虑进行 $\tt Dp$ 因为钦定了 $c_i$ 的关系，我们需要二维的状态复杂度 $O(n ^ 3)$，但是事实上我们钦定 $c_i$ 所以只需要枚举差分值就行了。考虑再推式子。 我们让 $t_i = c_i - c_{i + 1}$。 $$\be ...

Problem - 1620F - Codeforces 二分图本质上就是没有奇环，注意给定的是一个排列。 考虑什么时候会出现奇环，考虑如果 $(i, j), (j, k)$ 那么必然存在 $(i, k)$ 这样就去世了。 也就是如果存在 $(i, j)$ 那么 $\forall k \in [j + 1, n], a_k \ge a_j$。 我菜了。 既然结论已经想到这个份上了，直接考虑 $\tt Dp$。 我们注意结论：序列中不存在 $i < j < k, p_i > p_j > p_k$。 考虑进行填数设 $f(i, x, y)$ 表示填了 $i$ 个数，最大值为 $x$，已经填好的逆序对末尾的最大值为 $y$，能否没有奇环。 考虑优化状态，对于两个序列 $p_1, p_2$ 在相同的 $x$ 下选取较小的 $y$ 更加有潜力。 显然对于 $(i, y)$ 是固定的，$x$ 越小序列越容易合法。 考虑将状态变成 $f(i, x)$ 表示能取到的最小的 $y$。 如果不合法就是 $+\infty$。 转移方程，设 $z = \pm p_{ ...

Problem - 1603E - Codeforces 虽然是再论但是是一点题解的印象都无了。 首先从小到大开始考虑，对于这样的一个序列事实上我们可以任意排列，答案就是： $$\frac{n!}{\prod_{i} c_i!}$$ 其中 $c_i$ 表示一个数重复出现的次数。 发现做不下去了，考虑找找性质。 不妨考虑区间 $[l, r]$ 那么需要满足 $a_l \times a_r \ge sum_r - sum_{l - 1}$。 考虑对于同一个 $r$，$l$ 越小限制越强。 对于该序列只要前缀是合法的答案一定是合法的。 直接考虑 $\tt Dp$ 需要枚举第一个数，然后记录前缀和。 复杂度是 $O(n\times n^3\times n)$ 是过不去的。 考虑是否还有性质，不是很好找，那么考虑压缩状态，如果考虑前缀和第一个数不论转移的复杂度就已经是 $O(n^4)$ 了。 所以考虑能不能少枚举一些东西，前缀和是不能省掉的，考虑能否倒叙枚举，发现如果 $a_n \le n - 1$ 就去世了。所以 $a_n = n, n + 1$。 可以省略掉一维了，但是算上 ...

Problem - 1299D - Codeforces 切了，但是没有完全切。 有的时候还要打表一下证明一下结论。 md 不用打表，直接算就行了，之前直接感觉就是 $2^x$，比较大。 好吧，之前写过，严谨地说是抄过。现在能想到了还是挺好的。 打表得到线性基本质不同的个数为 $374$ 个。 考虑合并连通块就是线性基之间的转移，直接设 $f(i)$ 表示当前是第 $i$ 个线性基的方案数。 转移的时候保证线性无关就行了。 之后考虑三元环的情况： 因为没有重边所以没有二元环。 都是有 $2$ 条边连接节点 $1$，考虑分类讨论一下： 不选择，方案数为 $1$。 选择 $1$ 条边，随便选择即可方案数为 $2$。 选择两条边，加上当前线性基，方案数为 $1$。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283 ...

Problem - 1225G - Codeforces 一点想法首先我们看这个神奇的函数 $f$。 如果说 $x = k^a\times b$ 的话，那么 $f(x) = b$。 我们考虑对于 $x = k^{a_1}b_1, y = k^{a_2}b_2, a_1 < a_2$。 我们可以得到 $(x + y) = k^{a_1}(k^{a_2-a_1}b_2 + b_1)$，显然右边部分肯定不是 $k$ 的倍数，是可以直接算出来的。 考虑题目中的限制是最终的答案为 $1$，那么意味着最后一次合并有 $k | x +y$ 。 注意到 $n = 16, k = 2000, \sum a_i \le 2000$，是不是可以进行状压。 复杂度貌似是 $O(2^n\sum a_i)$。考虑设 $f(S, i)$ 表示集合 $S$ 中的数能否拼出 $i$。 转移的时候枚举一下加入哪个数，复杂度是 $O(2^nn\sum a_i)$。是不是可以 $\tt bitset$。 考虑枚举转移位置和 $S$，我们貌似可以预处理 ...

Problem - 1062F - Codeforces 可能是题单里面最水的一题了吧。 直接想到拓扑排序，考虑在队列中的所有点都是互相不可到达。考虑使用正反两次拓扑排序来计算答案。 q.size() == 1 $x$ 可以到达剩下的所有点。 q.size() == 2 考虑队列中的 $x, y$ 两点显然 $x$ 是不能到达 $y$ 的，如果出现 $y$ 的一个出边 $y \to z$ 且 $z$ 的入度为 $1$，那么 $x$ 就没救了，直接打标记。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495#include <bits/stdc++.h>using namespace std;namespace Legendgod { namesp ...

Problem - 1149D - Codeforces 一点小思路： 貌似有点问题。 首先保证图连通，发现点数为 $70$ 边数最多为 $200$。对于两种边权 $a, b$ 有一种想法就是让最短路包含在最小生成树中。或者说我们优先考虑边权小的边，先让其尽量成为生成树，能否直接暴力枚举端点 $i$，考虑暴力构建树。 是否有一个结论，就是我们考虑只使用 $a$ 边这样最短路肯定是可以在生成树上的。 如果仅仅使用 $a$ 边发现图是不连通的，我们考虑当前点 $i$ 所在的连通块。 现在本质上就是尝试暴力加入若干边，能否考虑使用 $b$ 边继续更新结果？ 显然 $b$ 边只要能使图连通就是最小生成树了，考虑使用 $b$ 边使得 $1 \to i$ 的距离最短。 不妨考虑对于 $i$ 也进行一次最短路，是不是直接弗洛伊德更新呀？ 就是每个点对之间打标记是否是通过了 $b$ 边进行更新即可。 $\tt solution$考虑还是对于最小生成树，先考虑 $a$ 边构成的若干个连通块，之后只要使用 $b$ 边保证距离最小就行了，考虑需要保证是树的情况，所以一个点出去了之后就不会再回来，直接使 ...