1835D
CF1835D Doctor's Brown Hypothesis 题解
题目链接 点击打开链接 题目解法 首先只有在一个强联通分量里的点对才可能合法,因此我们这里说的图默认为强联通图 但是上面的条件成立只需要满足 \(k\ge n\),考虑用好 \(k\) 可以认为是极大的性质 所以说我们可以通过图中所有的环 \(+\) 路径来凑出 \(k\) 不难发现,所有的环能构成 ......
CF1835D Doctor's Brown Hypothesis
D - Doctor's Brown Hypothesis 首先,一对合法的\((x,y)\)一定是在同一个\(scc\)中的,所以我们将每个\(scc\)分开处理 若我们当前在处理某一个\(scc\),考虑给这个\(scc\)建一棵\(dfn\)树,设当前\(scc\)中的所有的环长度的\(gcd ......
CF1835D
[原题](https://codeforces.com/contest/1835/problem/D) [翻译](https://www.luogu.com.cn/problem/CF1835D) 好题!图论用数论的解法真的很巧妙 首先注意读题,要**恰好等于$k$**,~~因为我看错了~~ 这题有 ......
CF1835D Doctor's Brown Hypothesis
由于 $k$ 够大,你可以随便在图上走环,不用担心不用走,那么你所担心的只有环长的 $\rm gcd$。 将所有强连通分量先求出,满足条件的点对必然在一个强连通分量里。我们以随便一个点为根,跑出强连通分量中的一棵dfs树,我们断言,如果 $dep_x-dep_y \equiv dep_y-dep_x ......