作者painechaos (老赵)
看板Grad-ProbAsk
标题[理工] 106交大资演 对答案与讨论
时间Wed Jan 17 17:43:56 2018
版上有关106交大的文章蛮少的@@ 所以直接po上来跪求指教
http://i.imgur.com/3z5eu4h.jpg
http://i.imgur.com/WAvH7QW.jpg
http://i.imgur.com/bDgqZqI.jpg
http://i.imgur.com/TYegNa1.jpg
http://i.imgur.com/srd34BN.jpg
http://i.imgur.com/9pREQuJ.jpg
http://i.imgur.com/x4OG9cT.jpg
http://i.imgur.com/LO7lcCj.jpg
http://i.imgur.com/DSPXwXH.jpg
http://i.imgur.com/ysnD99S.jpg
比较有疑惑的是第1、3、11、15题
1.一开始我是用课本定义的pi去做再转换为p，做完後看了题目的定义跟印象中的不太相同，爬文後发现定义有改，但用题目的定义去操作还是怪怪的
3.看完程式码，我的想法是第一轮q=n1开始往後比较，n1的value=8可以被2整除且後面的value皆小於8，所以一直swap直到8跑到n4;第二轮q从n2比较，最後得到3 2 7 8 ，这样的想法正确吗？
10.这题我自认在考场时也不会写，所以直接放弃...
11.第一眼看到"greedy"和"2-way tree"，脑海中浮现的想法是Huffman algo，但看到optimal merge tree就不懂要的是怎样子的tree
15.看到spanning tree就想到Krustal's algo和Prim algo，之後决定采用Krustal，接着令red edge weight=0,blue edge weight =1的想法下去做，请问这样子可行吗？
希望大家不吝指教@@
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.27.240.137
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1516182239.A.CEF.html
1F：→ aggress5566: 1应该就很平常的KMP吧？ 01/17 18:03
2F：→ aggress5566: 10 应该是randomized algorithm 我也还没看QQ 01/17 18:03
3F：→ aggress5566: 11应该是output整颗Tree 01/17 18:03
4F：→ aggress5566: 15用greedy应该没问题 01/17 18:03
5F：推 a1596482: 1. 条件式还有一个Pi+1=/=Pj+1，应该只剩f(6)=3，其他 01/17 18:50
6F：→ a1596482: 为-1 01/17 18:50
7F：推 a1596482: 9. 是不是只有extract-min是logn ，其他都是1？ 01/17 18:52
8F：→ aggress5566: 那不是本来就是定义吗 囧 01/17 19:03
9F：推 howard31622: 第十题我看了是哭笑不得 01/17 19:53
10F：→ howard31622: 乾...我没有被很熟那段 01/17 19:53
11F：→ howard31622: 不过这题真的是送分题 01/17 19:53
12F：→ howard31622: 你没有把洪逸的讲义看熟喔 01/17 19:53
13F：→ howard31622: 虽然多希望考这种 01/17 19:53
14F：→ howard31622: 因为我不用担心我选择题写不完 01/17 19:53
15F：→ howard31622: 而且这个分数一定拿得到不少 01/17 19:53
16F：→ howard31622: 还有第九题你写错了 01/17 19:54
17F：→ howard31622: 那个笔记有 01/17 19:54
18F：推 FRAXIS: 15题应该可以在 O(|E|)时间内解 01/17 20:52
19F：→ aggress5566: 其实应该是看熟才知道不能用他笔记上的证吧XD 01/17 21:17
20F：推 winiel559: 15不需要sort，一个个检查颜色正不正确就好了 01/17 21:37
21F：→ painechaos: 回agg大:我是後来对答案时发现有讨论这题，对於f(i)=t 01/18 00:02
22F：→ painechaos: he largest i<j 这段的意思有点难以理解 01/18 00:02
23F：→ painechaos: 请问第11题你会怎麽写呢，有点摸不着头绪该如何下笔 01/18 00:02
24F：→ painechaos: 第15这样分析还ok罗? 01/18 00:02
25F：→ painechaos: a大:请问对於f(i)=the largest i<j...这段的你是如何 01/18 00:12
26F：→ painechaos: 解读的? 01/18 00:12
29F：→ painechaos: 刚刚发现union写错了,extract-min我要再找找，谢谢你 01/18 00:12
30F：→ painechaos: 的提点 01/18 00:12
31F：→ painechaos: h大:这题我只有看个印象，没有认真去背它@@ 01/18 00:21
32F：→ painechaos: 刚刚找了一下，应该是这个推导 01/18 00:21
35F：→ painechaos: 那时候看完觉得实在没把握在时间紧迫的情况下写出来， 01/18 00:21
36F：→ painechaos: 所以就投注心力在其他基本题上了xD 01/18 00:21
37F：→ painechaos: F大 w大:谢谢你们，我再思考看看如何表达 01/18 00:24
38F：→ aggress5566: 你说failure function吗 我就用KMP下去做而已 01/18 00:33
39F：→ aggress5566: 然後你贴的笔记 Hmm 我觉得出题教授应该是看了这个 01/18 00:34
40F：→ aggress5566: 出了这题 XD 01/18 00:34
41F：推 winiel559: 想了一下15好像还是要sort 01/18 08:47
42F：→ a1596482: 1. 我觉得应该是f(j)才对 01/18 08:58
43F：推 yaya517: quick sort avg. prove跟你一样..看到觉得不会 翻笔记看 01/18 09:12
44F：→ yaya517: 到一样的东西 觉得自己考试时应该还是写不出来XD 01/18 09:12
45F：推 FRAXIS: 15 就算要排序 因为只有两种类型 counting sort 就可以了 01/18 11:26
46F：推 sarsman: 1我也觉得定义应该是f(j)，i都是input了找什麽largest啦X 01/18 14:58
47F：→ sarsman: D 01/18 14:58
48F：推 sarsman: 11，将m个sorted list建成m个只有一颗node的tree，定义no 01/18 16:00
49F：→ sarsman: de weight为element个数 01/18 16:00
50F：推 sarsman: 挑两个weight最小的tree（令为T1、T2）；再新增一个一颗n 01/18 16:05
51F：→ sarsman: ode的tree （令为T），将T1、T2接在T的左右子树 01/18 16:05
52F：→ sarsman: T的root weight为T1跟T2的weight sum，重复到剩下一棵tre 01/18 16:07
53F：→ sarsman: e就是输出 01/18 16:08
54F：→ painechaos: agg大:如果因为这样多拿了点分数，那真是赚到了xD 01/18 17:54
55F：→ painechaos: y大:我觉得还是稳稳地把握其他基本分比较实在，这题就 01/18 17:54
56F：→ painechaos: 给高手得分吧QQ 01/18 17:54
57F：→ painechaos: w大、F大:演算法设计的部分我比较不熟要再多思考，先 01/18 17:56
58F：→ painechaos: 谢谢指教 01/18 17:56
59F：→ painechaos: 谢谢s大的第11题，我了解node该怎麽定义了! 这是Huffm 01/18 18:00
60F：→ painechaos: an的应用吧？ 01/18 18:00
61F：推 leoone: 15题就先排序 把set依序由小排到大在 两两做merge 01/19 20:49
62F：→ leoone: 11题打错 01/19 20:49
63F：→ leoone: 15题 我是把red edge设0 blue edge设1做dijkstra 01/19 20:50
64F：→ leoone: 不对kruskal打错 01/19 20:51
65F：→ leoone: 一直打错XDD 01/19 20:52
66F：推 tinhanho: 1很奇怪 但f(8)应该是0吧?? 12/16 00:12
67F：→ tinhanho: 直接用KMP的failure func. 看的话 12/16 00:13