[心得] CF576C Mo's algorithm on non-DS problem
看板Prob_Solve (計算數學 Problem Solving)作者rareone (拍玄)時間5年前 (2019/03/29 00:18)推噓2(2推 0噓 1→)留言3則, 3人參與討論串1/1
題幹：平面給 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://www.ptt.cc/bbs/Prob_Solve/M.1553789929.A.B3C.html
推
03/29 11:09,
5年前
, 1F
03/29 11:09, 1F
→
03/29 13:10,
5年前
, 2F
03/29 13:10, 2F
推
03/30 07:55,
5年前
, 3F
03/30 07:55, 3F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
