竹園論壇

標題: [Tree][枚舉]1239 - 致命武器 Lethal Weapon [打印本頁]

作者: Sylveon 時間: 2015-3-23 16:50
標題: [Tree][枚舉]1239 - 致命武器 Lethal Weapon
原題：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]

歡迎光臨竹園論壇 (http://forum.tfcis.org/)