並查集

1/7ページ

codeforces 461 D Appleman and Complicated Task

Descritpion Solution 這題和之前沒改出來的矩陣遊走思想是類似的,即唯一確定的第一行確定了整個矩陣。那麼可以設第一行為未知數,討論一下其餘位置的取值情況。可以發現(0,k)能影響到的點滿足是連續的奇數或連續的偶數。那麼抽出奇偶點然後就能用字首異或和做了。 題目轉化為:給定一些限制條 […]

皮皮_ssl2542_並查集

Description 皮皮通過一次聚會認識了n個妹子。經過仔細的研究皮皮發現了一個有趣的現象:那就是有m對妹子是互相認識的。然而如果兩個妹子直接或間接地認識(A認識B,B認識C,則A認識C),那麼皮皮就只能在這兩個妹子裡面選一個來泡。 然而空空空空的皮皮想要泡到儘量多的妹子,於是皮皮就開始採取了一 […]

修復公路 洛谷1111 並查集

題目背景 A地區在地震過後,連線所有村莊的公路都造成了損壞而無法通車。政府派人修復這些公路。 題目描述 給出A地區的村莊數N,和公路數M,公路是雙向的。並告訴你每條公路的連著哪兩個村莊,並告訴你什麼時候能修完這條公路。問最早什麼時候任意兩個村莊能夠通車,即最早什麼時候任意兩條村莊都存在至少一條修復完 […]

關押罪犯 洛谷1525 並查集

題目描述 S 城現有兩座監獄,一共關押著N 名罪犯,編號分別為1~N。他們之間的關係自然也極不和諧。很多罪犯之間甚至積怨已久,如果客觀條件具備則隨時可能爆發衝突。我們用“怨氣值”(一個正整數值)來表示某兩名罪犯之間的仇恨程度,怨氣值越大,則這兩名罪犯之間的積怨越多。如果兩名怨氣值為c 的罪犯被關押在 […]

bzoj1015 [JSOI2008]星球大戰starwar 並查集

題目描述 很久以前,在一個遙遠的星系,一個黑暗的帝國靠著它的超級武器統治者整個星系。某一天,憑著一個偶然的機遇,一支反抗軍摧毀了帝國的超級武器,並攻下了星系中幾乎所有的星球。這些星球通過特殊的以太隧道互相直接或間接地連線。 但好景不長,很快帝國又重新造出了他的超級武器。憑藉這超級武器的力量,帝國開始 […]

食物鏈 洛谷2024 並查集

題目描述 動物王國中有三類動物 A,B,C,這三類動物的食物鏈構成了有趣的環形。A 吃 B,B 吃 C,C 吃 A。 現有 N 個動物,以 1 - N 編號。每個動物都是 A,B,C 中的一種,但是我們並不知道 它到底是哪一種。 有人用兩種說法對這 N 個動物所構成的食物鏈關係進行描述: 第一種說法 […]

貨車運輸 洛谷1967 最大生成樹 lca c

題目描述 A 國有 n 座城市,編號從 1 到 n,城市之間有 m 條雙向道路。每一條道路對車輛都有重量限制,簡稱限重。現在有 q 輛貨車在運輸貨物, 司機們想知道每輛車在不超過車輛限重的情況下,最多能運多重的貨物。 輸入輸出格式 輸入格式: 輸入檔名為 truck.in。 輸入檔案第一行有兩個用一 […]

2017年09月07日提高組第一式 A

Description 三大戰役的平津戰場上,傅作義集團在以北平、天津為中心,東起唐山西至張家口的鐵路線上擺起子一字長蛇陣,並企圖在潰敗時從海上南逃或向西逃竄。為了就地殲敵不讓其逃走,毛澤東制定了先切斷敵人東灑兩頭退路然後再逐個殲滅敵人的戰略方針。 秉承偉大軍事家的戰略思想,作為一個有智慧的軍長你, […]

1 7