#19252: 賽後題解


310573sao (Jiburiru)

學校 : 新北市立板橋高級中學
編號 : 48055
來源 : [59.127.176.2]
最後登入時間 :
2020-04-01 20:44:03
e370. 翻牌 -- 108學年度板橋高中校內資訊學科能力競賽Day3_pE310573sao | From: [59.127.176.2] | 發表日期 : 2019-09-20 20:21

 

N: 牌數 , M: 相異數字個數, E:邊數

 

暴力判斷: O(2N・N)

把正面反面視為01, 用 2N 種 01 bit 來決定拿正面或反面,同時紀錄有沒有拿過。

 

回溯法: O(2N)

窮舉拿正面或反面。用 vis 維護有沒有拿過這張數字。

 

接下來的思路,基本上是將問題轉化成圖論的問題。

 

二分匹配: O(N • E) 

將卡牌正反面數字與卡牌編號建邊,從牌面數字大的到小的來二分匹配,如果當前卡牌編號沒有匹配過,就匹配,否則考慮被匹配的數字(一定比較大)有沒有其他牌同樣有這個被匹配的數字。

 

時間複雜度最壞應該是 1+2+3 + ...+ N ?  

 

剩下的兩個方法想法類似:

 

把卡牌的數字(a, b)可以當作一條邊,而我們希望集合和最大那就是從大的數字開始選。

當這些邊都建完後會發現一件事,當有連通的數字的數量有等於或超過的邊數時,我們可以全拿,但是如果少一條邊(一定是N-1條邊, 樹),我們會少拿一個,讓少拿的最小就好。

 

問題簡化成建邊 then 找環or樹。

 

BFS/DFS: O(N+M+E ) 。 

用到的想法就是點數和邊數的關係,建邊(a, b)和(b, a)並爆搜所有連通塊,同時計數 or 判環即可。



並查集: O( Nㆍα(N) + M ) ,約為O(N)

把每張數字初始不同集合,每次把數字(a, b) union, 如果已經在同個set 代表有環了, merge的過程需要維護卡牌數量和circle有無,最後從大數到小數檢查,有環就加,無環就扣數量,同個set的最後一張牌不要算。

 

109 的牌面數字 要用離散化處理 !!

 
#19253: Re:賽後題解


310573sao (Jiburiru)

學校 : 新北市立板橋高級中學
編號 : 48055
來源 : [59.127.176.2]
最後登入時間 :
2020-04-01 20:44:03
e370. 翻牌 -- 108學年度板橋高中校內資訊學科能力競賽Day3_pE310573sao | From: [59.127.176.2] | 發表日期 : 2019-09-20 20:26

實測 DFS #14以後會吃 RE Segmentation Fault 但照理說應該是MLE?  但512MB是上限了...

 
 
ZeroJudge Forum