SRM 537 div2 _概率

本菜把时间记错了，没赶上比赛T_T 。这次的题貌似不是很简单，今天大体做了一下
250pt：水题
550pt：题意是给出A, B, X, 求Y，使得A*p + B*q的所有能取到的值X*p' + Y*q'都能取到。如果有无限种可能就 -1 。当X同时被A, B整除时 -1，其他情况枚举y，同时满足 (A - y*q')%x == 0 和 (B - x*p')%y == 0.

文章插图
View Code
1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include
10 #include
11 #include
12 #include
13 #include
14 #include
15 #include
16 #include
17 #include
18 #include
19 #include
20
21 using namespace std;
22
23
24 class KingXNewCurrency {
25 public:
26int howMany(int A, int B, int X) {
27int cnt = 0, f;
28int y, k;
29
30if(!(A%X) && !(B%X))return -1;
31int M = max(A, B);
32for(y = 1; y <= M; ++y) {
33f = 0;
34for(k = 0; k <= A; k += y) {
35if((A - k)%X == 0) {
36f++; break;
37}
38}
39for(k = 0; k <= B; k += X) {
40if((B-k)%y == 0) {
41f++; break;
42}
43}
44if(f == 2)cnt++;
45}
46return cnt;
47}
48 };
49
50
51
52 //Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!
925pt:
求讲解，没看懂大牛们的思路。
03/22 补充：
6f7548ea6beae000f94088bd2b5b3dac
925pt：
【SRM 537 div2】看了polla的解题报告。。。想明白点了。
值为-1的蛋糕被吸收的概率为1 ，若存在一个序列 a -> b -> c -> d ,可以看出来，d前边的a, b, c共有 A 33 种情况但只有一种情况是d可以被吸收的。所以d被吸收的概率为1/ A 33
最后结果将所有元素的概率累加起来就可以
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

class PrinceXToastbook {
public:
double eat(vector pre) {
double res = 0, tmp;
int i, j, r, m;
int l = pre.size();
for(i = 0; i < l; ++i) {
r = i; m = 1;
while(m < 55) {
r = pre[r];
if(r == -1)break;
++m;
}
tmp = 1.0;
for(j = 1; j <= m; ++j) {
tmp *= j;
}
res += 1.0/tmp;
}
return res;
}
};

//Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!