题解：P6644 [CCO 2020] Travelling Salesperson

· · 题解

HN 省集为数不多自己想出来的一道题。

当提示到增量构造的那一刻，一切都明了了。

老规矩，猜测取到下界来进行构造。

因为毕竟要覆盖所有点，所以路径长度应该是 n 个点。

我们猜测能构造出 n 个点的。

考虑我们现在已经构造出 k-1 个的了，要构造出 k 个的答案，那么我们发现我们肯定是到某个点转颜色，假设转完颜色后到的这个点为 x 那么如果 c_{pre_x,x}=c_{x,k} 就插入到 x 后面，否则只能插入到 x 前面了。

这样我们依然能保持只有一次转变颜色的性质，还可以让答案还是 k。

怎么维护这个过程呢，用双向链表插入即可，每次 O(n) 地扫一遍链表内的元素。

做完了，复杂度 O(n^2)。