[問題] 紅白彩帶 (APCS201902)
看板Prob_Solve (計算數學 Problem Solving)作者fatcat8127 (胖胖貓)時間4年前 (2020/11/08 01:33)推噓6(6推 0噓 5→)留言11則, 3人參與討論串1/1
給定彩帶的長度 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
推
11/08 12:30,
4年前
, 1F
11/08 12:30, 1F
你說的我有想過，不過不把因為合併的點刪除時會導致整個 HEAP 根據長度排序會出問題
如果是要根據合併後的 Group ID 長度為統一時，代表需要同步調整個 HEAP 當中
屬於這個 Group 的其他點確保 HEAP 的架構正確。
推
11/08 15:03,
4年前
, 2F
11/08 15:03, 2F
※ 編輯: fatcat8127 (61.222.86.91 臺灣), 11/08/2020 22:59:37
推
11/09 00:26,
4年前
, 3F
11/09 00:26, 3F
→
11/09 00:26,
4年前
, 4F
11/09 00:26, 4F
→
11/09 00:27,
4年前
, 5F
11/09 00:27, 5F
後來想到可以用 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
推
11/09 13:01,
4年前
, 6F
11/09 13:01, 6F
→
11/09 13:04,
4年前
, 7F
11/09 13:04, 7F
推
11/09 15:56,
4年前
, 8F
11/09 15:56, 8F
推
11/11 10:40,
4年前
, 9F
11/11 10:40, 9F
→
11/11 10:44,
4年前
, 10F
11/11 10:44, 10F
→
11/11 10:48,
4年前
, 11F
11/11 10:48, 11F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
