PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] NPSC 2017 國中組初賽 D.吃點心

看板Prob_Solve (計算數學 Problem Solving)作者 (胖胖貓)時間5年前 (2019/04/21 07:50), 編輯推噓6(6推 0噓 13→)
留言19則, 4人參與, 5年前最新討論串1/3 (看更多)
如題，題目在中女中的OJ上(http://tcgs.tc.edu.tw:1218/ShowProblem?problemid=z033) 目前沒人通過且NPSC補完計畫上的程式碼也是會TLE，當年的紀錄也沒有隊伍AC。 題目的數字個數最多會有 1e6 個，雖然時限是 6s 但枚舉任意組的開頭和結尾形成的子區間判斷會吃TLE。 附個暴力法實作的 Code : https://www.codepile.net/pile/oVxp1RVO 想問一下這題有O(N^2)的暴力法外的其他作法嗎? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.231.101.233 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1555804210.A.0E4.html
→
04/21 11:08, 5年前 , 1F
04/21 11:08, 1F
→
04/21 11:09, 5年前 , 2F
做到 O(logN) 的時間更新"所有數字奇偶狀態的"的 hash
04/21 11:09, 2F
→
04/21 11:10, 5年前 , 3F
但這應該不是 intended solution... 坐等高手
04/21 11:10, 3F
→
04/21 12:19, 5年前 , 4F
題目的舉例我看不懂 為什麼吃掉1有算一種？
04/21 12:19, 4F
→
04/21 12:20, 5年前 , 5F
哦 原來數字是種類不是數量
04/21 12:20, 5F
推
04/21 13:39, 5年前 , 6F
用積分方式算［0,L] 的奇偶數， 相扣可以得到任意[L,
04/21 13:39, 6F
→
04/21 13:39, 5年前 , 7F
R]的奇偶數，所以只統計相同奇偶數出現次數k算所有c(
04/21 13:39, 7F
→
04/21 13:39, 5年前 , 8F
k,2)加起來是答案，樓上用 hash tree 加速做掉了？
04/21 13:39, 8F
推
04/21 23:46, 5年前 , 9F
這是國中題目 所以有國中數學的解法...? 坐等高手+1
04/21 23:46, 9F
推
04/22 00:56, 5年前 , 10F
就樓上的方法啦, 積分方式其實就是 prefix sum 而已
04/22 00:56, 10F
→
04/22 00:56, 5年前 , 11F
統計可以用例如 std::map 或 std::unordered_map
04/22 00:56, 11F
推
04/22 02:33, 5年前 , 12F
種類太多 感覺也只能hash了
04/22 02:33, 12F
推
04/22 02:41, 5年前 , 13F
不過hash要怎麼存才不會爆記憶體?
04/22 02:41, 13F
→
04/22 10:41, 5年前 , 14F
就…只存hash出的值，不存原本的值，祈禱不會碰撞
04/22 10:41, 14F
→
04/22 10:43, 5年前 , 15F
把10^6個數字hash到uint64_t，有碰撞產生的機率差不
04/22 10:43, 15F
→
04/22 10:44, 5年前 , 16F
多是 (10^6)^2 / 2^64 而已 (birthday attack)
04/22 10:44, 16F
推
04/22 14:08, 5年前 , 17F
剛剛用1e18+3這個prime modulo喇過了...
04/22 14:08, 17F
→
04/22 14:09, 5年前 , 18F
仔細想想 1e6種數字 裝到1e60的buckets 還會碰撞也太賽
04/22 14:09, 18F
→
04/22 14:10, 5年前 , 19F
講錯 1e18的buckets
04/22 14:10, 19F
‣ 更多 fatcat8127 的文章
文章代碼(AID): #1Skx0o3a (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 fatcat8127 的文章
文章代碼(AID): #1Skx0o3a (Prob_Solve)