Re: [理工] [離散] 99成大
※ 引述《lsy77613 (鯨魚)》之銘言：
: 題目大意:
: 共有4個女生跟5個男生
: 1號女生不喜歡1或3或5號男生
: 2號女生不喜歡2或4號男生
: 3號女生不喜歡3或5號男生
: 4號女生不喜歡4號男生
: 請問有幾種方法可使這4個女生都找到合適的男生?
: 考慮過女生當箱子,男生當球的想法
: 但完全不知道這樣的解法x要取幾次方的係數才是所要的方法數
: 請高手指導這題該怎麼寫了,謝謝
想法是利用排容原理
將ai定義為第i個女生有限制
則可以推導答案為S-S1+S2-S3+S4
那S1~S4可以用暴力法或用小黃上課教過的"機車大連線"
這邊說明一下暴力法
S1定義為有一個女生選男生受到限制
example:1號女生必選1 3 5號男生 或是2號女生必選 2 4號男生
將全部的方法數加起來就是S1
所以S1=4*3*2*(3+2+2+1)
其中(4*3*2代表每一個女生受到限制之外的其他3個女生選男生方法數)
依此類推..
有錯請指教謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.161.193.164
※ 編輯: johnyne 來自: 1.161.193.164 (02/09 23:48)
推
02/09 23:50, , 1F
02/09 23:50, 1F
→
02/09 23:51, , 2F
02/09 23:51, 2F
推
02/10 01:15, , 3F
02/10 01:15, 3F
→
02/10 01:29, , 4F
02/10 01:29, 4F
→
02/10 08:09, , 5F
02/10 08:09, 5F
推
02/10 11:31, , 6F
02/10 11:31, 6F
推
02/10 17:09, , 7F
02/10 17:09, 7F
推
02/10 22:51, , 8F
02/10 22:51, 8F
→
02/10 22:51, , 9F
02/10 22:51, 9F
討論串 (同標題文章)