526互联

AGC010E Rearranging

发布时间 2023-07-21 08:35:03作者: Ender_32k

考虑先手操作完后得到的序列为 \(b_i\)，后手如何操作得到最大答案。

由于不互质的数不能交换，所以任意一对 \(i<j,\text{gcd}(b_i,b_i)\neq 1\)，后手操作后相对顺序不变。

所以可以枚举每对不互质的数，编号小的往大的连边，然后用优先队列跑最大拓扑序。

再考虑先手如何操作。

容易发现相当于是一个无向图上确定每条边的方向，使其成为一个 \(\text{DAG}\)，并且最大拓扑序最小。

贪心先从小的数开始连边即可。

复杂度 \(O(n^2\log n)\)。