作者qaswed101 (一一)
看板Grad-ProbAsk
标题[理工] 成大107 资讯联招
时间Mon Feb 5 12:05:41 2018
想问大家 资演都有写算式吗
最後一题根本没有读怎麽写
（approximation那题）ans=2
直接把背的答案写上去了～
不过整份考卷我都没看到说要explain有点怕怕的，所以每一题除了那题我都有写XD
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 101.8.247.71
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1517803544.A.8CA.html
1F：推 can18: 虽然他没要求但我每题都证明02/05 12:06
2F：推 kssdpp222: 202/05 12:06
3F：→ kssdpp222: 都没写 哈哈 写一面02/05 12:06
4F：→ can18: 2|C*| < 2|A| = |C|02/05 12:07
5F：推 lion83395: 我觉得要 去年我都没怎麽写算式 出来不如预期 QQ02/05 12:07
6F：→ MaoJ: 第一题ce吗02/05 12:07
7F：→ can18: 2|C*| > 2|A| = |C| 才对02/05 12:08
8F：推 gR7P4zXH: 第一题是A?02/05 12:08
9F：→ lion83395: Ce02/05 12:08
10F：→ kssdpp222: ce+102/05 12:08
11F：→ gR7P4zXH: Multipop那题有人有头绪吗QQ02/05 12:09
12F：推 MaoJ: 帅喔02/05 12:09
13F：推 havewind: CE+102/05 12:10
14F：→ MaoJ: n^2 + n 我赛一个02/05 12:10
15F：推 moneylon: 排序的lower bound 是多少02/05 12:11
16F：推 can18: ce+102/05 12:11
17F：推 kssdpp222: 可是他说开头空结尾也空 所以pop=push (包含mutilpop)02/05 12:12
18F：→ kssdpp222: 所以我猜不会那麽多02/05 12:12
19F：→ qaswed101: 我写 O(n)02/05 12:13
20F：推 gR7P4zXH: 恭喜大家QQ02/05 12:13
21F：推 can18: stack O(n) 我用accounting method 证02/05 12:14
22F：推 kssdpp222: Mutilpop O(n)+1 02/05 12:14
23F：→ can18: 排序 nlogn 用 decision tree证02/05 12:15
24F：推 wade8204: 如果只写答案会有分吗QQ 像排序那题02/05 12:20
25F：推 leoone: Stack 那题在考amortize cost O(n)02/05 12:20
26F：→ MaoJ: 排序那题会不会是纯比较和交换而已呢02/05 12:21
27F：推 jch660tw: Stack那题他说总共n次operation我想很久 最後我是算push02/05 12:33
28F：→ jch660tw: 最多n-1次 pop：2/n次 mpop：2/n次 然後把lower upper b02/05 12:33
29F：→ jch660tw: ound都写给它02/05 12:33
30F：推 ahahahahah: Multi 我写theta(n)02/05 12:34
31F：→ ahahahahah: 因为我upper和lower bound都算n...02/05 12:34
32F：→ jch660tw: 排序我是比较 交换 合在一起算的复杂度都写了 因为不知02/05 12:35
33F：→ jch660tw: 道要不要分开写02/05 12:35
34F：推 sarsman: 感觉得出来在考分摊，但我只有写次数，没转成复杂度符号q02/05 12:35
35F：→ sarsman: q02/05 12:35
36F：推 gary70812: potential function用里面item数量应该ok 吧？02/05 12:37
37F：推 can18: 比较後交换也是o(1) 没差吧02/05 12:37
38F：→ MaoJ: 水管 23吗02/05 12:39
39F：推 s06i06: 2302/05 12:40
40F：推 jch660tw: 23 我忘记几加几了02/05 12:40
41F：推 moneylon: 19+402/05 12:42
42F：推 OctRhythm: vertex cover大家算多少呢？02/05 12:44
43F：推 can18: vertex cover = 2 那题课本有02/05 12:44
44F：推 leoone: Vertex cover 那题是2 近似演算法的经典题 02/05 12:45
45F：→ leoone: 水管我写19忘记+4QQ02/05 12:46
46F：→ MaoJ: 是哪题呀 最後吗02/05 12:47
47F：推 kssdpp222: 那个考古的singer value 既然出现了 还有Jordan...02/05 15:22
48F：推 s06i06: 数学爆炸的举手 干02/05 15:24
49F：推 p5341500: 干02/05 15:24
50F：推 kssdpp222: 最後无解吗02/05 15:25
51F：→ s06i06: 是吧02/05 15:25
52F：推 lion83395: SVD看到直接跳了02/05 15:25
53F：推 gary70812: 无解＋102/05 15:26
54F：推 ahahahahah: 无解02/05 15:27
55F：推 jch660tw: 无解02/05 15:27
56F：推 Ofianse: 无解02/05 15:28
57F：推 can18: 无解+102/05 15:29
58F：推 ahahahahah: 离散第一题是38/83吗02/05 15:29
59F：推 gary70812: 红球那题是条件机率吗02/05 15:30
60F：→ can18: 机率第二题2/5？02/05 15:30
61F：→ gary70812: 我写45/83死定了02/05 15:30
62F：→ can18: 第一题我算 83/200多02/05 15:31
63F：推 lion83395: 45/83 +102/05 15:31
64F：→ can18: 好像是83 /28602/05 15:31
65F：→ lion83395: 第二题我算3/802/05 15:32
66F：推 MOUOREO: 不是45/83吗 还有x1,x2都等於2的情况？ 02/05 15:32
67F：→ can18: 45/83是哪一题呢02/05 15:32
68F：推 ahahahahah: 啊干我最後一步错了02/05 15:32
69F：→ gary70812: 红球算3/802/05 15:32
70F：→ MOUOREO: 第二题我也3/802/05 15:32
71F：→ ahahahahah: 这样还会有分吗QQ02/05 15:32
72F：→ lion83395: 整数解那题02/05 15:32
73F：→ can18: ... GG两题都错02/05 15:33
74F：推 Ofianse: 45/83辣02/05 15:33
75F：→ can18: 求算式02/05 15:33
76F：→ moneylon: 我算45/83下一题红球的3/802/05 15:33
77F：推 king8313: 是要算SVD还是只要singular value啊请问?!!02/05 15:34
78F：→ lion83395: 高中的记忆都还在 神奇XD02/05 15:34
79F：推 s1020824: C(10,8)/[2*C(10,8)-C(7,6)] 吧02/05 15:37
80F：→ can18: 误会题目意思 QQ02/05 15:39
81F：→ qaswed101: 我也是45/83 跟 3/802/05 16:03
82F：→ can18: 请问红球怎麽算02/05 16:07
83F：推 Ofianse: 八个红球只有三个来自第二桶啊02/05 16:09
84F：→ qaswed101: 红球8颗 第二箱有3颗 故得 3/802/05 16:10
85F：推 can18: 我算 第二桶拿到红球 /(第一桶拿到红球+第二桶拿到红球)02/05 16:16
86F：→ can18: 请问这样的算法的错误在哪02/05 16:17
87F：推 lion83395: 你这样算也会得3/8 我也是这样算的02/05 16:18
88F：推 can18: 好的 感谢 02/05 16:19
89F：推 gary70812: (1/6) /(8/18)吧 好像02/05 16:20
90F：推 lion83395: （1/2*1/3）/（1/2*5/9 +1/2*1/3）02/05 16:21
※ 编辑: qaswed101 (180.204.178.227), 02/05/2018 16:40:06
91F：推 nvwy9632: 难道只有我觉得是第二题1/6吗... 02/05 16:51
92F：推 kssdpp222: 3/8 02/05 17:04
93F：推 nO25948: 我也写1/6 02/05 17:06
94F：推 shownlin: 3/8 林纬题库班有一题一模一样的 02/05 17:07
95F：推 kssdpp222: 45/83 02/05 17:07
96F：推 q1qip123: 题目有说第二颗要拿红球喔？！想说2个箱子 直接写1／2… 02/05 17:20
97F：推 haohaoger: 请问资演第一题搜寻363怎麽找出错误选项啊？ 02/05 17:48
98F：推 leoone: 楼上 画出BST 记得c选项有出现 911 2xx 912 这样会出现分 02/05 17:54
99F：→ leoone: 支 就是错的 去年台大也考过 02/05 17:54
100F：推 nvwy9632: 往下找的数一定会夹在两个转向的数中间 02/05 17:58
101F：推 haohaoger: 嗯嗯好的谢谢两位解答~ 02/05 18:31
102F：推 jd06: 资演第一题有e? 我检查了两次没发现欸@@ 02/05 20:16
103F：推 MOUOREO: 有哦 02/05 20:24
104F：推 arhtur945: 程设100神人朝圣推 03/01 20:14