作者查詢 / dreamoon

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

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

限定看板：Prob_Solve

首頁

尾頁

Re: [問題] 主席樹？

[ Prob_Solve ]16 留言, 推噓總分: +7

作者: DJWS - 發表於 2015/02/05 13:46(11年前)

2^F推dreamoon: 總覺得這種食後要貼出那個Let me google that for you..02/05 16:13

Re: [討論] UVa12615

[ Prob_Solve ]8 留言, 推噓總分: +3

作者: DJWS - 發表於 2015/01/15 22:54(11年前)

2^F→dreamoon: 若把邊當點，大概可以應轉成一般圖的最大獨立集01/15 19:53

4^F→dreamoon: 若把邊當點，大概可以應轉成一般圖的最大獨立集

5^F推dreamoon: 不過這題顯然就是特殊圖01/15 23:22

6^F推dreamoon: 我喜歡FRAXIS所說的用tree decomposition去思考它01/15 23:24

7^F→dreamoon: 這樣去思考感覺上比較有系統01/15 23:24

11^F推dreamoon: 線性是把tree-width當常數?若是這樣應該就和我的方法01/15 23:55

12^F→dreamoon: 差不多01/15 23:55

[討論] UVa12615

[ Prob_Solve ]21 留言, 推噓總分: +8

作者: dreamoon - 發表於 2015/01/15 03:37(11年前)

6^F→dreamoon: ICPC台灣參賽者交流社根本沒人在討論題目...01/15 19:49

7^F→dreamoon: 資訊競賽選手新手村到是第一次看到01/15 19:50

8^F→dreamoon: 若把邊當點，大概可以應轉成一般圖的最大獨立集01/15 19:53

9^F→dreamoon: 而且每條邊至多和六條邊相鄰01/15 19:54

10^F→dreamoon: 這樣才真的有用到題目條件01/15 19:54

11^F→dreamoon: 新手村的成員都太年輕了0.001/15 19:55

15^F→dreamoon: 抱歉說錯名詞01/15 22:21

16^F→dreamoon: 查了一下什麼是tree decomposition,看來我的做法確實01/15 22:40

17^F→dreamoon: 是這個東西01/15 22:40

18^F→dreamoon: 一般圖最小支配集能做嘛?01/15 22:41

Re: [問題] Reduce LP成Min-cost flow

[ Prob_Solve ]2 留言, 推噓總分: +1

作者: FRAXIS - 發表於 2015/01/13 21:48(11年前)

1^F推dreamoon: 我想應該沒有整數的限制01/14 07:07

2^F→dreamoon: 一般的flow問題時數也可以作01/14 07:08

Re: [問題] Reduce LP成Min-cost flow

[ Prob_Solve ]8 留言, 推噓總分: +5

作者: bleed1979 - 發表於 2015/01/13 00:39(11年前)

6^F推dreamoon: 真是巧妙的題目...01/13 13:43

7^F→dreamoon: 有上下界的最小花費網路流01/13 13:44

8^F推dreamoon: 是說我可不覺得任何LP都可以換成min-cost flow @@01/13 13:47

[問題] Missing Numbers

[ Prob_Solve ]31 留言, 推噓總分: +3

作者: FRAXIS - 發表於 2014/11/10 00:09(11年前)

1^F推dreamoon: k=2時，如何"很容易"的用xor的技巧找出答案?11/10 03:51

2^F→dreamoon: http://codepad.org/LRPxss3911/10 04:50

3^F→dreamoon: 寫了一個空間複雜度O(k)的O(log n)-pass的方法11/10 04:51

4^F→dreamoon: 也是多項式時間11/10 04:52

5^F→dreamoon: 不知道符不符合你的需求@@?11/10 04:53

6^F→dreamoon: http://codepad.org/JE2jYW8011/10 06:17

10^F→dreamoon: 最多都是O(K)11/11 08:50

11^F→dreamoon: 這方法某種程度和你下篇的方法很像11/11 08:50

12^F→dreamoon: 就是一剛開始先把所有在A裡第一個bit是0或是1兩類11/11 08:51

13^F→dreamoon: 若其中一類的個數恰少一個，我們就可以用該類的所有數的11/11 08:52

14^F→dreamoon: xor值來得知少的是哪個11/11 08:53

15^F→dreamoon: 若該類少了至少兩個數11/11 08:54

16^F→dreamoon: 例如說，第一個bit是0的那類少了至少兩個數11/11 08:54

17^F→dreamoon: 我們就在下一次pass時把它變成前兩個bit是00和10兩類11/11 08:55

18^F→dreamoon: 然後一直做下去11/11 08:55

19^F→dreamoon: 用同樣的方法到最後就可以把所有少的數找出來11/11 08:56

20^F→dreamoon: 只是這個方法要pass log n次11/11 08:56

21^F→dreamoon: 過程中我們可以確定同一類裡分出來的兩類裡一定至少少了11/11 08:57

22^F→dreamoon: 兩個數,所以在每個iteration中分類的類別總數一定<=K11/11 08:58

28^F推dreamoon: 你只要枚舉1~n代進去看哪些數使得f(x)=0就行了11/19 19:53

Re: [問題] 給定n個排好序的整數陣列找中位數

[ Prob_Solve ]12 留言, 推噓總分: +8

作者: chz - 發表於 2014/10/15 18:31(11年前)

2^F推dreamoon: 我猜若只需求O(n log n log n)的話10/15 20:48

3^F→dreamoon: 甚至可以直接random取一個數代替MoM就行了10/15 20:49

Re: [問題] 給定n個排好序的整數陣列找中位數

[ Prob_Solve ]26 留言, 推噓總分: +9

作者: FRAXIS - 發表於 2014/10/14 20:08(11年前)

1^F推dreamoon: 並無法保證max_i或是min_i列至少有一列可以刪掉一半吧?10/14 22:56

2^F→dreamoon: (在不知道min和max實際上是全部的數第幾大的情況下)10/14 22:56

4^F推dreamoon: 那你怎麼知道min小於median?10/15 01:11

6^F推dreamoon: 我好像想懂了，不過你說的少於一半的元素應該還不夠輕楚10/15 01:52

7^F→dreamoon: 因為雖然一剛開始是求中位數,但過程中會變得不一定是在10/15 01:53

8^F→dreamoon: 求中位數10/15 01:54

10^F推dreamoon: 這不太對吧...?max_i和min_i可能包含不同數目的數?10/15 02:37

12^F推dreamoon: 這樣的話複雜度還會是O(n lg^2 n)嘛?10/15 02:50

14^F推dreamoon: 似乎會耶!10/15 02:53

16^F→dreamoon: 恩恩，這樣的話就比我原本想的容易實做了10/15 02:54

19^F推dreamoon: 我認為只要改程max_i和min_i一律減半,並重新計算10/15 03:05

20^F→dreamoon: 下一個round要求的是第幾大的數,就可以計算任意第k大了10/15 03:06

21^F推dreamoon: 若是求中位數的話,當某列只剩一個數且又被選到10/15 03:09

22^F→dreamoon: 應該是可以直接丟掉10/15 03:09

[問題] 演算法問題

[ Prob_Solve ]21 留言, 推噓總分: +14

作者: cutekid - 發表於 2014/08/01 16:48(11年前)

6^F推dreamoon:http://ppt.cc/DEO108/01 18:56

7^F推dreamoon:這是相關文章，搜尋逆序數對+樹狀數組應該可以搜到很多08/01 18:59

8^F→dreamoon:東西08/01 18:59

Re: [問題] ICPC 5713 疑似MST的問題

[ Prob_Solve ]2 留言, 推噓總分: +1

作者: DJWS - 發表於 2014/04/24 22:45(11年前)

1^F推dreamoon:http://www.csie.ntnu.edu.tw/~u91029/SpanningTree.html04/25 00:57

2^F→dreamoon:幫原PO附上second-best minimum spanning tree的連結04/25 00:58

首頁

尾頁