查看: 355|回復: 2

[競賽分享] [成大賽2015]野生題解_2.7182(E~F)

[複製鏈接]
  • TA的每日心情
    開心
    2015-6-17 11:50
  • 簽到天數: 177 天

    [LV.7]常住居民III

    15

    主題

    315

    帖子

    1437

    積分

    金牌會員

    Rank: 6Rank: 6

    積分
    1437

    新手達陣台南一中資訊社

    發表於 2015-7-9 09:33:42 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

    x
    1. Problem E.冰雪奇緣

    題目是給你一個圖,長度小於給定數邊的才能通過
    問說一個人是否能從一點走遍全部的邊(可以重複)

    其實這題只要直接刪除長度大於給定距離的邊,然後在快樂的判斷一下連通性就可以AC了
    完全沒有陷阱,輕鬆AC.

    2. Problem F.大家族


    題目是給你一個連通的族譜,求他的最大親等
    其實這就只是一個基本的樹直徑而已.

    2次DFS O(N) 即可解決.


    但是你一開始會發現你會WA,然後過一陣子才變成AC.
    這是有內情的.話說有一隊拿到WA之後,他們正好有人在UVa上寫過這題,於是Judge就被嗆了(X.
    為了不要再被嗆,所以只好把WA改成AC以平息眾怒.(大誤
    =========================================
    就先這樣啦 剩下的以後再看看(?

    點評

    jd3
    第一句小修正 : 長度小於等於給定數的邊才能通過  發表於 2015-7-9 23:20

    評分

    參與人數 1金幣 +4 收起 理由
    domen111 + 4 給個讚!

    查看全部評分

    目標:Taiwan Oranges-Integraled 2016 (TOI'16)台灣積分橘子。
    回復

    使用道具 檢舉

  • TA的每日心情
    鬱悶
    2015-5-15 22:38
  • 簽到天數: 33 天

    [LV.5]常住居民I

    75

    主題

    302

    帖子

    766

    積分

    版主

    TFcis - 105 附設監工官

    Rank: 7Rank: 7Rank: 7

    積分
    766

    台南一中資訊社程式設計達人 - 2014

    發表於 2015-7-9 23:59:23 | 顯示全部樓層
    補充:

    pF 樹直徑 詳解

    首先是題目的祖譜
    雖然說是祖譜但哪一代根本不重要
    重點是沒有環,所以是樹

    題目找樹上最遠的兩點的距離
    也就是所謂「直徑」
    這東西有點像有機化學在找最長碳鏈
    有認真讀有機化學應該會很有感覺

    作法大致長這樣:
    1.從任意一點 DFS 找到最遠的點
    2.從找到的點再DFS一次,一樣找到最遠的點
    3.以上兩個步驟找到的兩點必為其中一條直徑上的兩點


    說明(這不是嚴謹的證明, 用詞和符號也不學術):

    以下解釋在邊權>0時才成立

    _0:先定義直徑就是最遠兩點間的路徑
    _1:直徑不一定只有一條,但都一樣長 ( 廢話 ˋ ˊ )
    _2:直徑間必相交於一半長度,或部分重疊
    _3:如果有直徑AB,直徑上有一點P,
          A在P左邊(或同點), B在P右邊(或同點)
          P往左走到C的距離|CP|若>|AP|
          則 |CPB| > |APB|, AB就不是直徑
          所以得知C往左走最遠一定是A或距離相同的點(同樣可以當直徑端點)
    _4:左右走並沒什麼差別
           所以DFS能走到的最遠的點一定是某個直徑端點
    _5:從一個直徑端點能走到最遠的點必然為某個直徑上的另一端點
           否則這個點不可能是直徑上的點(ㄜ...這麼說是為了讓前一段落看不懂還能理解)

    綜合以上
    DFS第1次找到直徑上某點
    第2次找到另一點

    長度就是DFS深度

    此題結束。
    <這是個人簽名欄位>
    回復 支持 反對

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表