作者fatcat8127 (胖胖貓)
看板Prob_Solve
標題[問題] NPSC 2017 國中組初賽 D.吃點心
時間Sun Apr 21 07:50:07 2019
如題，題目在中女中的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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1555804210.A.0E4.html
2F：→ sifmelcara: 做到 O(logN) 的時間更新"所有數字奇偶狀態的"的 hash 04/21 11:09
3F：→ sifmelcara: 但這應該不是 intended solution... 坐等高手 04/21 11:10
4F：→ longlongint: 題目的舉例我看不懂 為什麼吃掉1有算一種？ 04/21 12:19
5F：→ longlongint: 哦 原來數字是種類不是數量 04/21 12:20
6F：推 longlongint: 用積分方式算［0,L] 的奇偶數， 相扣可以得到任意[L, 04/21 13:39
7F：→ longlongint: R]的奇偶數，所以只統計相同奇偶數出現次數k算所有c( 04/21 13:39
8F：→ longlongint: k,2)加起來是答案，樓上用 hash tree 加速做掉了？ 04/21 13:39
9F：推 GYLin: 這是國中題目 所以有國中數學的解法...? 坐等高手+1 04/21 23:46
10F：推 LPH66: 就樓上的方法啦, 積分方式其實就是 prefix sum 而已 04/22 00:56
11F：→ LPH66: 統計可以用例如 std::map 或 std::unordered_map 04/22 00:56
12F：推 GYLin: 種類太多 感覺也只能hash了 04/22 02:33
13F：推 GYLin: 不過hash要怎麼存才不會爆記憶體? 04/22 02:41
14F：→ sifmelcara: 就…只存hash出的值，不存原本的值，祈禱不會碰撞 04/22 10:41
15F：→ sifmelcara: 把10^6個數字hash到uint64_t，有碰撞產生的機率差不 04/22 10:43
16F：→ sifmelcara: 多是 (10^6)^2 / 2^64 而已 (birthday attack) 04/22 10:44
17F：推 GYLin: 剛剛用1e18+3這個prime modulo喇過了... 04/22 14:08
18F：→ GYLin: 仔細想想 1e6種數字 裝到1e60的buckets 還會碰撞也太賽 04/22 14:09
19F：→ GYLin: 講錯 1e18的buckets 04/22 14:10