bzoj

1/37ページ

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

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

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

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

bzoj1370 團伙 【並查集】

題目描述 在某城市裡住著 n 個人,任何兩個認識的人不是朋友就是敵人,而且滿足: 1、我朋友的朋友是我的朋友; 2、我敵人的敵人是我的朋友; 所有是朋友的人組成一個團伙。告訴你關於這 n 個人的 m 條資訊,即某兩個人是朋友,或者某兩個人是敵人,請你編寫一個程式,計算出這個城市最多可能有多少個團伙? […]

bzoj1370 團伙

團伙 題目背景: bzoj1370 分析:並查集,對於兩個敵人,將x與y n,y與x n,合併,然後對於朋友,將x與y合併,然後就可以符合題目要求了,敵人的敵人是朋友,朋友的朋友是朋友,注意對於朋友,x n與y n不能合併,因為沒有說朋友的敵人一定是敵人。最後統計1 ~ n中有多少集合就可以了 So […]

bzoj 3319: 黑白樹 (並查集)

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