[問題] 離線處理

看板Prob_Solve (計算數學 Problem Solving)作者 (胖胖貓)時間5年前 (2019/04/09 00:41), 5年前編輯推噓1(105)
留言6則, 2人參與, 5年前最新討論串1/1
想問一下關於 ZJ-c710 這題的離線處理,題目是標準RMQ類型 一般莫隊算法是處理離線問題的代表,ZJ-b417的區間眾數是經典 但是這題要取餘數該怎麼下手呢?應該不可能將各個數字計算個數... 雖然題目的標籤處提示是期望空間複雜度為 O(N+M)。 N 應該原始數據,M 代表所有的查詢需要儲存達到符合離線的作法, 但具體的方式就完全卡住。 解法: ( 離線處理=>莫隊 ) 89%(11% TLE,卡在當除數很小但是暴力法查詢倍數導致的TLE) 根據theshold決定採用莫隊還是前綴和計算 訂一個 threshold 來決定當除數小於時透過『前綴和』計算區間內可以被該除數整除 的個數,因為前綴和的計算方式整體記憶體空間不能過大(√NxN太大,所以才把 threshold調降為50),若大於等於則採用莫隊算法處理, 這時即便是暴力查詢倍數時間成本也是K√N,K=√N/threshold。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.208.164 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1554741717.A.5D2.html

04/09 10:31, 5年前 , 1F
04/09 10:31, 1F

04/09 10:32, 5年前 , 2F
這底下的討論之類的可能可以回答你
04/09 10:32, 2F

04/09 13:12, 5年前 , 3F
感謝oT大大
04/09 13:12, 3F

04/12 01:47, 5年前 , 4F
實作了莫隊算法,不過只能拿到89%和一個TLE,原因應
04/12 01:47, 4F

04/12 01:47, 5年前 , 5F
該是累加除數的倍數時太耗時間
04/12 01:47, 5F

04/21 07:26, 5年前 , 6F
感謝 cutecpu 的指導 問題以解決
04/21 07:26, 6F
※ 編輯: fatcat8127 (61.231.101.233), 04/21/2019 07:32:16
文章代碼(AID): #1SgtdLNI (Prob_Solve)
文章代碼(AID): #1SgtdLNI (Prob_Solve)