洛谷5288 [HNOI2019]多边形
Luogu LOJ 分析 首先有一个结论：最终状态一定满足所有边都连向 $n$ 。那么步数就等于初始状态下不与 $n$ 相连的边数。 把所有初始与 $n$ 相连的边按另一个端点排序。那么对于排序后相邻的两个点 $l,r(l+1\neq r)$ ，一定会存在一条边 $(l,r)$ 。那么图中一定会存在一个点 $mid$ ，使得初始状态下存在两条边 $(l,mid)$ 和 $(mid,r)$ 。...
Luogu LOJ 分析 首先有一个结论：最终状态一定满足所有边都连向 $n$ 。那么步数就等于初始状态下不与 $n$ 相连的边数。 把所有初始与 $n$ 相连的边按另一个端点排序。那么对于排序后相邻的两个点 $l,r(l+1\neq r)$ ，一定会存在一条边 $(l,r)$ 。那么图中一定会存在一个点 $mid$ ，使得初始状态下存在两条边 $(l,mid)$ 和 $(mid,r)$ 。...