bzoj插值

bzoj – 4003 城池攻佔 【可並堆 lazy標記】 好題!!!

傳送門 題目大意: 小銘銘最近獲得了一副新的桌遊,遊戲中需要用 m 個騎士攻佔 n 個城池。 這 n 個城池用 1 到 n 的整數表示。除 1 號城池外,城池 i 會受到另一座城池 fi 的管轄, 其中 fi < i。也就是說,所有城池構成了一棵有根樹。這 m 個騎士用 1 到 m 的整數表示 […]

bzoj – 3252 攻略 【思維 or 可並堆】 好題

傳送門 題目: 就是同時有k個人從一顆有n個節點的樹的根節點出發, 走過的點都可以累加到ans中, 一個點只能被累加一次, 問最大能累加多少. 思路: 其實最開始做這道題是用的倒著做的, 然後dp了一下, 現在學了這個就用這個再做做, 實際上我們從葉子節點開始每次每個節點只加在價值最大的那個子節點上 […]

bzoj 3526: [Poi2014]Card 線段樹

題意 有n張卡片在桌上一字排開,每張卡片上有兩個數,第i張卡片上,正面的數為a[i],反面的數為b[i]。現在,有m個熊孩子來破壞你的卡片了! 第i個熊孩子會交換c[i]和d[i]兩個位置上的卡片。 每個熊孩子搗亂後,你都需要判斷,通過任意翻轉卡片(把正面變為反面或把反面變成正面,但不能改變卡片的位 […]