SRMdiv2第三題:
(頭兩題太水,就不貼出來了. . . . . . )
參照大神的代碼,終于理解(至少我認為基本懂了)了:下面是原題,大意是有N本書,給你一個數組a,a[n] = m代表的意思是要讀懂第N本書就必須先讀第m本書,如果m = -1,則不需要讀其他的書便可讀懂...然后求,:如果隨機讀這N本書,問能夠讀懂的書的數目的數學期望,
思路:算出每一本書的期望,加起來就是總數目的期望,,,對于第i本書,總可以找到一條以Si開始以Sj結束有向鏈(其中S(i+1) = a[Si], a[Sj] = -1),,然后在這條鏈中每一本書跟其他的書是獨立的,,也就是說,,讀不讀其他的書與這些書沒關系,,,對于Si,要讀懂它,就得先讀S(i+1)到S(j)這些書,期望為1 / len!,,,,(len是這條鏈的長度,,,就是排列組合,不多說了....)然后迭代這N本書的期望,,疊加得總數目期望.......
這是第一次參加Topcoder的比賽:感覺刷的題太少了,沒經驗,,,,最大的感悟就是,,,代碼越簡單越好(當然是在正確的前提下).晦澀難懂的代碼自己都懶得看,,,而且還不一定能夠編譯通過...還有就是在數據量很少的情況下優秀考慮用暴力法.,,,學好數學很重要!! !還好我是數學系的,,<:-:>
下面附上原題和大神的代碼截圖::::
Problem Statement
|
||||||||||||
|
King Dengklek is the perfect king of Kingdom of Ducks, where slimes and ducks live together in peace and harmony.
Kingdom of Ducks has a pretty strange currency system. There are only two coin types: one with value A and one with value B , where A and B are different. This currency system is denoted by { A , B }. These two coin types are sufficient for daily transactions, because all prices in this kingdom are in the form of ( A *p + B *q) for some non-negative integers p and q. Therefore, slimes and ducks can pay for any goods with a combination of the two coin types. Bored with the current system, King Dengklek considered another currency system with two coin types: one with value X and one with value Y, where X and Y are different. Of course, with this new system, combinations of the two new coin types must make it possible to pay all the prices one could pay with currency system { A , B }. (Note that the new coin types may also make it possible to pay some additional prices.) You are given ints A , B , and X . Return the number of different positive integers Y (other than X ) such that the currency system { X , Y} can be used to replace the currency system { A , B }. If there is an infinite number of possible values for Y, return -1 instead. |
||||||||||||
Definition |
||||||||||||
|
||||||||||||
Constraints |
||||||||||||
| - | A , B , and X will each be between 1 and 200, inclusive. | |||||||||||
| - | A and B will be different. | |||||||||||
Examples |
||||||||||||
| 0) | ||||||||||||
|
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
