CF1835D&E&F

感觉这三题分开写很浪费，所以合并成了半场 CF 的总结（

CF1835D Doctor's Brown Hypothesis

首先你看到这个 \(k\geq n^3\) 就在疯狂暗示，也就是说你可以经过每个环，并且对于每个环都绕 \(n-1\) 圈，因此只需要满足增量被所有环长的 \(\gcd\) 整除并且在一个 SCC 里面，那么就是可以调整到的。

后一个条件对于每个 SCC 分开做就行，前面一个咋做？有一个比较高妙的染色，给每个点一个值 \(dfn_x\)，如果对于每一条边 \(x\to y\)，满足 \(dfn_x+1\equiv dfn_y\pmod g\)，那么 \(g\) 整除所有环的 \(\gcd\)。所以只需要先跑一个 dfs 树出来给每个点染色，然后再看非树边算出 \(\gcd\) 就行。

然后计算答案也是简单的，因为 \(x\to y\) 和 \(y\to x\) 的路径拼成了一个环，所以 \(g\mid 2k\)。所以要么 \(k\bmod g=0\)，要么 \(g\mid 2\and k\bmod g=\frac{g}{2}\)，开桶记录即可。

submission

CF1835E Old Mobile

我觉着这题没有 D 难啊！

首先当我们需要输入某个字符的时候，如果已经知道这个字符在哪里，那么最优的方案是直接输入，否则会随机猜直到猜到这个字符。因此最后的答案只和序列中的不同个数以及 \(n\) 有关。

delete 键是至关重要的，记 \(f_i\) 表示没有猜错过猜到了第 \(i\) 个，\(dp_{i,j}\) 表示猜到了第 \(i\) 个，已经知道了 \(j\) 个字符和 delete 键的概率。因为期望具有线性性，所以可以拆到每一步计算贡献。

对于 \(f_i\)，要么直接猜中；要么猜到 delete 回退一格，这一格需要一次去补回来，除了在第一位的时候，然后变成 \(dp\) 的内容；要么猜到了某个不是这一位的字符，那么就需要不断地猜直到猜到 delete 键，然后变成 \(dp\) 的内容相关。

对于 \(dp\)，要么在前面就已经把这个字符猜出来了，要么不断地猜，猜错就 delete，猜对就下一个，容易实现。

时间复杂度 \(O(m^2)\)。

submission

CF1835F Good Graph

可能理解了二分图匹配就不是很难？

首先这个形式让人想到了 Hall 定理，图是 Good 充要于有完美匹配。

首先考虑 No 怎么输出方案。考虑匹配失败的那个点，发现只需要把所有在这一轮里面增广到的点都拉出来就构成一个不合法的子集了。

然后考虑 Yes 的 tight 到底是个啥。考虑求出包含一个点的最小 tight 集合，记右部第 \(i\) 个点匹配的左部点是 \(mch_i\)，我们有这样的性质：

性质1：包含 \(x\) 的最小 tight 集合一定包含 \(\{mch_y|(x,y)\in E\}\) 。

考虑反证，如果不包含 \(mch_y\)，考虑这个 tight 集合的某个完美匹配，直接取原二分图匹配的完美匹配是一定可行的。但是由于不包含 \(mch_y\)，那么 \(y\) 没有点匹配，同时 \(y\) 又在 \(x\) 出点的集合内，所以集合不是 tight 集合，矛盾。

所以大概可以像 2-sat 连一条 \(x\to mch_y\) 的边，表示只要 \(x\) 在 tight 集合内 \(mch_y\) 就在，跑个传递闭包就可以得到包含 \(x\) 的最小 tight 集合。

对于 tight 集合做进一步观察，还有以下性质：

性质2：在一个 Good 的图中，定义极小 tight 集合为没有一个子集是 tight 集合的 tight 集合，那么一个非极小 tight 集合要么是包含某个点的最小 tight 集合，要么是两个无交 tight 集合并起来的。

反证，假设某个 tight 集合上面两个条件都不满足，选择 \(x\) 使得包含 \(x\) 的最小 tight 集合最大，然后将整个集合 \(U\) 分成包含 \(x\) 的最小 tight 集合和另外的数构成的集合，分别记作 \(X,Y\)。这两个集合之间显然有边，如果由 \(X\) 指向 \(Y\)，则与 \(X\) 是 tight 集合矛盾，如果由 \(Y\) 指向 \(X\)，则与 \(X\) 是最大的包含某个点的最小 tight 集合矛盾。

因此包含每个点的最小 tight 集合就可以表示所有 tight 集合，所以我们的目标相当于构造一个新图满足传递闭包不变，那么对于每个 SCC，先把 SCC 内部连成一个环，然后从这个 SCC 内一个点连向拓扑序最近的点就行。

复杂度瓶颈在于二分图匹配和传递闭包的 \(O(\frac{n^3}{\omega})\)。

submission