03 October, 2006

ACM 10125

這題一看到就是直覺的報搜,不過當然也很直接的TLE一次....
這題其實就是解a+b+c = d這個方程式,如果直接去做的話一定是把(a+b+c)看成一組,d看成另一組,這樣爆下去的話就是O(n^3),但是換個角度看a+b+c=d <=> a+b = d-c,如果用這樣的想法去看這組方程式的話,時間複雜度就瞬間變成O(n^2),這種技巧好像還滿常見的~
我只能說 "爆搜也是一門學問阿!!" (10149 還是沒有爆過...)

No comments: