SRMdiv2第三題:
(頭兩題太水,就不貼出來了. . . . . . )
參照大神的代碼,終于理解(至少我認(rèn)為基本懂了)了:下面是原題,大意是有N本書,給你一個(gè)數(shù)組a,a[n] = m代表的意思是要讀懂第N本書就必須先讀第m本書,如果m = -1,則不需要讀其他的書便可讀懂...然后求,:如果隨機(jī)讀這N本書,問能夠讀懂的書的數(shù)目的數(shù)學(xué)期望,
思路:算出每一本書的期望,加起來就是總數(shù)目的期望,,,對(duì)于第i本書,總可以找到一條以Si開始以Sj結(jié)束有向鏈(其中S(i+1) = a[Si], a[Sj] = -1),,然后在這條鏈中每一本書跟其他的書是獨(dú)立的,,也就是說,,讀不讀其他的書與這些書沒關(guān)系,,,對(duì)于Si,要讀懂它,就得先讀S(i+1)到S(j)這些書,期望為1 / len!,,,,(len是這條鏈的長(zhǎng)度,,,就是排列組合,不多說了....)然后迭代這N本書的期望,,疊加得總數(shù)目期望.......
這是第一次參加Topcoder的比賽:感覺刷的題太少了,沒經(jīng)驗(yàn),,,,最大的感悟就是,,,代碼越簡(jiǎn)單越好(當(dāng)然是在正確的前提下).晦澀難懂的代碼自己都懶得看,,,而且還不一定能夠編譯通過...還有就是在數(shù)據(jù)量很少的情況下優(yōu)秀考慮用暴力法.,,,學(xué)好數(shù)學(xué)很重要!! !還好我是數(shù)學(xué)系的,,<:-:>
下面附上原題和大神的代碼截圖::::
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) | ||||||||||||
|
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
