發表新討論
#9172: [JAVA] 執行逾時，時間是不是太緊湊?


highcollege90027 (冰人雪糕)

學校 : 不指定學校
編號 : 41648
來源 : [218.161.27.179]
最後登入時間 ：
2021-10-20 18:15:36
d712. The 3n + 1 problem -- ms0472904 | From: [1.171.11.146] | 發表日期 : 2014-09-11 12:28
第 1 測資點(0%): TLE (6s) 
執行逾時
Killed
第 2 測資點(1%): AC (0.2s, 1.8MB) 
通過檢測
請問這題應該要用到何種演算法才行得通?
 
#9177: Re:[JAVA] 執行逾時，時間是不是太緊湊?


gtyuse (gtyuse)

學校 : 國立科學工業園區實驗高級中學
編號 : 37104
來源 : [140.112.215.56]
最後登入時間 ：
2021-02-18 08:23:14
d712. The 3n + 1 problem -- ms0472904 | From: [123.110.232.18] | 發表日期 : 2014-09-13 09:49
1. 一開始先建表
由小到大把每個數字的 cycle 存下來
這樣在找比較大的時候當它變回已找過的數字時
就不用重新計算, 超快 der
 
2. 因為要找區間最大值
所以本題卡掉 O(n) 基本作法
只好用線段樹 (或是演算法筆記裡的 "Fake" Segment Tree )
演算法筆記用陣列實作, 我是用 node 指標
我覺得陣列可能比較快 (y)
 
#9178: Re:[JAVA] 執行逾時，時間是不是太緊湊?


gtyuse (gtyuse)

學校 : 國立科學工業園區實驗高級中學
編號 : 37104
來源 : [140.112.215.56]
最後登入時間 ：
2021-02-18 08:23:14
d712. The 3n + 1 problem -- ms0472904 | From: [123.110.232.18] | 發表日期 : 2014-09-13 09:49
1. 一開始先建表
由小到大把每個數字的 cycle 存下來
這樣在找比較大的時候當它變回已找過的數字時
就不用重新計算, 超快 der
 
2. 因為要找區間最大值
所以本題卡掉 O(n) 基本作法
只好用線段樹 (或是演算法筆記裡的 "Fake" Segment Tree )
演算法筆記用陣列實作, 我是用 node 指標
我覺得陣列可能比較快 (y)
 
#9179: Re:[JAVA] 執行逾時，時間是不是太緊湊?


gtyuse (gtyuse)

學校 : 國立科學工業園區實驗高級中學
編號 : 37104
來源 : [140.112.215.56]
最後登入時間 ：
2021-02-18 08:23:14
d712. The 3n + 1 problem -- ms0472904 | From: [123.110.232.18] | 發表日期 : 2014-09-13 09:50
傳到兩次惹抱歉 /(_ _)\ 
#9180: Re:[JAVA] 執行逾時，時間是不是太緊湊?


gtyuse (gtyuse)

學校 : 國立科學工業園區實驗高級中學
編號 : 37104
來源 : [140.112.215.56]
最後登入時間 ：
2021-02-18 08:23:14
d712. The 3n + 1 problem -- ms0472904 | From: [123.110.232.18] | 發表日期 : 2014-09-13 09:52

喔對如果你也是這樣寫的話

我想就是 JAVA 的問題了 

 
#9184: Re:[JAVA] 執行逾時，時間是不是太緊湊?


highcollege90027 (冰人雪糕)

學校 : 不指定學校
編號 : 41648
來源 : [218.161.27.179]
最後登入時間 ：
2021-10-20 18:15:36
d712. The 3n + 1 problem -- ms0472904 | From: [1.171.11.146] | 發表日期 : 2014-09-13 22:05

喔對如果你也是這樣寫的話

我想就是 JAVA 的問題了 


還是不太行，可能是我自己演算法太慢，先不怪JAVA，

 

雖然他的確慢了點，但我想還是有方法解決，

謝謝指教，我再嘗試看看 

 
#9564: Re:[JAVA] 執行逾時，時間是不是太緊湊?


z3x56 (二信阿資)

學校 : 基隆市私立二信高級中學
編號 : 41061
來源 : [61.231.128.29]
最後登入時間 ：
2020-08-22 18:35:15
d712. The 3n + 1 problem -- ms0472904 | From: [49.159.137.154] | 發表日期 : 2014-12-25 23:28

喔對如果你也是這樣寫的話

我想就是 JAVA 的問題了 


還是不太行，可能是我自己演算法太慢，先不怪JAVA，

 

雖然他的確慢了點，但我想還是有方法解決，

謝謝指教，我再嘗試看看 

 


應該提示：區間最大值

 

若只有一組資料1 1000000 大約0.3s可以解決
我將計算過的存起來查，若數十筆應可以，

但最後仍是TLE，所以有很大的可能是要測 「求區間最大值」

 

 
ZeroJudge Forum