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 ...

Problem - 1152F2 - Codeforces 发现 $k, m$ 很小这个东西肯定有问题。 要么是直接通向要么可以使用矩阵快速幂。 感觉任意两个元素都是不同比较难处理，所以我们考虑进行 $\tt Dp$。 设 $f(i ,j, S)$ 表示当前值是 $i$，是序列长度为 $j$。 因为直接按照序列进行放置值域是不好确定的，我们考虑进行插入操作。 对于值域为 $i$ 我们需要权值 $\ge i - m$ 的位置在其前面，所以 $S$ 表示权值 $\ge i - m$ 的权值有哪些在序列中。 当然我们可以放在序列的开头，因为我们考虑值域是从小到大的，所以可以直接进行操作。 $$\begin{aligned}f(i, j, S) \times (popcount(S) + 1) &\tof(i + 1, j + 1, (2S + 1)) \\f(i, j, S) &\to f(i + 1, j + 1, (2S))\end{aligned}$$ 直接矩阵快速幂即可。 1234567891011121314151617181920212223242526272 ...

Problem - 843D - Codeforces 竟然直接被我想对了。 首先这个 $O(nq)$ 貌似是可以过的，可以发现是求最短路问题。所以做法应该比较直观就是考虑每次暴力 $O(n)$ 进行更新。 如何进行更新呢？ 考虑原来的最短路，不妨设为 $d(i)$，现在有新增加的路径 $add(i)$。可以发现我们可以直接通过宽搜看一下 $add(i)$ 能否进行更新。 但是我们这样还是需要优先队列，我们考虑如何模拟这个过程，可以发现每次是 $+1$，所以距离最多是增加 $n$。我们直接开桶暴力存即可，如果发现 $add(i)$ 与当前信息不符合可以直接剪枝，复杂度是 $O(n)$ 的。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021 ...

Problem - 687E - Codeforces 图是不变的，如果出现环我们肯定是必须要一直遍历，所以我们肯定是考虑通过改变遍历顺序得到最小的环。 考虑缩点之后的强联通分量，如果一个强联通分量没有出边肯定是要自己内部构造环。 如果不然我们肯定是可以构造出一个到另外强联通分量的最短路径。 考虑一个环的贡献就是 $\text{点数} \times 999 + 1$。 对于全局来说就是 $\text{点数} \times 998 + n + \text{环数}$。 直接 $\tt tarjan$ 暴力做即可。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161 ...

Problem - 889E - Codeforces 愚人节快乐。 首先考虑每个 $x$ 最终得到的序列肯定是单调不递增的。 那么对于最终的答案我们可以表示成 $x_n \times i + b$ 的形式。 我们考虑对于这个东西能不能进行 $\tt Dp$，设 $f(i, j)$ 表示考虑了前 $i$ 个数，最终的 $x$ 是 $j$ 得到的最大的 $b$。 我们会发现有很多无用状态，如果存在 $f(i, j - 1) \le f(i, j)$ 那么前面的部分肯定是没用了。 所以我们只需要考虑 $f(i, k)$ 随着 $k$ 增大值是递减的情况，我们转移的时候同时转移 $[0, k]$ 可以发现所有的情况都被转移过了。 对于 $a_{i + 1} > k$ 的情况，我们可以直接转移到 $f(i + 1, k)$。 不然的话我们肯定是考虑最后一段 $0, 1, 2, \cdots k \mod a_{i + 1}$ 的这一段进行转移，这样可以叠加尽量多的 $b$。 可以发现我们的状态 $k$ 每次是 $\div 2$ 或者不变的，所以状态数是 $\log$ 级别的。 不妨 ...