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

现在的位置: 首页 > 综合 > 正文

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

2013年12月04日 ⁄ 综合 ⁄ 共 1931字 ⁄ 字号小中大 ⁄ 评论关闭

文章目录

SRMdiv2第三题:
Definition
Constraints
Examples

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, whereA 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

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)