作者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/m.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