作者zaq851017 (交大小V)
看板Grad-ProbAsk
標題[理工] 107交大資演對答案
時間Wed Jan 9 10:50:22 2019
如題搜尋版上好像沒有討論答案的文XD ，小弟就當第一個了。
不過錯誤率可能會有點高就是了，請見諒 :P
答案都更正過了。 感謝各位大大的提供。
https://imgur.com/5fnFTfl
<第一頁應該都沒什麼問題>
https://imgur.com/lNF6XXZ
https://imgur.com/xIvlpLO
https://imgur.com/b2lS4GW
https://imgur.com/DZgnr1n
應該只剩下最後一題了 求解QAQ
https://imgur.com/V8RKNFY
<第十題完全不會XD>
有問題歡迎討論。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.136.219
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1547002225.A.C03.html
1F：推 neutral9913: 第五題19 01/09 11:05
2F：→ neutral9913: 第六題7 01/09 11:05
3F：→ neutral9913: 紅黑樹那題我想問一下 他的數是不是沒有root的樹根紅 01/09 11:06
大大可以提供一下 5.6的過程嗎
4F：→ neutral9913: 點數目相同阿？ 01/09 11:06
5F：推 YOAOY: 紅黑樹寫錯了，路徑不會連續出現2紅吧 01/09 12:02
寫錯了感謝提醒
※ 編輯: zaq851017 (140.113.136.219), 01/09/2019 13:10:09
※ 編輯: zaq851017 (140.113.136.219), 01/09/2019 13:10:40
7F：推 z3588191: 第九題 我寫(a) A[i] - k (b) A[i] 01/09 13:37
8F：→ z3588191: 直覺是這樣 k取Array前i個最小的 ans就會是A[i] - k 中 01/09 13:38
大大兩題應該都沒錯！感謝 那第五第六你答案也是同上樓的嗎
9F：→ z3588191: 最大的 01/09 13:38
10F：→ z3588191: 第七題 時間應該是O(V^2logV + VE) 01/09 13:44
※ 編輯: zaq851017 (140.113.136.219), 01/09/2019 13:54:16
11F：→ z3588191: 摁摁 我也寫19跟7 01/09 14:04
13F：→ ing12339: 紅黑覺得是這樣 01/09 14:16
感謝大大我想說我一次訂正完再一次修改文章
※ 編輯: zaq851017 (140.113.136.220), 01/09/2019 14:18:21
※ 編輯: zaq851017 (140.113.136.219), 01/09/2019 14:52:33
14F：推 hsiehweiwei: 第8題我的過程都跟你一樣 不過想問那個min cut怎麼求 01/09 22:55
其實mincut不只一種 我隨便找的 總之找流出去的邊要流滿 逆向的要不能流 這樣就行了
※ 編輯: zaq851017 (140.113.136.218), 01/10/2019 10:51:23
15F：推 Aa841018: 請教一下第五題過程，想很久還是不知為何是19 01/15 07:26
16F：推 srenso: 請問一下，RB的2 和11不是應該是紅色的嗎？ 01/19 19:20
17F：→ zaq851017: 0.0? 你是用什麼方法我那個RB TREE應該沒錯了~ 01/20 09:01
18F：推 jack33319: 紅黑樹2 11應該是紅沒錯 01/26 05:08
19F：→ jack33319: 第二次插入9時不應該再回頭作 01/26 05:08
20F：→ jack33319: CC 01/26 05:08
21F：→ Leaving: 紅黑樹2 11紅+1 01/26 19:29
22F：→ Leaving: 用原文書的方法 01/26 19:29
23F：推 ab940917: 紅黑樹 2 11紅 + 我用程式跑也是紅的 01/26 23:22
24F：→ zaq851017: 恩恩是2 11 紅沒錯 不過我在想有人規定紅黑樹步驟一定 01/27 22:16
25F：→ zaq851017: 長怎樣ㄇ 因為我那個也沒違反規則XD.... 01/27 22:17
27F：→ RinHizakura: 第五題 foo1是兩兩交換 foo2是postorder的偶數項相 01/28 19:41
28F：→ RinHizakura: 加 01/28 19:41
30F：→ RinHizakura: 然後min-cut 應該不會不只一種吧！？應該是分成S可 01/28 20:12
31F：→ RinHizakura: 以到的跟不能到的兩堆 01/28 20:12