#4243: 真的是故意整人


davidhsu (David)

學校 : 不指定學校
編號 : 12295
來源 : [36.237.202.120]
最後登入時間 :
2020-12-23 11:36:28
d102. 一堆線段 | From: [114.27.212.4] | 發表日期 : 2010-09-15 16:05

67108512
第140個測試資料是26個1, 答案高達67108512個
單算這個測試資料,用JAVA跑要用8秒,
1~139個測試資料,用JAVA跑只用了27.2s,符合本題限製的30秒時間

出題的作者請看看你的題意:
「愛斯基摩人給了你一堆線段,他想要問這些線段能組合
出幾種多邊形呢?對了他說那些線段長度不會有重複的」

用「不會有重複的線段」的演算法,如何在2.8s內算出第140個測試資料「26個1」。

 
#4244: Re:真的是故意整人


davidhsu (David)

學校 : 不指定學校
編號 : 12295
來源 : [36.237.202.120]
最後登入時間 :
2020-12-23 11:36:28
d102. 一堆線段 | From: [111.242.132.41] | 發表日期 : 2010-09-15 17:00

第140個測試資料是26個1, 答案高達67108512個
單算這個測試資料,用JAVA跑要用8秒,
1~139個測試資料,用JAVA跑只用了27.2s,符合本題限製的30秒時間

出題的作者請看看你的題意:
「愛斯基摩人給了你一堆線段,他想要問這些線段能組合
出幾種多邊形呢?對了他說那些線段長度不會有重複的」

用「不會有重複的線段」的演算法,如何在2.8s內算出第140個測試資料「26個1」。


---------------------------------------

別說27.2s太長了
我將JAVA改成C++
1~139個測試資料,只用了7秒多
單算第140個測試資料,又要用6秒多,
永遠得到TLE(本題C++限10s,JAVA限30s)

 

 
#4264: Re:真的是故意整人


liouzhou_101 (王启圣)

學校 : 广西柳州高级中学
編號 : 3714
來源 : [126.108.190.144]
最後登入時間 :
2023-07-21 17:40:51
d102. 一堆線段 | From: [121.31.205.117] | 發表日期 : 2010-09-20 11:21

第140個測試資料是26個1, 答案高達67108512個
單算這個測試資料,用JAVA跑要用8秒,
1~139個測試資料,用JAVA跑只用了27.2s,符合本題限製的30秒時間

出題的作者請看看你的題意:
「愛斯基摩人給了你一堆線段,他想要問這些線段能組合
出幾種多邊形呢?對了他說那些線段長度不會有重複的」

用「不會有重複的線段」的演算法,如何在2.8s內算出第140個測試資料「26個1」。


---------------------------------------

別說27.2s太長了
我將JAVA改成C++
1~139個測試資料,只用了7秒多
單算第140個測試資料,又要用6秒多,
永遠得到TLE(本題C++限10s,JAVA限30s)

 



但是有人在10ms内AC这题的哟!

你应该考虑一下其他的算法吧...

//不一定是DFS,也许是DP之类的呢??

 
#4267: Re:真的是故意整人


davidhsu (David)

學校 : 不指定學校
編號 : 12295
來源 : [36.237.202.120]
最後登入時間 :
2020-12-23 11:36:28
d102. 一堆線段 | From: [114.27.214.169] | 發表日期 : 2010-09-21 10:33

第140個測試資料是26個1, 答案高達67108512個
單算這個測試資料,用JAVA跑要用8秒,
1~139個測試資料,用JAVA跑只用了27.2s,符合本題限製的30秒時間

出題的作者請看看你的題意:
「愛斯基摩人給了你一堆線段,他想要問這些線段能組合
出幾種多邊形呢?對了他說那些線段長度不會有重複的」

用「不會有重複的線段」的演算法,如何在2.8s內算出第140個測試資料「26個1」。


---------------------------------------

別說27.2s太長了
我將JAVA改成C++
1~139個測試資料,只用了7秒多
單算第140個測試資料,又要用6秒多,
永遠得到TLE(本題C++限10s,JAVA限30s)

 



但是有人在10ms内AC这题的哟!

你应该考虑一下其他的算法吧...

//不一定是DFS,也许是DP之类的呢??

但是有人在10ms内AC这题的哟!???


應是早期測資只有少數的資料吧!
我知道你也通過了,
可否將你早期的程式再貼一次,解看看!

 
#4269: Re:真的是故意整人


liouzhou_101 (王启圣)

學校 : 广西柳州高级中学
編號 : 3714
來源 : [126.108.190.144]
最後登入時間 :
2023-07-21 17:40:51
d102. 一堆線段 | From: [116.253.25.205] | 發表日期 : 2010-09-21 19:24

第140個測試資料是26個1, 答案高達67108512個
單算這個測試資料,用JAVA跑要用8秒,
1~139個測試資料,用JAVA跑只用了27.2s,符合本題限製的30秒時間

出題的作者請看看你的題意:
「愛斯基摩人給了你一堆線段,他想要問這些線段能組合
出幾種多邊形呢?對了他說那些線段長度不會有重複的」

用「不會有重複的線段」的演算法,如何在2.8s內算出第140個測試資料「26個1」。


---------------------------------------

別說27.2s太長了
我將JAVA改成C++
1~139個測試資料,只用了7秒多
單算第140個測試資料,又要用6秒多,
永遠得到TLE(本題C++限10s,JAVA限30s)

 



但是有人在10ms内AC这题的哟!

你应该考虑一下其他的算法吧...

//不一定是DFS,也许是DP之类的呢??

但是有人在10ms内AC这题的哟!???


應是早期測資只有少數的資料吧!
我知道你也通過了,
可否將你早期的程式再貼一次,解看看!

 

我再次贴了,发现这时的时间和我当时的一样,说明数据没有加强!

其实那些10msAC的是用DP解的——惭愧自己不会...

 
ZeroJudge Forum