Re: [理工] [algo] 99中央第5題

看板Grad-ProbAsk作者FRAXIS (喔喔)時間15年前 (2011/01/09 11:02)推噓6(6推 0噓 5→)

留言11則, 4人參與討論串4/4 (看更多)

※ 引述《aoqq12 (阿任)》之銘言： : http://ezproxy.lib.ncu.edu.tw:8080/~arhui/cexamn/exam/EC02_99_01.pdf : 今天一直卡住= = 第五題 : 感覺上用dp能做出來可是想半天還是卡住 : 我是想說先將 x y z排序 : 然後 a[i]= k-xi : 在到 y or z排序好的找小於a[i]的數來做組合 : 不過好像很沒技術性....= =" : 這該怎麼解= =" 才會比較有效率有請高手解惑 orz 首先，令Z' = k - z, for all elements z in Z 這問題就變成要找x, y, z 使得 x + y = z, where x in X, y in Y, z in Z' 這步要花O(|Z|)的時間第二步，把Y和Z'做排序，這步要花O(|Z| lg |Z| + |Y| lg |Y|)的時間第三步對一個在X中的元素x，產生Yx = y + x, for all elements y in Y 我們現在要找的就是Ya和Z'的共同元素，只要找到了就是有解，因為Yx和Z' 都是有序的，所以要找共同元素只需要O(|Z| + |Y|)的時間。第四步對所有在X中的元素x執行第三步，時間是O(|X|(|Z| + |Y|))。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.119.162.50 ※ 編輯: FRAXIS 來自: 140.119.162.50 (01/09 11:08)

推

christianSK

01/09 13:56, , 1^F

01/09 13:56, 1^F

→

FRAXIS

01/09 18:59, , 2^F

01/09 18:59, 2^F

→

FRAXIS

01/09 19:00, , 3^F

01/09 19:00, 3^F