作者rareone (拍玄)
看板Prob_Solve
标题[心得] CF576C Mo's algorithm on non-DS problem
时间Fri Mar 29 00:18:44 2019
题干：平面给 N 个点，输出一条 circuit 走过所有点一次，而且长度小於等於 2.5e9
条件 (x, y) in [0, 1e6] X [0, 1e6], N <= 1e6
作法：
我一开始看到这题的时候真的用莫队下去切，也没有分析一下复杂度，就这样踩到雷
我的莫队是这样 implement 的：
key = make_pair(x / SQRT, y)
sort points by key
分析一下为何错误：
SQRT = sqrt(1e6) = 1000
莫队把 x 轴分成约 SQRT 块，每一块的 cost 右界移动最多是 1e6
** 块跟块之间的转移 cost 是 1e6（右界指标要回来）**
光右界就能轻松造出 2e9
左界移动每次幅度大可以到 SQRT （外加 O(N) 均摊，倒不是很关键）
左届总计也差不多 1e9 刚好吃 WA
如果交错右届可以磨掉 ** 之间的 cost 也就是：
key = make_pair(x / SQRT, x / SQRT % 2 ? y : -y)
sort point by key
偷看了一下测资，的确没有 cost 是大於 2e9 ，很接近倒是有
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.114.216.110
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1553789929.A.B3C.html
1F：推 FRAXIS: 这是 Eucldean TSP 吗？ 03/29 11:09
2F：→ rareone: Nope 是用莫队想法 03/29 13:10
3F：推 oToToT: 前几天也刚好看到这题XD 03/30 07:55