作者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/cn.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