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$ 边保证距离最小就行了，考虑需要保证是树的情况，所以一个点出去了之后就不会再回来，直接使 ...

Problem - 1615F - Codeforces 首先怀疑一手这个东西是 $\tt Dp$。 就只会怀疑了 $\cdots$ 有一个很强的转化，考虑先对于每个串的偶数位置取反，之后原来的操作本质上就是交换两个数。 考虑对于位置 $a_i, a_{i + 1}$ 经过操作后是 $!a_i, !a_{i + 1}$。 经过变换后是 $a_i, !a_{i + 1}$ 和 $!a_{i}, a_{i + 1}$。发现对于 $a_i \ne a_{i + 1}$ 经过交换是不变的，所以这个变换满足充要条件。 考虑合法的条件就是两个序列 $1$ 的个数相同，考虑如何计算最小的操作次数。 题目说只能 $s$ 动所以比较简单考虑通过交换去填充 $1$ 的位置，显然每个 $1$ 填充的最优位置是确定的。 不妨考虑 $S$ 中第 $i$ 个 $1$ 位置在 $x_i$，$T$ 中为 $y_i$，答案就是 $\sum_{i \ge 1} |x_i - y_i|$。 还要继续转化，考虑 $S$ 中 $1 \sim i$ 的 $1$ 的个数为 $a_i$，$T$ 中为 $b_i$。 答案同样可以 ...

Problem - 1499G - Codeforces 完蛋一点不会。 考虑没有询问的时候是考虑对于度数为奇数的点连接一个虚点，之后跑欧拉回路钦定入边为红色，出边为蓝色即可。 之后考虑虚拟点不是很好搞，所以考虑删除虚拟点那么原图就是一堆环和路径，考虑加入一条边的情况： 边的端点不是路径端点，直接作为新的路径。 边的一段是路径端点，合并路径。 边的两端都是路径，要么合并两条之前不同的路径，要么之前的一个路径变成了环。 我们考虑欧拉回路本质上就是对边进行黑白染色，我们考虑染色的问题只在最后一种情况上出现，事实上我们只要翻转奇偶性就行了。 所以考虑使用并查集来维护即可，注意要维护红边的哈希值的和，但是有翻转操作所以两边都要维护。 可能最近生病了（借口），一开始写的时候一点都不清晰，在看题解。 但事实上我们只需要考虑每个点正好断掉的路径，然后记录整条路径当前是否被翻转过，显然如果中间连接一条边必定满足该边和左右两条路径颜色都不同，且左右两条颜色相同。 1234567891011121314151617181920212223242526272829303132333435363 ...

Problem - 1142E - Codeforces 一点自己的想法首先考虑 $m = 0$ 的情况，同时发现题目没有限定条件，说明解是一定存在的，考虑尝试证明这个东西。 显然解一定存在，考虑点 $u$ 直接连接了若干个点，对于 $v \to u$ 那么 $v$ 本质上可以看成一个星图。那么如果存在 $v \to u, y \to u$ 显然 $(v, y)$ 这条边无论方向是怎么样的都是可以归结于上面情况，所以当 $m = 0$ 的时候解一定存在。 尝试按照上述的方法进行构造，考虑先将 $1$ 作为根节点，之后考虑询问其他节点与 $1$ 连接的情况，如果存在边 $(1, u)$ 那么点 $u$ 本质没有贡献，如果存在边 $(u, 1)$ 考虑分类讨论： 如果 $1$ 已经有了一个继承节点 $v$ 询问 $(u, v)$ 之后进行合并。 如果没有，直接将 $1$ 合并到 $v$ 上。 这样对于每个节点每次最多询问 $1$ 次，总共应该是 $n - 1$ 次。 考虑 $m \ne 0$ 的情况，需要考虑当前节点是否是通过 $\tt \color{pink} ...

Problem - 1477D - Codeforces 题目描述： 给定一张 $n$ 个点 $m$ 条边的简单无向图，构造两个排列 $p,q$，使得： 对任意 $(u,v) \in E，(p_u​−p_v​)(q_u​−q_v​)>0$。 在此基础上，最大化 $p_i \ne q_i$ 的个数。 $1\le n,m \le 5×10^5$。 考虑上述限制的本质，如果说已经确定了排列 $p$，那么对于 $p_u, p_v$，$(u, v)$ 在 $q$ 中的相对位置也是确定的。所以本质上就是给边定向，在这之后求出拓扑排序的两个排列使得对应位置不同的元素个数最大。 观察样例发现大部分情况下都是可以构造全部错位的情况，显然如果一个点同时被所有点限制才能确定位置，也就是度数为 $n - 1$。所以这样的点其实本质上不需要考虑，考虑删除点之后对于每个连通块进行计算。 考虑之后的图是怎么样的，就是所有点的度数至多为 $n - 2$，但是感觉一下子没有什么用。 考虑直接对于连通块进行 $\tt bfs$ 分层，同一层错位排序发现如果存在一层只有 $1$ 个点就去世了，所以我们考虑一下星 ...

Problem - 1474F - Codeforces 经典题。 首先最长严格上升子序列可以直接求得。 之后将其分成若干上升和下降的段，显然这样的段的值域肯定是连续的，或者说我们的最长严格上升子序列值域是连续的。 考虑对于这个东西进行 $\tt Dp$，发现我们只需要知道答案的最小值和最大值就可以确定一个数列。如果有多种这样的答案，对于任意两个答案序列肯定是不交的。 如果相交就可以获得更长的答案。 所以对于这个东西可以分开计算，具体来说就是枚举最小值，之后考虑将序列分成上升和下降的段。 发现按照段进行转移是不方便的， 所以考虑按照值域进行转移。 我们考虑枚举之后设 $f(i, j)$ 表示当前值为 $i$，处于第 $j$ 段的方案数。 这个东西可以矩阵加速，复杂度是 $O(n \times n^3 \log V)$。 发现一个问题，如果直接只考虑左右端点的话会发现部分转移没法转移到。 所以需要拆点拆成一个可以使其转移到的位置，也就是拆成 $3$ 份。 我们具体来说说： 12345678910for(i = 1; i <= totd; ++ i) { if ...