SRM 537 div2

　　本菜把时间记错了，没赶上比赛T_T。这次的题貌似不是很简单，今天大体做了一下

250pt：水题

550pt：题意是给出A, B, X, 求Y，使得A*p + B*q的所有能取到的值X*p' + Y*q'都能取到。如果有无限种可能就return -1。当X同时被A, B整除时return -1，其他情况枚举y，同时满足 (A - y*q')%x == 0 和 (B - x*p')%y == 0.

View Code

 1 #include <vector>
 2 #include <list>
 3 #include <map>
 4 #include <set>
 5 #include <queue>
 6 #include <deque>
 7 #include <stack>
 8 #include <bitset>
 9 #include <algorithm>
10 #include <functional>
11 #include <numeric>
12 #include <utility>
13 #include <sstream>
14 #include <iostream>
15 #include <iomanip>
16 #include <cstdio>
17 #include <cmath>
18 #include <cstdlib>
19 #include <ctime>
20 
21 using namespace std;
22 
23 
24 class KingXNewCurrency {
25 public:
26     int howMany(int A, int B, int X) {
27         int cnt = 0, f;
28         int y, k;
29         
30         if(!(A%X) && !(B%X))    return -1;
31         int M = max(A, B);
32         for(y = 1; y <= M; ++y) {
33             f = 0;
34             for(k = 0; k <= A; k += y) {
35                 if((A - k)%X == 0) {
36                     f++; break;
37                 }
38             }
39             for(k = 0; k <= B; k += X) {
40                 if((B-k)%y == 0) {
41                     f++; break;
42                 }
43             }
44             if(f == 2)    cnt++;
45         }
46         return cnt;
47     }
48 };
49 
50 
51 <%:testing-code%>
52 //Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!

925pt:

求讲解，没看懂大牛们的思路。

03/22 补充：

925pt：

看了polla的解题报告。。。想明白点了。

值为-1的蛋糕被吸收的概率为1，若存在一个序列 a -> b -> c -> d ,可以看出来，d前边的a, b, c共有 A³₃种情况但只有一种情况是d可以被吸收的。所以d被吸收的概率为1/ A³₃

最后结果将所有元素的概率累加起来就可以

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;


class PrinceXToastbook {
public:
    double eat(vector <int> 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;
    }
};


<%:testing-code%>
//Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!