作者查詢 / mathtsai

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

作者 mathtsai 在 PTT [ Grad-ProbAsk ] 看板的留言(推文), 共328則

限定看板：Grad-ProbAsk

看板排序：

首頁

尾頁

[理工] 109 台大電機丙資演 fibonacci heap

[ Grad-ProbAsk ]3 留言, 推噓總分: +2

作者: waes81224 - 發表於 2021/01/25 20:30(4年前)

3^F推mathtsai: 單一: worst case 多次操作: amortized01/25 22:13

106 台聯大離散遞迴

[ Grad-ProbAsk ]23 留言, 推噓總分: +3

作者: x3767x - 發表於 2021/01/22 22:34(4年前)

4^F→mathtsai: 原來能這樣解謝謝樓上01/23 00:08

6^F→mathtsai: 想請問第二題怎麼解？ Substitution Method？01/23 00:25

9^F→mathtsai: 猜他 < cn-b 然後用substitution method證明吧01/23 06:04

12^F→mathtsai: 想請問畫出來答案是多少？01/23 14:01

13^F→mathtsai: 我是算O(n)01/23 14:53

16^F→mathtsai: 感謝不錯第二行為什麼不是 n/20 和 n/4 ？01/23 15:17

17^F→mathtsai: *不過*01/23 15:17

18^F→mathtsai: 是我看錯題目嗎QQ01/23 15:18

23^F→mathtsai: 我也是畫7/20跟1/401/23 18:47

[理工] 109交大資演

[ Grad-ProbAsk ]20 留言, 推噓總分: +7

作者: lucy35 - 發表於 2021/01/16 00:29(4年前)

1^F→mathtsai: 25.按照題目給的條件簡單不等式就能寫01/16 01:32

2^F→mathtsai: 26.根據題目給的定義01/16 01:33

3^F→mathtsai: prefix_sum[i] is at most s 所以遞迴選C01/16 01:34

4^F→mathtsai: D應該是 D(n, min(6an,sum of A))01/16 01:35

5^F→mathtsai: E 表格大小決定dp複雜度表格大小最多n*6an01/16 01:36

6^F→mathtsai: 我記得這題好像前面也有，可以找找01/16 01:40

7^F→mathtsai: 24.是說順序不能變暴力找應該都是5個01/16 01:44

8^F→mathtsai: D 應該是 D(n,sum of A)01/16 01:49

9^F→mathtsai: E 我要再想想不太清楚為啥不是表格大小01/16 01:52

19^F→mathtsai: 看題目不用連號01/16 21:39

[理工] 計系交大 109 (5)(8)(26)

[ Grad-ProbAsk ]22 留言, 推噓總分: +7

作者: try66889 - 發表於 2021/01/14 09:37(4年前)

1^F→mathtsai: 26.code應該被放在text的部分吧?01/14 10:13

16^F→mathtsai: 原來26是這個意思01/14 14:22

[理工] 109中央演算法

[ Grad-ProbAsk ]10 留言, 推噓總分: +4

作者: seafoodccu - 發表於 2021/01/09 15:37(4年前)

1^F推mathtsai: 第一次看到會不知道怎麼下筆但是看C就知道是dp01/09 19:26

2^F→mathtsai: https://reurl.cc/E2KGk0 提供dp參考01/09 19:28

3^F→mathtsai: 這個問題叫做subset sum problem是NP-complete問題01/09 19:29

4^F→mathtsai: 至於b 你需要找到一個NP-complete可以reduce成這個問題01/09 19:30

[理工] 109清大計科

[ Grad-ProbAsk ]73 留言, 推噓總分: +11

作者: seafoodccu - 發表於 2021/01/04 20:05(4年前)

1^F→mathtsai: b-ii 畫個等腰三角形邊長2,2,101/04 21:23

2^F→mathtsai: 9.很經典新增一個元素 sum/201/04 21:27

3^F→mathtsai: 就可以從2-partition reduce成 3-partition01/04 21:27

4^F→mathtsai: 12.應該只要能構造就好01/04 21:32

6^F→mathtsai: https://reurl.cc/e80A07 參考01/05 00:38

56^F→mathtsai: 欸欸所以我b-ii的例子也是錯的嗎QQ?01/07 17:53

57^F→mathtsai: 結果隨便舉個例子都錯看來要想清楚一點QQ01/07 17:55

58^F→mathtsai: 會不會其實這題根本沒反例啊XD01/07 17:55

59^F推mathtsai: 考慮三個點a,b,c d(a,b) = L (最長的shortest path)01/07 23:05

60^F→mathtsai: https://imgur.com/UqlK6C4 這樣有符合b-ii嗎01/07 23:11

61^F→mathtsai: 自答不符合01/07 23:35

62^F推mathtsai: https://imgur.com/xasTue5 上面的edge都是最短路徑01/07 23:47

63^F→mathtsai: a,b是absolute center ， d1+d2 < max01/07 23:48

64^F→mathtsai: 假設有一點p在edge上，並且p也是absolute center01/07 23:54

65^F→mathtsai: p必須在ab的最短路徑上(簡單證明)01/07 23:55

66^F→mathtsai: 令d(a,p) = max-d1，則d(b,p) = d101/07 23:57

67^F推mathtsai: 根據定義 d(c,p) = max01/07 23:59

68^F→mathtsai: 但是根據上面所述 d(c,p) = min(max, d1+d2) = d1+d201/08 00:00

69^F→mathtsai: 抱歉我寫錯了我等等重回01/08 00:01

70^F→mathtsai: 我放棄感覺有啥地方卡住了應該可以從上面的方向去思考01/08 00:46

[理工] 資演交大108 (10)(13)

[ Grad-ProbAsk ]12 留言, 推噓總分: +1

作者: try66889 - 發表於 2021/01/06 19:52(4年前)

7^F→mathtsai: 10-2 選中間1/301/06 20:50

[理工] 108 交大資工計系第二題

[ Grad-ProbAsk ]13 留言, 推噓總分: +1

作者: ChouEita - 發表於 2021/01/02 21:29(4年前)

2^F→mathtsai: time sharing 可以 preemtive01/02 21:48

3^F→mathtsai: 抱歉沒看清楚我覺得原po說得有道理還請其他人解惑01/02 23:02

13^F→mathtsai: 了解感謝!01/03 16:55

[理工] 109 交大資工 8、9、12、14

[ Grad-ProbAsk ]6 留言, 推噓總分: 0

作者: liljimmy - 發表於 2021/01/02 03:46(4年前)

1^F→mathtsai: 23.b 快速冪回答B是dp A是快速冪01/02 10:35

2^F→mathtsai: 26.C 根據定義前i-1個的sum必須小於等於6ai01/02 10:43

3^F→mathtsai: 31 p1是s,p2是t 這樣就能看成flow問題01/02 11:24

4^F→mathtsai: 最後一題我怎麼看全部選項都錯求解釋QQ01/02 11:39

5^F→mathtsai: 最後一題 successor是指BST中的下一個元素01/02 19:28

6^F→mathtsai: 所以他的找法y一定是successor 我誤以為是指child了QQ01/02 19:28

[理工] 107年交大資聯計系 20 與題組D

[ Grad-ProbAsk ]16 留言, 推噓總分: +3

作者: uuxx66 - 發表於 2020/12/31 00:15(5年前)

1^F→mathtsai: 20 (a)belady's anamoly12/31 00:31

2^F→mathtsai: d是想問什麼？英文問題嗎？12/31 00:35

首頁

尾頁