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