算法合集之回到起點——一種突破性思維(已修改)
2024-12-20 11:31 本頁面
【正文】 回到起點 —— 一種突破性思維 南京市外國語學(xué)校 朱澤園 問題一的提出 USACO Shaping Regions 改編 ?N個不同顏色的不透明長方形（ 1=N=3000） ?放在一張長寬分別為 A、 B的白紙上 ?邊與白紙的邊緣平行 ?求俯視時看到的所有顏色的面積 問題一的解決 —— 簡單的預(yù)處理 ?離散化 ?整數(shù)坐標(biāo) ?坐標(biāo)范圍在1~2n之間。 1 2 3 4 5 6 1 2 3 4 5 6 離散行 離散列 離散格 問題一的解決 —— 經(jīng)典算法 [1,10] [1,5] [5,10] [1,3] [3,5] [5,7] [7,10] [1,2] [2,3] [3,4] [4,5] [5,6] [6,7] [7,8] [8,10] [8,9] [9,10] [3,8]線段對應(yīng)線段樹上節(jié)點 問題一的解決 —— 經(jīng)典算法 ?自頂至底依次插入顏色為 X的線段 [l,r]，該區(qū)間 [l,r]上原有顏色不被替換，其余部分染上顏色 X。 ?O(logn) ?返回所有顏色的覆蓋量。 ?O(n) 問題一的解決 —— 經(jīng)典算法 ?O(n2logn) ?優(yōu)點： ?廣為人知 ?復(fù)雜度較低，練習(xí)線段樹的經(jīng)典教材 問題一的解決 —— 樸素算法 ?O(n3) 問題一的解決 —— 另
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1