[問題] 紅白彩帶 (APCS201902)

看板 Prob_Solve
作者
時間
留言 11則留言,3人參與討論
推噓 6  ( 6推 0噓 5→ )
給定彩帶的長度 N 和每一格的顏色(0=白,1=紅),K次的著色(保證會在白色格子塗紅), 輸出的兩個數字分別為每次著色後最長和最短的紅色區間長度總和。 這題會用到 DSU 連通的概念,維護每次著色後最長的紅色區間長度問題不大。 但問題點在於維護最短區間長度。 因為著色的關係,導致最多2個區間合併,代表 RootID 的長度會被改變。 又因為格子個數最多會有 1e5 個,暴力法理論上應該不可行。 我只想到 Mapping HEAP 這個資料結構(不確定有沒有這種東西...)。 基礎的 HEAP 資料結構加上一個映射陣列( mapp[RootID]=這個 RootID在HEAP的位置 ) 這個 HEAP 只維護 每個 Group 的代表ID 並且依照長度維護(越小越上層)。 保證某個 RootID 長度被改變時是 ㏒N (HeapDown), 或是因為區間合併導致需要刪除某個存在 HEAP 內的 RootID 時是 ㏒N (HeapUp+Down)。 不過考慮到這題屬 APCS,應該存在某種合理的資料結構應付上述需求? 至少不是要當場寫這種 Mapping HEAP吧... 最後附上程式碼:https://www.codepile.net/pile/NG2lD4rl ※ 編輯: fatcat8127 (61.222.86.91 臺灣), 11/08/2020 01:57:38 ※ 編輯: fatcat8127 (101.12.22.166 臺灣), 11/08/2020 03:36:07
1Fckc1ark: 不一定要改heap現有的 放新產生的頭尾進去即可 11/08 12:30
你說的我有想過,不過不把因為合併的點刪除時會導致整個 HEAP 根據長度排序會出問題 如果是要根據合併後的 Group ID 長度為統一時,代表需要同步調整個 HEAP 當中 屬於這個 Group 的其他點確保 HEAP 的架構正確。
2Fucrxzero: 跨謀 11/08 15:03
※ 編輯: fatcat8127 (61.222.86.91 臺灣), 11/08/2020 22:59:37
3Fckc1ark: 我heap存的是(len, left, right) 再用輔助的array很快就 11/09 00:26
4Fckc1ark: 知道目前看到這個是不是過時的 11/09 00:26
5Fckc1ark: 反正n變兩倍不影響heap複雜度 11/09 00:27
後來想到可以用 multiset(存在多個長度相同的Group)+struct(定義小於=根據長度排序) muiltiset.find() 可以找到指定的 struct,可以直接 erase, 但是找到的 struct 是 read-only,所以更新某個已經存在的 Group 長度時, 需要 erase older version + insert new version(after updating)。 這邊附上實作的程式:https://www.codepile.net/pile/gaWjg6vb ※ 編輯: fatcat8127 (61.222.86.91 臺灣), 11/09/2020 12:30:51
6Fckc1ark: https://tinyurl.com/y6gwpfyp 我的意思是這樣 11/09 13:01
7Fckc1ark: combo裡的值存每段紅色彩帶的長度(僅兩端) 非兩端不重要 11/09 13:04
8Fucrxzero: 好想跟著寫但我連leetcode 都快寫不完了 11/09 15:56
9FDJWS: O(nk)不行嗎? 那就O(kk)吧! 排序所有區間、插入排序法 11/11 10:40
10FDJWS: O(kk)不行嗎? 那就O(klogn)吧! 來一發線段樹就搞定了 11/11 10:44
11FDJWS: O(klogn)不行嗎? 那就O(klogk)吧! 二元樹紀錄所有區間 11/11 10:48