jeremydingeric@gmail.com
(164253)
學校
:
臺北市立成功高級中學
編號 : 158900
來源 : [42.77.129.143]
最後登入時間 ：
2024-11-15 12:14:59
O(n2)解
全部讀入後 先假設第一個是三角形的一邊 假設第二個也是一邊 把三以後的所有邊窮舉看是不是直角三角形
舉完繼續固定第一個 改為第三個當作第二邊 繼續舉 依此類推 複雜度n2/2
判定是不是直角三角形也很簡單 a2+b2==c2就行 不用開根號
O(n2)解 但是加一點優化
一樣窮舉 但是由於這題長度範圍不大 開一個陣列l[101](懶得減1 直接多開一格 而且多做減1還慢)儲存每種長度的木棒出現次數
另一個陣列v儲存不重複的木棒長度(就是讀入長度i發現l[i]==0就加入v)
對v內的元素窮舉計算sqrt(a2+b2) 然後ans+=l[a]*l[b]*l[sqrt(a2+b2)]
O(1)解
由於長度範圍不大 事先找出三邊在100以內的勾股數放到陣列a 讀入木棒跟n2優化的解法一樣放進l 對a內的元素窮舉l[a[k][0]]*l[a[k][1]]*l[a[k][2]] k從0到51
順便附上這個陣列a[52][3]={{3,4,5},{6,8,10},{9,12,15},{12,16,20},{15,20,25},{18,24,30},{21,28,35},{24,32,40},{27,36,45},{30,40,50},{33,44,55},{36,48,60},{39,52,65},{42,56,70},{45,60,75},{48,64,80},{51,68,85},{54,72,90},{57,76,95},{60,80,100},{5,12,13},{10,24,26},{15,36,39},{20,48,52},{25,60,65},{30,72,78},{35,84,91},{8,15,17},{16,30,34},{24,45,51},{32,60,68},{40,75,85},{7,24,25},{14,48,50},{21,72,75},{28,96,100},{9,40,41},{18,80,82},{11,60,61},{12,35,37},{24,70,74},{13,84,85},{16,63,65},{20,21,29},{40,42,58},{60,63,87},{28,45,53},{33,56,65},{36,77,85},{39,80,89},{48,55,73},{65,72,97}};
| AC (2ms, 76KB) |
mountainwu14@gmail.com
(吳小四)
學校
:
不指定學校
編號 : 187101
來源 : [123.193.136.130]
最後登入時間 ：
2024-07-25 20:25:33
python的陣列是這樣,方便copy
a=[ [3,4,5],[6,8,10],[9,12,15],[12,16,20],[15,20,25],[18,24,30],[21,28,35],[24,32,40],[27,36,45],[30,40,50],[33,44,55],[36,48,60],[39,52,65],[42,56,70],[45,60,75],[48,64,80],[51,68,85],[54,72,90],[57,76,95],[60,80,100],[5,12,13],[10,24,26],[15,36,39],[20,48,52],[25,60,65],[30,72,78],[35,84,91],[8,15,17],[16,30,34],[24,45,51],[32,60,68],[40,75,85],[7,24,25],[14,48,50],[21,72,75],[28,96,100],[9,40,41],[18,80,82],[11,60,61],[12,35,37],[24,70,74],[13,84,85],[16,63,65],[20,21,29],[40,42,58],[60,63,87],[28,45,53],[33,56,65],[36,77,85],[39,80,89],[48,55,73],[65,72,97]]
O(1)解由於長度範圍不大 事先找出三邊在100以內的勾股數放到陣列a 讀入木棒跟n2優化的解法一樣放進l 對a內的元素窮舉l[a[k][0]]*l[a[k][1]]*l[a[k][2]] k從0到51
順便附上這個陣列a[52][3]={{3,4,5},{6,8,10},{9,12,15},{12,16,20},{15,20,25},{18,24,30},{21,28,35},{24,32,40},{27,36,45},{30,40,50},{33,44,55},{36,48,60},{39,52,65},{42,56,70},{45,60,75},{48,64,80},{51,68,85},{54,72,90},{57,76,95},{60,80,100},{5,12,13},{10,24,26},{15,36,39},{20,48,52},{25,60,65},{30,72,78},{35,84,91},{8,15,17},{16,30,34},{24,45,51},{32,60,68},{40,75,85},{7,24,25},{14,48,50},{21,72,75},{28,96,100},{9,40,41},{18,80,82},{11,60,61},{12,35,37},{24,70,74},{13,84,85},{16,63,65},{20,21,29},{40,42,58},{60,63,87},{28,45,53},{33,56,65},{36,77,85},{39,80,89},{48,55,73},{65,72,97}};
AC (2ms, 76KB)