作者try66889 (猫猫只求黑琴ㄍㄟˋ婚 )
看板Grad-ProbAsk
标题[理工] 资演 交大109 (4)(9)(12)
时间Sun Jan 3 12:49:36 2021
想请问大家几题QQ
4.
https://i.imgur.com/he9Gp5b.jpg
这题答案是CE
想请问CDE选项
CD）题目说minimum degree是t 代表应该每个node最少有t个child，为什麽有可能会小於t
个child呢？若minimum degree是t 每个node最少应该有t-1个key?
E）不知道要怎麽推QQ
9.
https://i.imgur.com/VxF6hZE.jpg
这题答案是E
题目的意思应该是把数列从小排到大看有几个可以满足 a_i1+a_i2+....+a_i(j-1)<=6a_ij
这样的话应该都可以满足？
1+2+2+2+3+5<=6*6
为什麽答案是5个呢？
还是有什麽地方我误会了吗QQ
12.
https://i.imgur.com/tKdskEY.jpg |
这题不知道怎麽算出X QQ
谢谢大家> <
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.32.191.76 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1609649378.A.51E.html
※ 编辑: try66889 (114.32.191.76 台湾), 01/03/2021 12:50:50
1F：推 karta1241535: 第4题, root不在限制范围 然後最後一个选项去看clr01/03 13:55
2F：→ karta1241535: s, 题目的是移项後的结果 第9题, 顺序不能自己改,01/03 13:55
3F：→ karta1241535: 只能选或不选, 最後一题, 当dp做凑个答案吧, 或是01/03 13:55
4F：→ karta1241535: 按照题目讲的当作min cost max flow 问题用Ford fu01/03 13:55
5F：→ karta1241535: lkerson做也行，但应该会做很久01/03 13:55
感谢k大 > < 前面两题了解惹!想再请问k大最後一题fulkerson画出来是这样吗@@?
因为画出後还试很久X算不出<=24 还是其实是我画错了? 谢谢 > <
https://i.imgur.com/fqUxu2g.jpg
※ 编辑: try66889 (114.32.191.76 台湾), 01/03/2021 14:18:07
※ 编辑: try66889 (114.32.191.76 台湾), 01/03/2021 14:18:46
6F：推 alex391a: 请问有大大可以分享109的交大考古吗～01/03 15:29
a大我题目和解答放google云端你试试看~
https://reurl.cc/v1yekj
8F：→ karta1241535: 这个方法其实我也不太会..01/03 15:36
9F：→ karta1241535: 建议直接试试各种不同的assign方式找出最小，考试01/03 15:38
10F：→ karta1241535: 中比较有可能只能这样做01/03 15:38
了解~感谢k大!，我再研究看看fulkerson~ 不好意思想再请问k大这题的DP是怎麽做的呢QQ
因为我做很多遍最小是找到22 QQ 取b1 a2 b3 a4 本身cost外再加上C12，C34 QWQ
11F：推 joywilliamjo: 最後一题我算X是22啦，题目有点不太理解意思，但我 01/03 16:15
12F：→ joywilliamjo: 算是B1B2B3A1，总cost2201/03 16:15
j大我和你一样最小找到22 QQ
※ 编辑: try66889 (114.32.191.76 台湾), 01/03/2021 16:29:04
※ 编辑: try66889 (114.32.191.76 台湾), 01/03/2021 16:31:07
13F：推 joywilliamjo: 我是觉得考场第一时间遇到这种题目要是没想到怎麽01/03 16:50
14F：→ joywilliamjo: 解就只能凑一凑了QQ 01/03 16:50
15F：→ joywilliamjo: 我是直接全a全b加，然後跳号不考虑，从C最小的开始 01/03 16:51
16F：→ joywilliamjo: 凑01/03 16:51
对阿QQ 考试遇到没想到应该只能先硬凑QQ 不过我这题凑两三天惹自己凑不出来XD
17F：→ chengweihsu: 最後一题，01/03 19:32
19F：→ chengweihsu: 中间的边容量 : 各modules间的通讯成本(双向都要)，01/03 19:37
20F：→ chengweihsu: 然後自己对自己为无限大01/03 19:37
21F：→ chengweihsu: flow有些没更新，不影响结果，修正一下01/03 20:23
感谢c大QQ 原来图要这样画QQ 不过想请问cost=0的cij不用在图上画出来吗OAO?
cost=0是像m1->m1'容量无限大吗@@?
然後为什麽p1->m3 那边的流量不能从m3->m3'->m2->m2'->m1->m4'->p2这样走呢?
最後是因为m4'->p2没有流满所以取b1b2b3a4吗?
不好意思问题有点多> < 再次感谢
23F：→ naive131: 原po你的13在a,24在b不是最小吧 你好像少算c23的cost 01/03 20:25
24F：→ naive131: 这题最小应该是123a, 4b 01/03 20:25
25F：→ naive131: 123b, 4a讲错01/03 20:25
感谢n大!我以为a对b一个对一个计算communication值就可以惹!原来每个都要计算> <
※ 编辑: try66889 (114.32.191.76 台湾), 01/03/2021 20:48:24
26F：→ chengweihsu: 每种cut代表一种分配法，因为各个modules最後都只会01/03 21:01
27F：→ chengweihsu: 属於p1或p2其中一个cut，所以为了强迫m_i和m_i'(同01/03 21:01
28F：→ chengweihsu: 个modules)只会被同时分到同个cut,它们之间的容量才 01/03 21:01
29F：→ chengweihsu: 要设成无限，并不是cost=0的关系 01/03 21:01
30F：→ chengweihsu: 然後m1->m4'之间没边怎麽流？01/03 21:03
31F：推 kopk159: B1+B2+B3+A4+C2,4+C3,4 01/03 21:06
32F：→ chengweihsu: 不过後来想想m_i跟m_i'捏成同一点结果应该会一样01/03 21:13
了解惹!!OWO! 感谢大家 > <
※ 编辑: try66889 (114.32.191.76 台湾), 01/03/2021 21:24:32
※ 编辑: try66889 (114.32.191.76 台湾), 01/03/2021 21:24:54
33F：推 joywilliamjo: 可是为什麽最後一题那个答案有给A啊？看不懂01/03 23:09
X=24，24 (mod10) =4 ~
※ 编辑: try66889 (114.32.191.76 台湾), 01/03/2021 23:41:29
34F：推 joywilliamjo: 可是算出来X不是22吗@@ 01/03 23:46
35F：→ joywilliamjo: 没事没事 01/03 23:47
36F：→ joywilliamjo: 我看到上面的了01/03 23:47
好XD
※ 编辑: try66889 (114.32.191.76 台湾), 01/03/2021 23:49:13
※ 编辑: try66889 (114.32.191.76 台湾), 01/04/2021 17:43:51