查看: 768|回復: 0

[TIOJ] [Tree][枚舉]1239 - 致命武器 Lethal Weapon

[複製鏈接]
  • TA的每日心情
    慵懶
    2015-4-10 14:18
  • 簽到天數: 78 天

    [LV.6]常住居民II

    176

    主題

    612

    帖子

    3959

    積分

    管理員

    Rank: 9Rank: 9Rank: 9

    積分
    3959

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

    發表於 2015-3-23 16:50:00 | 顯示全部樓層 |閱讀模式

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

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

    x
    原題:http://tioj.ck.tp.edu.tw/problems/1239
    AC:http://tioj.ck.tp.edu.tw/submissions/13047

    莫名的把雙向邊建成單向邊然後一直WA...

    我們可以發現切出來的線段一定是N-1的因數,而N-1小於10000,也沒幾個因數,所以我們可以枚舉所有因數,檢查是否能將現段切成該長度。

    我們定義函數[tex]check(X)[/tex]為以X為根的子樹,尚未配對的直鏈線段長,若為-1為無解。顯然的葉子的check()值為0。
    計算X的check值,我們可以遞迴它的子樹,然後把子樹的所有check值加一(代表child到根的那一段),開始兩兩配對是否相加等於L(要檢查的因數),如果有超過2個數字無法配對,即為失敗回傳-1,則回傳剩下的數字(或0)給上面的parent解決。

    正確性嗎?我們只有一條邊往parent,如果剩下超過兩條不能配對的鏈,把那條邊分給誰都不能滿足,如此而已。
    [sojcodepad]f5e35f2c[/sojcodepad]


    回復

    使用道具 檢舉

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

    本版積分規則

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