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) | ||||||||||||
|
