作者查詢 / williamd4112

總覽項目：發文 | 留言 | 暱稱

作者 williamd4112 在 PTT [ Prob_Solve ] 看板的留言(推文), 共35則

限定看板：Prob_Solve

看板排序：

全部Prob_Solve35Transfer35NPTHS4Gossiping2<< 收起看板(4)

首頁

尾頁

[問題] 數列問題

[ Prob_Solve ]42 留言, 推噓總分: +13

作者: williamd4112 - 發表於 2015/01/31 17:44(11年前)

4^F→williamd4112: 阿...看到hint突然好想撞牆...根本就不用方陣來存阿01/31 22:24

5^F→williamd4112: 只要花O(n)時間跑一次prefix sum就好.............01/31 22:24

10^F→williamd4112: 從反向可以做到O(Q)？！如果可希望能提示更多...02/01 00:05

23^F→williamd4112: http://pastebin.com/mJmwVgeD 昨天也是想到用pq來02/01 14:52

24^F→williamd4112: 但當時沒有想到說維護k個數字就好xd02/01 14:52

25^F→williamd4112: 但這段code還是re了...看來還得花一段時間來debug..02/01 14:53

27^F→williamd4112: 上面這段是因為用priority_queue跑RE...想說換個類02/01 16:34

28^F→williamd4112: 換成heap來做不知道會不會正確,結果還是re...02/01 16:34

29^F→williamd4112: 看了好久沒看出哪裡可能RE說...02/01 16:35

30^F→williamd4112: AC了,原來記憶體很吃緊,不能用long long02/01 17:08

31^F→williamd4112: 而seq[n]也是多開的空間,然後sums[n]應該改成sums[q02/01 17:08

32^F→williamd4112: 不過看Rank有人可以做到0.001 ...02/01 17:11

33^F→williamd4112: 我目前只能做到0.444...02/01 17:11

38^F→williamd4112: seq[n]那個寫法我記得以前上課時也是被告誡過...02/01 21:38

39^F→williamd4112: 不過後來compiler都會過就沒再去想了,我查看看02/01 21:39

[問題] HappyStorm's Sock Sucks

[ Prob_Solve ]48 留言, 推噓總分: +4

作者: williamd4112 - 發表於 2015/01/28 21:44(11年前)

6^F→williamd4112: 會變成nlogn是因為我在處理輸入資料時多了一個map查01/28 22:02

7^F→williamd4112: 查詢的動作嗎？01/28 22:02

8^F→williamd4112: 阿...不好意思,問了廢話...01/28 22:06

9^F→williamd4112: 改成先把所有可能的name以及一個sizeMap放入map01/28 22:34

10^F→williamd4112: 再讀取輸入時直接sockMap[name][size]++去遞增次數01/28 22:34

11^F→williamd4112: 最後traverse map一次輸出.依然TLE...QQ01/28 22:35

13^F→williamd4112: 謝謝提示！目前用陣列四維陣列儲存次數已經不會TLE01/28 23:05

16^F→williamd4112: ？！樓上可以再說得更詳細點嗎01/29 00:34

18^F→williamd4112: http://pastebin.com/UTiBZPV5 目前的code01/29 01:18

19^F→williamd4112: 想請問這樣再處理輸入時應該是O(1)了？(直接隨機存01/29 01:19

20^F→williamd4112: 取到紀錄次數的位置(ps:剛剛看到RE,以為已經沒tle..01/29 01:20

39^F→williamd4112: @hinet60613:阿...我誤解題意(以為成對就fine...01/29 16:42

40^F→williamd4112: 可是如果要紀錄未成對的襪子,又必須在o(1)的複雜度01/29 16:44

41^F→williamd4112: 找到尚未成對的襪子然後移出01/29 16:45

42^F→williamd4112: 那應該用什麼結構來儲存比較好呢？01/29 16:45

43^F→williamd4112: 之前我是把name的3個字母對a的offse以及size當作索01/29 16:47

44^F→williamd4112: 引,不過,這樣再輸出時又需要全部遍歷一次(雖然次數01/29 16:48

45^F→williamd4112: 不算太大(26*26*26*5), 但還是跑了TLE...01/29 16:48

47^F→williamd4112: 感謝各位,剛剛發現問題了...我把output修正過後就ac01/30 01:21

48^F→williamd4112: 了,原來,跑錯的output也有可能跑到TLE QQ01/30 01:22

首頁

尾頁