尤拉回路bzoj

1/3ページ

bzoj 3319: 黑白樹 (並查集)

題目描述 傳送門 題目大意:給定一棵樹,邊的顏色為黑或白,初始時全部為白色。維護兩個操作: 1.查詢u到根路徑上的第一條黑色邊的標號。 2.將u到v 路徑上的所有邊的顏色設為黑色。 Notice:這棵樹的根節點為1 題解 先將所有操作正著進行一遍,將所有的黑邊相鄰的點按照關係合併,就是一個集合中的代 […]

BZOJ 4505 K個串 主席樹標記永久化

Description     兔子們在玩 kk 個串的遊戲。首先,它們拿出了一個長度為 nn 的數字序列,選出其中的一個連續子串,然後統計其子串中所有數字之和(注意這裡重複出現的數字只被統計一次)。     兔子們想知道,在這個數字序列所有連續的子串中,按照以上方式統計其所有數字之和,第 kk 大 […]

BZOJ 3720 Gty的妹子樹 塊狀樹

題目大意:維護一棵樹,每個點有一個權值,提供下列操作: 1.詢問某棵子樹中有多少個節點的權值大於x 2.修改某個節點的權值 3.增加一個葉子節點 強制線上 傳說中的樹分塊 首先DFS,對於每個節點,如果這個節點的父親節點所在塊未滿,就塞進父節點所在塊中,否則自成一塊,然後與父節點所在的塊連邊 新增節 […]

BZOJ 3720 Gty的妹子樹 樹上分塊

題目大意:給出一棵樹,要求維護:1.求出以x為根節點的子樹的嚴格大於y的數量。 2.將一個節點的權值改變。 3.在一個節點下加一個權值為y的節點。 思路:分塊這個東西太神了(別找我分析時間複雜度。。樹上的分塊更神。。。 首先,分塊的原則和正常分塊一樣,把一棵樹分成√n塊,每一塊不超過√n個,然後所有 […]

[BZOJ 2502]清理雪道:上下界網路流

點選這裡檢視原題 點選這裡檢視上下界網路流教程 這個題很明顯就是: 從ss到所有點連下界00上界infinf的邊(因為可以從任何點出發) 從所有出度為零的點到tt連下界00上界infinf的邊(最優方案一定是到達該點才結束) 所有點向他能到達的點連下界11上界infinf的邊(每條邊至少走一次) 那 […]

bzoj 4155: [Ipsc2015]Humble Captains 最小割 dp

題意 每天下午放學時都有n個zky衝出教室去搞基。搞基的zky們分成兩隊,編號為1的zky是1號隊的首領,編號為2的zky是2號隊的首領。其他的zky可以自由選擇是去1隊還是2隊。 zky們當中有幾對zky是好基友(同一個zky可能在多對“好基友”關係中),如果一對好基友在同一個隊,那麼這個隊的戰鬥 […]

bzoj 4298: [ONTAK2015]Bajtocja hash啟發式合併

題意 給定d張無向圖,每張圖都有n個點。一開始,在任何一張圖中都沒有任何邊。接下來有m次操作,每次操作會給出a,b,k,意為在第k張圖中的點a和點b之間新增一條無向邊。你需要在每次操作之後輸出有序數對(a,b)的個數,使得1<=a,b<=n,且a點和b點在d張圖中都連通。 1<=d […]