作者qwertz (人生苦短，來日方長)
看板Grad-ProbAsk
標題Re: [理工] [離散]-成大99
時間Mon Mar 8 17:02:32 2010
原題照我印象應該是..
女男配對問題
四女 五男
女1不配男1,3,5
女2不配男2,4
女3不配男1,3
女4不配男4
利用排容
__ __ __ __
令Ai表示女i與其不願意男配對 求N(A1 A2 A3 A4)
__ __ __ __
N(A1 A2 A3 A4) = S0 - S1 + S2 - S3 + S4
S0 = 5! = 120
S1 = N(A1) + N(A2) + N(A3) + N(A4)
= 4!( 3 + 2 + 2 + 1 )
= 192
S2 = N(A1 A2) + N(A1 A3) + N(A1 A4) + N(A2 A3) + N(A2 A4) + N(A3 A4)
= 3!( 3x2 + 2+2 + 3 + 2x2 + 1 + 2 )
= 120
S3 = N(A1 A2 A3) + N(A1 A2 A4) + N(A1 A3 A4) + N(A2 A3 A4)
= 2!( 2x(2+2) + 3 + 2+2 + 2 )
= 34
S4 = N(A1 A2 A3 A4)
= 1!(2+2)
= 4
__ __ __ __
N(A1 A2 A3 A4) = 120 - 192 + 120 - 34 + 4 = 18
在考場寫這題花了快三十分鐘 ... 結果S0寫成5^4.... 噢死 = ="
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.160.114.236
→ EntHeEnd:嗯嗯 感謝回答 03/08 17:03
→ EntHeEnd:畫tree解很快就解出來了 不過很多時候都會避免使用暴力法 03/08 17:03
→ EntHeEnd:orz... 有時候 暴力法還是蠻快的 03/08 17:04
推 assassin88:是說我也很幹..第一次算18，最後回頭蒜第二遍8+10寫成 03/08 17:06
→ assassin88:80..........幹爆了= = 03/08 17:06
推 EntHeEnd:補推~ 03/08 17:06
→ qwertz:真的... 在考場什麼不可能的錯都會出現= =" 03/08 17:08
推 luckysky1:暴力解算成17= = 03/08 17:08
推 EntHeEnd:有時候要不要用暴力法很難判斷... 反而浪費太多時間在想 03/08 17:08
→ EntHeEnd:要怎樣解orz... 03/08 17:08
→ losew:今年考70以上應該就滿強了我覺得 03/08 17:32
推 dancinglight:我畫一個好大的tree XD.... 03/08 23:46