作者bochengchen (LFII)
看板Grad-ProbAsk
标题[理工] 101交大资演
时间Sun Dec 1 14:34:43 2019
各位大大好，小弟有几个问题想问
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1575182085.A.E4F.html
2F：推 zuchang: 第三 这是prim’s algo 12/01 15:32
3F：推 zuchang: 啊 第一题还能再降 刚看答案是B 等其他人的方法 12/01 15:36
4F：→ zuchang: 啊 在一个node中找x 因为排序过 所以用二元搜寻 所以logm 12/01 15:38
5F：→ zuchang: 就可以 12/01 15:38
6F：推 mi981027: 第一题 从第一个node开始 每次都直接比最後一个值 12/01 15:56
7F：→ mi981027: 如果x比较大就到下个node 比较小就在当前node做bs 12/01 15:56
8F：→ mi981027: worst case会比2n/m个 12/01 15:56
9F：→ mi981027: 到最後一个node後 再做binary search 12/01 15:56
10F：→ mi981027: 总共是O(log(m/2)+2n/m) 12/01 15:56
这边没有想到要用binary search感谢mi大~
感谢gash大! 我来研究研究
13F：→ mi981027: 第二题的e是错的 这种表示法会是唯一的 这也说明了这个 12/01 17:59
14F：→ mi981027: 可以用greedy来解 先找出最大的a, 再找b, 再找c 12/01 17:59
这个证明好厉害阿! 在考试的时候遇到这种题目也来不及想出来了吧!!
※ 编辑: 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