第一次参加topcoder的感悟和解题报告

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 valueAand one with valueB, whereAandBare 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 valueXand one with value Y, whereXand 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 intsA,B, andX. Return the number of different positive integers Y (other thanX) 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

Class:	KingXNewCurrency
Method:	howMany
Parameters:	int, int, int
Returns:	int
Method signature:	int howMany(int A, int B, int X)
(be sure your method is public)

Constraints

-

A,B, andXwill each be between 1 and 200, inclusive.

-

AandBwill be different.

Examples

0)

5

8

5

Returns: 5

These are the 5 possible currency systems: {5, 1}, {5, 2}, {5, 3}, {5, 4}, and {5, 8}.