[理工] 101交大資演

[bochengchen (LFII)]

各位大大好，小弟有幾個問題想問
1.
https://imgur.com/kXTsauq.jpg
第13題的B跟C 要怎麼選呢? 為甚麼會是logm呢?

2.
https://imgur.com/k3kgqYc.jpg
第51題 這個binomial coefficient represent integral的特性是什麼呢?

3.
https://imgur.com/bkw2Tht.jpg
第54題的time complexity該怎麼算呢?

麻煩各位大大了!

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.39.113.93 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1575182085.A.E4F.html
推 zuchang: 第一題 https://i.imgur.com/yDytnto.jpg
推 zuchang: 第三 這是prim’s algo
推 zuchang: 啊 第一題還能再降 剛看答案是B 等其他人的方法
→ zuchang: 啊 在一個node中找x 因為排序過 所以用二元搜尋 所以logm
→ zuchang:  就可以
推 mi981027: 第一題 從第一個node開始 每次都直接比最後一個值
→ mi981027: 如果x比較大就到下個node 比較小就在當前node做bs
→ mi981027: worst case會比2n/m個
→ mi981027: 到最後一個node後 再做binary search
→ mi981027: 總共是O(log(m/2)+2n/m)
這邊沒有想到要用binary search感謝mi大~


推 gash55025502:  https://i.imgur.com/HJF5xix.jpg
感謝gash大! 我來研究研究


推 mi981027: https://i.imgur.com/RNjDb2I.jpg
→ mi981027: 第二題的e是錯的 這種表示法會是唯一的 這也說明了這個
→ mi981027: 可以用greedy來解 先找出最大的a, 再找b, 再找c
這個證明好厲害阿! 在考試的時候遇到這種題目也來不及想出來了吧!!


※ 編輯: bochengchen (114.39.113.93 臺灣), 12/02/2019 01:34:16
※ 編輯: bochengchen (114.39.113.93 臺灣), 12/02/2019 01:34:43
※ 編輯: bochengchen (114.39.113.93 臺灣), 12/02/2019 01:36:51
※ 編輯: bochengchen (114.39.113.93 臺灣), 12/02/2019 01:51:41