PTT數位生活區 / C_and_CPP (C/C++)

[ACM ] 386

看板C_and_CPP (C/C++)作者 (wnuiayldh)時間16年前 (2009/07/01 16:02), 編輯推噓6(6推 0噓 20→)
留言26則, 4人參與, 最新討論串1/1
http://uva.onlinejudge.org/external/3/386.html 方程式：a^3 = b^3 + c^3 + d^3 a<= 200 ,（a,b,c,d均大於1） 語言：c 用暴力法寫四個迴圈去跑 code: http://nopaste.info/a97770cc90.html 時間：0.140 先把次方算完放在array 時間：0.100 請問有辦法讓他跑快一點嗎？ 要用什麼資料結構或演算法？ 可以給個方向嗎 ＠ ＠？ ------------------------------------------------- 如果要建表用bsearch 是用structure存 b,c,d ? for(j=2; j<200; j++){ for(k=j; k<200; k++){ for(l=k; l<200; l++){ } } } 這樣要1313410項？＝＝？ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 122.122.32.152
推
07/01 16:09, , 1F
比如說 binary search
07/01 16:09, 1F
→
07/01 16:10, , 2F
不用每次都真的去乘, 一開始先乘好放在 array 裡
07/01 16:10, 2F
推
07/01 16:12, , 3F
還有一些數論的加速, 如果 (a,b,c,d)=1, 那麼 a 是偶數
07/01 16:12, 3F
→
07/01 16:12, , 4F
b, c, d 只有一個會是偶數
07/01 16:12, 4F
→
07/01 16:13, , 5F
a 是奇數, b,c,d 就只會有一個是奇數
07/01 16:13, 5F
→
07/01 16:15, , 6F
是說 sample output 怎麼沒有 9^3 = 1^3 + 6^3 + 8^3 ?
07/01 16:15, 6F
→
07/01 16:15, , 7F
是我弄錯意思了嗎? 囧
07/01 16:15, 7F
→
07/01 16:16, , 8F
啊, a, b, c, d > 1, 沒注意到 ...
07/01 16:16, 8F
→
07/01 16:18, , 9F
XD 我應該先把條件打出來 sorry= =|||
07/01 16:18, 9F
→
07/01 16:23, , 10F
來試看看先寫在array的方法！！ 謝啦～
07/01 16:23, 10F
→
07/01 16:25, , 11F
在論壇有看到說用hash table會比較快！是說先乘好在用
07/01 16:25, 11F
→
07/01 16:26, , 12F
hash table 搜尋嗎？？
07/01 16:26, 12F
推
07/01 16:30, , 13F
對, 算是 binary search 的進階吧 key 是 a^3, value 是 a
07/01 16:30, 13F
→
07/01 16:30, , 14F
啊, 怕你誤會, 他們的意思是先算出 b^3+c^3+d^3 再看這個
07/01 16:30, 14F
→
07/01 16:31, , 15F
值有沒有出現在立方數的 hash table (預先建好) 裡
07/01 16:31, 15F
推
07/01 17:24, , 16F
這題還想過一些DP加速的方式
07/01 17:24, 16F
→
07/01 17:25, , 17F
A^3=B^3+C^3+D^3 => (xA)^3=(xB)^3+(xC)^3+(xD)^3
07/01 17:25, 17F
→
07/01 17:25, , 18F
Table[A]=Table[2A]=...=Table[xA]
07/01 17:25, 18F
→
07/01 17:27, , 19F
但會讓順序難以決定變得挺麻煩的所以作罷~
07/01 17:27, 19F
※ 編輯: deepking 來自: 122.122.32.152 (07/01 17:57)
→
07/01 18:01, , 20F
修正一下 Table[xA]=x*Table[A] 好久以前的記憶了
07/01 18:01, 20F
推
07/01 18:31, , 21F
bsearch 那個存 1^3 ~ 200^3 只要存 200 項就好
07/01 18:31, 21F
→
07/01 18:33, , 22F
要再快的話把 a^3 - b^3 建 hash , 用 c^3+d^3 查
07/01 18:33, 22F
推
07/01 18:43, , 23F
用兩個陣列存 a^3 - b^3, b^3 + d^3
07/01 18:43, 23F
→
07/01 18:43, , 24F
分別排序之後找相同的元素..
07/01 18:43, 24F
→
07/01 19:04, , 25F
瞭解...搞亂掉了XD
07/01 19:04, 25F
→
07/01 19:56, , 26F
還沒學過演算法XD，DP是DynamicProgramming嗎？
07/01 19:56, 26F
‣ 更多 deepking 的文章
文章代碼(AID): #1AInWR4- (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 deepking 的文章
文章代碼(AID): #1AInWR4- (C_and_CPP)