Re: [问题] NPSC 2017 国中组初赛 D.吃点心

楼主: cutekid (可爱小孩子)   2019-04-22 20:50:26
我把 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
作者: sifmelcara (sifmelcara)   2019-04-22 21:01:00
搞不好他它RAND_MAX只有32767 你就WA掉了 (咦)
楼主: cutekid (可爱小孩子)   2019-04-22 21:07:00
sifmelcara 大说的没错!保险一点用 4 个 rand() & 65535 串成一个 int64上面打错,rand() & 32767 才对
作者: GYLin (Lynx)   2019-04-23 10:06:00
推推
楼主: cutekid (可爱小孩子)   2019-04-24 02:02:00
借用 Zobrist hashing 的概念应用在这题上面!http://www.devacg.com/?post=591
作者: fatcat8127 (胖胖猫)   2019-04-24 13:06:00
国中生真的有这种知识吗...(眼神死)

Links booklink

Contact Us: admin [ a t ] ucptt.com