Luogu P5676 [GZOI2017] 小z玩游戏

P5676 [GZOI2017] 小z玩游戏

难度：提高+/省选-
标签：Tarjan 建图
\(\mathtt{blog}\)

有 \(n\) 组数 \((w_i,e_i)\)，如果当前数值为 \(w_i\) 即可改变为 \(e_i\)，如果当前数值为 \(x\) 也可以变为 \(kx(k\ge 2)\)，问有多少组数在一个循环中。

这题不一眼 Tarjan。

想到对于这些关系建成一个图跑一个 Tarjan 求强连通分量，在一个强连通分量内就说明满足条件。

第一种建图方式：
暴力枚举游戏，判断是否可行进行建边。
时间复杂度 \(O(n^2)\)。得分 \(40\sim70\)。

第二种建图方式：
把点所代表的从游戏变为单个数，边所表达的从这个游戏能不能换到另一个游戏变为这个数能不能变成另一个数，便按照题意建 \(2\) 种边：
\(i\to k\times i(k\ge 2)\)，和 \(w_i\to e_i\)。
时间复杂度为 \(O(w\log w+n)\)，\(w\) 为值域。可以通过。

\(\mathtt{Code}\)