[理工] 資演 交大109 (4)(9)(12)

[try66889 (貓貓只求黑琴ㄍㄟˋ婚 )]

想請問大家幾題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://www.ptt.cc/bbs/Grad-ProbAsk/M.1609649378.A.51E.html
※ 編輯: try66889 (114.32.191.76 臺灣), 01/03/2021 12:50:50
推 karta1241535: 第4題, root不在限制範圍 然後最後一個選項去看clr
→ karta1241535: s, 題目的是移項後的結果 第9題, 順序不能自己改,
→ karta1241535: 只能選或不選, 最後一題, 當dp做湊個答案吧, 或是
→ karta1241535: 按照題目講的當作min cost max flow 問題用Ford fu
→ karta1241535: lkerson做也行，但應該會做很久
感謝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
推 alex391a: 請問有大大可以分享109的交大考古嗎～
a大我題目和解答放google雲端你試試看~
https://reurl.cc/v1yekj

推 karta1241535: 可參考 http://web.ntnu.edu.tw/~algo/Flow2.html
→ karta1241535: 這個方法其實我也不太會..
→ karta1241535: 建議直接試試各種不同的assign方式找出最小，考試
→ karta1241535: 中比較有可能只能這樣做
了解~感謝k大!，我再研究看看fulkerson~ 不好意思想再請問k大這題的DP是怎麼做的呢QQ
因為我做很多遍最小是找到22 QQ 取b1 a2 b3 a4 本身cost外再加上C12，C34 QWQ
推 joywilliamjo: 最後一題我算X是22啦，題目有點不太理解意思，但我
→ joywilliamjo: 算是B1B2B3A1，總cost22
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
推 joywilliamjo: 我是覺得考場第一時間遇到這種題目要是沒想到怎麼
→ joywilliamjo: 解就只能湊一湊了QQ
→ joywilliamjo: 我是直接全a全b加，然後跳號不考慮，從C最小的開始
→ joywilliamjo: 湊
對阿QQ 考試遇到沒想到應該只能先硬湊QQ 不過我這題湊兩三天惹自己湊不出來XD
→ chengweihsu: 最後一題，
→ chengweihsu: https://i.imgur.com/ReCvSUJ.jpg
→ chengweihsu: 中間的邊容量 : 各modules間的通訊成本(雙向都要)，
→ chengweihsu: 然後自己對自己為無限大
→ chengweihsu: flow有些沒更新，不影響結果，修正一下
→ chengweihsu: https://i.imgur.com/elN3Fxe.jpg
感謝c大QQ 原來圖要這樣畫QQ 不過想請問cost=0的cij不用在圖上畫出來嗎OAO?
cost=0是像m1->m1'容量無限大嗎@@?
然後為什麼p1->m3 那邊的流量不能從m3->m3'->m2->m2'->m1->m4'->p2這樣走呢?
最後是因為m4'->p2沒有流滿所以取b1b2b3a4嗎?
不好意思問題有點多> < 再次感謝
→ naive131: 原po你的13在a,24在b不是最小吧 你好像少算c23的cost
→ naive131: 這題最小應該是123a, 4b
→ naive131: 123b, 4a講錯
感謝n大!我以為a對b一個對一個計算communication值就可以惹!原來每個都要計算> <
※ 編輯: try66889 (114.32.191.76 臺灣), 01/03/2021 20:48:24
→ chengweihsu: 每種cut代表一種分配法，因為各個modules最後都只會
→ chengweihsu: 屬於p1或p2其中一個cut，所以為了強迫m_i和m_i'(同
→ chengweihsu: 個modules)只會被同時分到同個cut,它們之間的容量才
→ chengweihsu: 要設成無限，並不是cost=0的關係
→ chengweihsu: 然後m1->m4'之間沒邊怎麼流？
推 kopk159: B1+B2+B3+A4+C2,4+C3,4
→ chengweihsu: 不過後來想想m_i跟m_i'捏成同一點結果應該會一樣
了解惹!!OWO! 感謝大家 > <
※ 編輯: try66889 (114.32.191.76 臺灣), 01/03/2021 21:24:32
※ 編輯: try66889 (114.32.191.76 臺灣), 01/03/2021 21:24:54
推 joywilliamjo: 可是為什麼最後一題那個答案有給A啊？看不懂
X=24，24 (mod10) =4 ~
※ 編輯: try66889 (114.32.191.76 臺灣), 01/03/2021 23:41:29
推 joywilliamjo: 可是算出來X不是22嗎@@
→ joywilliamjo: 沒事沒事
→ joywilliamjo: 我看到上面的了
好XD
※ 編輯: try66889 (114.32.191.76 臺灣), 01/03/2021 23:49:13
※ 編輯: try66889 (114.32.191.76 臺灣), 01/04/2021 17:43:51