推 peter506g: 直覺是可以用DP做到O(nk) 09/02 04:18
推 ddavid: 直覺是先跑個O(n)把奇偶分開,奇數那邊跑DP解出k個以下奇 09/02 04:23
→ ddavid: 數所有可能,再接上偶數那邊的所有可能性 09/02 04:24
→ ddavid: 因為偶數那邊的可能性數量可以統計好不同值的個數後組合公 09/02 04:25
→ ddavid: 式解,所以實際上不需要暴力法處理,DP的部分也因為只需要 09/02 04:26
→ ddavid: 知道種類數,因此也可以省去列出可能性的步驟 09/02 04:26
→ ddavid: 等等不對,如果沒要印出所有可能性只需要知道可能性總數的 09/02 04:27
→ ddavid: 話,好像連DP都不需要嘛? 09/02 04:28
這樣可以避免duplicate subarray嗎
推 c225: Subarray 是原 array 裡連續一段嗎 09/02 05:28
是連續的
推 DJWS: binary string / suffix array / lcp array 這樣可以嗎 09/02 05:52
→ DJWS: sort all suffixes. for each suffix, count #(odd) until 09/02 05:55
→ DJWS: reaching k. use lcp array to speed up. 09/02 05:56
推 idiont: 應該可以O(n)求出符合的subarray數量 再利用lcp array減掉 09/02 06:39
→ idiont: 重複的部分 時間複雜度取決suffix array的建構複雜度 最快 09/02 06:39
→ idiont: 是O(n) 09/02 06:39
lcp是kmp裡面那個longest prefix also suffix的那個? 假如是的話, 每一個suffix都要一個lcp?
推 idiont: 把n個suffix排序後 兩兩相鄰的最長共同前綴 就是lcp array 09/02 07:18
推 DJWS: here is another method without lcp: 09/02 14:29
→ DJWS: 1. prefix sum: fast get #(odd) for any interval [a,b]. 09/02 14:31
→ DJWS: 2. for each suffix, binary search k, get its prefix. 09/02 14:32
→ DJWS: 3. push all substrings into a trie. 09/02 14:33
→ DJWS: 4. count number of the nodes of the trie. 全文完 09/02 14:34
感謝大家幫忙, 我之前的方法只會找所有的subarray, 可是不知道怎麼扣掉重複, 等等再把code更新一下, trie那個我等等也來試試看
→ john2007: 輸入[1,1,1,1] k = 1 跑出負數 應該不對吧? 09/02 17:00
→ idiont: 我也有想到trie 不過複雜度應該是O(n^2)?還是能更快? 09/02 17:32
推 DJWS: sure. worst case O(n^2). n-k evens following by k odds. 09/02 17:49
→ DJWS: followed 09/02 20:02
推 ddavid: 傻了,原來是連續的,完全搞錯題意XD 09/02 21:34
推 kokal: 試了一下, len(common_prefix)會把[1,1,1],[1,1]*2都算入 09/02 21:43
推 kokal: 輸入是[1,1,1,1] k=1 09/02 21:45
對欸, 稍微更新一下找common prefix的邏輯了, 感謝
※ 編輯: phoenixrace (24.251.153.7), 09/03/2018 01:10:24
推 FRAXIS: 建一個 suffix tree 然後作 tree traversal? 09/03 05:15
推 DJWS: 樓上一句話就講完了 XD 畢竟n=1000應該可以換成suffix trie 09/03 07:18
推 powertodream: 請問suffix array 是指用甚麼部分建的? 09/03 11:24
推 powertodream: 大概理解, suffix array是甚麼, 不過不太理解怎麼 09/03 11:40
→ powertodream: 用它來加速找出odd count subarray 09/03 11:40
推 powertodream: 理解上, 是不是假如建成suffix trie, 每個tree node 09/03 11:46
→ powertodream: 有count, tree traversal 在odd count <k 就把tree 09/03 11:47
→ powertodream: node count 加到ans? 09/03 11:47
→ powertodream: 不太了解, prefix sum, binary search k 的動作@@" 09/03 11:48
→ powertodream: 這是加速建suffix array的做法嗎? 09/03 11:48
推 powertodream: 唔 如果是distinct array, 那好像treenode不用count 09/03 12:02
推 powertodream: google一下 發現我把suffix array跟suffix trie搞混 09/03 17:04
→ powertodream: 一直以為先有suffix array 再建立 suffix trie 09/03 17:05
→ powertodream: 不過好像有O(N)的做法可以把 suffix trie建起來 09/03 17:08
推 JameC: size 才1000,暴力解+string hashing +map 感覺可以 09/22 19:51
推 JameC: 猜不太到為什麼樓主的O(n^2)過不了...就當我隨便說說吧lol 09/22 19:52
→ oToToT: 單純猜python太慢吧 09/22 23:46
推 rareone: 簡單雙指標就可以做到O(N) 01/06 18:21