hdu最大子段和

2/3ページ

HDU 6162 Ch’s gift 【LCA暴力 or 主席樹 樹鏈剖分】

傳送門 題目大意: 一顆樹, 樹上有點權, 每次詢問u, v的樹上路徑上的點權範圍在[a, b]內的權值和是多少. 思路: 這道題居然暴力能過, 而且巨快…. 後面還是寫了寫正解. 很明顯我們需要把u – > v的路徑剖下來, 然後問題就變成區間問題了, 詢問區間中在一定範圍內的數 […]

HDU 5828 Rikka with Sequence 【線段樹區間更新中單點更新】 好題!!!

傳送門 題目大意: 有三種操作: 1. 區間開根 2.區間加 3.詢問區間和 思路: 如果沒有第二種操作, 就非常簡單了, BZOJ上面有一道就是這種題, 因為開根的話每個數會下降的很快, 所以暴力的搞也不會搞太久, 但是有了區間加就不一樣了.. 比如 3 4 3 4 3 4 3 4 …. 這段區間 […]

HDU – 6319 Ascending Rating 【單調佇列 逆向思維】

傳送門 題目大意: 給定一個序列 a[1..n],對於每個長度為 m 的連續子區間,求出區間 a 的最大值以及從左往右掃描該區間時 a 的最大值的變化次數 思路: 首先最大值很好維護, 主要是count是難點, 所以我們考慮下逆向做, 那麼對於一個區間的開始. 後面比它小的都被剔除了. 所以剩下的就 […]

HDU – 6110 路徑交 【LCA 線段樹 思維】

傳送門 悟: 樹上路徑相交問題一定和他們之間的LCA的最深的那一兩個有關係!!! 題目大意: 給定一棵n個點的樹,以及m條路徑,每次詢問第L條到第R條路徑的交集部分的長度(如果一條邊同時出現在2條路徑上,那麼它屬於路徑的交集) 思路: 首先我們考慮兩條路徑相交的情況, A – > […]

HDU 2196 樹形dp入門

連結 : 傳送門 題意: 給你一個n個節點的棵樹,然後給你和 第i臺電腦與第a臺電腦相連的花費 v 問你最長的線路是多長(求樹上任意節點所能達到的最遠點的距離) 樹形dp ,開個陣列 分別記錄這個點到子樹最遠節點的最長距離和次長距離 和記錄到父節點上的最長距離 這樣在樹上dp 1. 求子樹最長 和 […]

HDU 4288 Coder 離散化 線段樹

 題意:對一個集合進行插入與刪除操作。要求詢問某個時刻,集合中的元素從小到大排序之後,序號%5 ==3 的元素值之和。 首先元素的值可以達到10^9 所以,首先離散化,將所有可能的元素值對映到正整數。 然後線段樹的話,用index  存當前節點 所含的元素數量。 用 D [R] 存 所含的元素中,序 […]