TA的每日心情 | 慵懶 2015-4-10 14:18 |
---|
簽到天數: 78 天 [LV.6]常住居民II
管理員
- 積分
- 3959
|
趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
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]
|
|