作者cutekid (可爱小孩子)
看板Prob_Solve
标题Re: [问题] NPSC 2017 国中组初赛 D.吃点心
时间Mon Apr 22 20:50:26 2019
我把 sifmelcara 和 GYLin 两位大大的综合一下：
1. state 部份采用 simfmelcara 大大的 xor sum
2. 其余采用 GYLin 大大对 state 做 count 加总
程式码：
https://ideone.com/XJL6RM
※ 引述《GYLin (月月挂长)》之铭言：
: ※ 引述《fatcat8127 (胖胖猫)》之铭言：
: : 如题，题目在中女中的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)的暴力法外的其他作法吗?
: 先讲一下如果数字范围<64的话要怎麽做:
: 假设数字只有K种
: 那我就能用 K bits 表示"目前各种数字总数之奇偶性"
: 比方说看完1 1 3 2 3, 共有三种数字,
: 那他们的数量(2,1,2)奇偶性就是 0 1 0
: 假设 state[i] 为加入第i个数字时的奇偶性, 共有三种数字
: 那 state[0] = 000
: 而区间 [i,j] 是一个符合题目要求的区间
: 等於是 state[i-1] 跟 state[j] 每个bit要完全一样
: 以区间尾巴j的角度来看
: 要数有几个满足的区间头, 就等於是数跟state[j]同样的家伙出现了几次
: 因为数字最多只有64种, 所以奇偶状态可以用long long表达,
: 要做到上面的事情, 只要用一个 map<long long, int> 做为各奇偶状态的counter就好
: 总而言之,
: 每加入一个Ai -> 更新奇偶状态 ->
: 将答案加上"以目前位置为尾巴的区间数量" -> counter++
: 但到目前为止都不是困难的事
: 此题的数字种类为1e6种, 根本不可能去存各奇偶状态的counter,
: 於是仔细想想, 奇偶状态虽然总可能性有 2^(1e6) 种,
: 跑完阵列却也只会出现 1e6种而已,
: 所以拿个够大的数字%掉, 不要运气太差的话就会过了= =
: https://paste.ofcode.org/vnnTrh5q4sW2BfZRv2mWTU
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 1.168.28.142
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1555937429.A.F03.html
1F：→ sifmelcara: 搞不好他它RAND_MAX只有32767 你就WA掉了 （咦） 04/22 21:01
2F：→ cutekid: sifmelcara 大说的没错！ 04/22 21:07
3F：→ cutekid: 保险一点用 4 个 rand() & 65535 串成一个 int64 04/22 21:09
4F：→ cutekid: 上面打错，rand() & 32767 才对 04/22 21:10
5F：推 GYLin: 推推 04/23 10:06
6F：→ GYLin: 第一次看到xor sum 长知识 04/24 01:39
7F：→ cutekid: 借用 Zobrist hashing 的概念应用在这题上面！ 04/24 02:02
9F：推 fatcat8127: 国中生真的有这种知识吗...(眼神死) 04/24 13:06