Google Kick Start 2020 Round B

Posted on Edited on In Views:

这次差半题就达成ALL KILL成就了，虽然有点遗憾，但是排名比Round A高出不少。华为软件杯已经打完，按照约定来复题了~

Round B的成绩主要失利在多次提交，罚时太重肯定拉了我很多名次。

Bick Tour

原题

Problem

Li has planned a bike tour through the mountains of Switzerland. His tour consists of N checkpoints, numbered from 1 to N in the order he will visit them. The i-th checkpoint has a height of Hi.

A checkpoint is a peak if:

  • It is not the 1st checkpoint or the N-th checkpoint, and
  • The height of the checkpoint is strictly greater than the checkpoint immediately before it and the checkpoint immediately after it.

Please help Li find out the number of peaks.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the integer N. The second line contains N integers. The i-th integer is Hi.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of peaks in Li's bike tour.

Limits

Time limit: 10 seconds per test set. Memory limit: 1GB. 1 ≤ T ≤ 100. 1 ≤ Hi ≤ 100.

Test set 1

3 ≤ N ≤ 5.

Test set 2

3 ≤ N ≤ 100.

Sample

Input

4 3 10 20 14 4 7 7 7 7 5 10 90 20 90 10 3 10 3 10

Output

Case #1: 1 Case #2: 0 Case #3: 2 Case #4: 0

  • In sample case #1, the 2nd checkpoint is a peak.
  • In sample case #2, there are no peaks.
  • In sample case #3, the 2nd and 4th checkpoint are peaks.
  • In sample case #4, there are no peaks.

题目大意

有N个检查点，如果一个检查点不是第一个也不是最后一个，而且它比前后检查点高度都要高，那么这就是一个山峰。问有几个山峰？

分析

比赛的时候我用的最朴素的方法，挨个数就完事了，时间复杂度O(n)，看了题解也是这个方法。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;

#define ll long long

int n;

int solve()
{
    cin >> n;
    int cnt = 0;
    vector<int> height(n);
    for (int i = 0; i < n; i++)
    {
        cin >> height[i];
    }
    
    for (int i = 1; i < n - 1; i++)
    {
        if (height[i - 1] < height[i] && height[i + 1] < height[i])
            cnt++;
    }
    return cnt;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    //freopen("1.txt", "r", stdin);
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        cout << "Case #" << i << ": " << solve() << endl;
    }

    return 0;
}

Bus Route

原题

Problem

Bucket is planning to make a very long journey across the countryside by bus. Her journey consists of N bus routes, numbered from 1 to N in the order she must take them. The buses themselves are very fast, but do not run often. The i-th bus route only runs every Xi days.

More specifically, she can only take the i-th bus on day Xi, 2Xi, 3Xi and so on. Since the buses are very fast, she can take multiple buses on the same day.

Bucket must finish her journey by day D, but she would like to start the journey as late as possible. What is the latest day she could take the first bus, and still finish her journey by day D?

It is guaranteed that it is possible for Bucket to finish her journey by day D.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the two integers N and D. Then, another line follows containing N integers, the i-th one is Xi.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the latest day she could take the first bus, and still finish her journey by day D.

Limits

Time limit: 10 seconds per test set. Memory limit: 1GB. 1 ≤ T ≤ 100. 1 ≤ Xi ≤ D. 1 ≤ N ≤ 1000. It is guaranteed that it is possible for Bucket to finish her journey by day D.

Test set 1

1 ≤ D ≤ 100.

Test set 2

1 ≤ D ≤ 1012.

Sample

Input

3 3 10 3 7 2 4 100 11 10 5 50 1 1 1

Output

Case #1: 6 Case #2: 99 Case #3: 1

In Sample Case #1, there are N = 3 bus routes and Bucket must arrive by day D = 10. She could:

  • Take the 1st bus on day 6 (X1 = 3),
  • Take the 2nd bus on day 7 (X2 = 7) and
  • Take the 3rd bus on day 8 (X3 = 2).

In Sample Case #2, there are N = 4 bus routes and Bucket must arrive by day D = 100. She could:

  • Take the 1st bus on day 99 (X1 = 11),
  • Take the 2nd bus on day 100 (X2 = 10),
  • Take the 3rd bus on day 100 (X3 = 5) and
  • Take the 4th bus on day 100 (X4 = 50),

In Sample Case #3, there is N = 1 bus route and Bucket must arrive by day D = 1. She could:

  • Take the 1st bus on day 1 (X1 = 1).

题目大意

出去旅行需要乘坐一些巴士，这些巴士都是每隔Xi天发一次车，如果需要在D天内坐完所有巴士，那么可以拖延几天之后，再开始坐巴士。

分析

这是如我一般拖延症患者经常思考的问题，如果已知ddl，问最晚什么时候开始工作一样可以完成任务。

言归正传，这是贪心题。贪心选择策略是最后需要乘坐的车辆尽可能晚上车，然后倒数第二个需要乘坐的车辆也尽可能晚上车…依次类推的话，可以得到第一个需要上车的车辆，最晚什么时候可以上车。

那最后需要乘坐的车辆最晚什么时候可以上车呢？如果最后需要乘坐的车辆每x天发车一次，需要在d天内完成旅程，那么上车时间应该是(d / x) * x，即d整除x再乘以x。此时如果把d更新成最后一辆车的上车时间，那么可以依次迭代计算，直至算出第一辆车的最晚上车时间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;

#define ll long long

ll solve()
{
    ll n, d;
    cin >> n >> d;
    vector<ll> x(n);
    for (int i = 0; i < n; i++)
    {
        cin >> x[i];
    }

    for (int i = n - 1; i >= 0; i--)
    {
        d = (d / x[i]) * x[i];
    }
    
    
    return d;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    //freopen("1.txt", "r", stdin);
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        cout << "Case #" << i << ": " << solve() << endl;
    }

    return 0;
}

Robot Path Decoding

原题

Problem

Your country's space agency has just landed a rover on a new planet, which can be thought of as a grid of squares containing \(10^9\) columns (numbered starting from 1 from west to east) and \(10^9\) rows (numbered starting from 1 from north to south). Let (w, h) denote the square in the w-th column and the h-th row. The rover begins on the square (1, 1).

The rover can be maneuvered around on the surface of the planet by sending it a program, which is a string of characters representing movements in the four cardinal directions. The robot executes each character of the string in order:

  • N: Move one unit north.
  • S: Move one unit south.
  • E: Move one unit east.
  • W: Move one unit west.

There is also a special instruction , whereXis a number between 2 and 9 inclusive andYis a non-empty subprogram. This denotes that the robot should repeat the subprogramYa total ofXtimes. For example:

Since the planet is a torus, the first and last columns are adjacent, so moving east from column \(10^9\) will move the rover to column 1 and moving south from row \(10^9\) will move the rover to row 1. Similarly, moving west from column 1 will move the rover to column \(10^9\) and moving north from row 1 will move the rover to row \(10^9\) . Given a program that the robot will execute, determine the final position of the robot after it has finished all its movements.

Input

The first line of the input gives the number of test cases, T. T lines follow. Each line contains a single string: the program sent to the rover.

Output

For each test case, output one line containing Case #x: w h, where x is the test case number (starting from 1) and w h is the final square (w, h) the rover finishes in.

Limits

Time limit: 10 seconds per test set. Memory limit: 1GB. 1 ≤ T ≤ 100. The string represents a valid program. The length of each program is between 1 and 2000 characters inclusive.

Test set 1

The total number of moves the robot will make in a single test case is at most \(10^4\) .

Test set 2

No additional constraints.

Sample

Input

4 SSSEEE N N3(S)N2(E)N 2(3(NW)2(W2(EE)W))

Output

Case #1: 4 4 Case #2: 1 1000000000 Case #3: 3 1 Case #4: 3 999999995

In Sample Case #1, the rover moves three units south, then three units east.

In Sample Case #2, the rover moves one unit north. Since the planet is a torus, this moves it into row \(10^9\) .

In Sample Case #3, the program given to the rover is equivalent to NSSSNEEN.

In Sample Case #4, the program given to the rover is equivalent to NWNWNWWEEEEWWEEEEWNWNWNWWEEEEWWEEEEW.

题目大意

有一个机器人，它会接受指令在地图上移动，地图的大小是\(10^9 \times 10^9\)，左上角点坐标是(1， 1)，这也是起始点，右下角点坐标是(\(10^9\)， \(10^9\))。

指令是这样的，指令中会有NSEW四个字符，分别表示向上向下向右向左移动，另外还可能有一个数字后面跟上一对小括号，表示括号里的指令需要重复多少次。

分析

这种括号展开的题以前也见到过，我的思路是当我遇到第一个右括号时，那么从最近的一个左括号到这个右括号之间的字符串，一定是一个简单的不包含任何括号的字符串，否则这就不是第一个右括号。

虽然有NSEW四个字符，但是可以只用两个变量来表示，类比于平面坐标系里的x和y，N和S可以用y--和y++来记录，EW同理。

我使用了类似于栈的数据结构，每遇到一个左括号，就进入一层栈空间，等遇到下一个右括号时，这个栈空间的数据处理完毕，把结果融入到上一层栈空间中。

Note：这题注意要及时对\(10^9\)取模，不然很可能会数值溢出。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;

#define ll long long

ll ords[1005][3]; // 分别表示向下和向右的前进次数（如果为负数就表示向上和向左），第3格存储这段指令重复次数
const ll limit = 1e9;

void solve()
{
    string ordstr;
    cin >> ordstr;
    int ptr = 0;
    char c;

    ords[0][0] = 0;
    ords[0][1] = 0;
    ords[0][2] = 1;

    for (auto it = ordstr.begin(); it != ordstr.end(); it++)
    {
        c = *it;
        if (c == 'N')
            ords[ptr][0]--;
        else if (c == 'S')
            ords[ptr][0]++;
        else if (c == 'E')
            ords[ptr][1]++;
        else if (c == 'W')
            ords[ptr][1]--;
        else if (c == ')')
        {
            ords[ptr - 1][0] += ords[ptr][2] * ords[ptr][0];
            ords[ptr - 1][1] += ords[ptr][2] * ords[ptr][1];
            ords[ptr - 1][0] = (ords[ptr - 1][0] + limit) % limit;
            ords[ptr - 1][1] = (ords[ptr - 1][1] + limit) % limit;
            ptr--;
        }
        else
        {
            ptr++;
            ords[ptr][0] = 0;
            ords[ptr][1] = 0;
            ords[ptr][2] = c - '0';
            it++;
        }
    }
    cout << (ords[0][1] + limit) % limit + 1 << " " << (ords[0][0] + limit) % limit + 1;
}

int main()
{
    // freopen("1.txt", "r", stdin);

    ios::sync_with_stdio(0);
    cin.tie(0);
    int t, i = 1;
    cin >> t;
    while (t--)
    {
        cout << "Case #" << i++ << ": ";
        solve();
        cout << "\n";
    }
    return 0;
}

Wandering Robot

原题

Problem

Jemma is competing in a robotics competition. The challenge for today is to build a robot that can navigate around a hole in the arena.

The arena is a grid of squares containing W columns (numbered 1 to W from left to right) and H rows (numbered 1 to H from top to bottom). The square in the x-th column and y-th row is denoted (x, y). The robot begins in the top left square (1,1) and must navigate to the bottom right square (W, H).

A rectangular subgrid of squares has been cut out of the grid. More specifically, all the squares that are in the rectangle with top-left square (L, U) and bottom-right square (R, D) have been removed.

Jemma did not have much time to program her robot, so it follows a very simple algorithm:

  • If the robot is in the rightmost column, it will always move to the square directly below it. Otherwise,
  • If the robot is in the bottommost row, it will always move to the square directly right of it. Otherwise,
  • The robot will randomly choose to either move to the square directly to the right, or to the square directly below it with equal probability.

Jemma passes the challenge if her robot avoids falling into the hole and makes it to the square (W, H). What is the probability she passes the challenge?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of a single line containing W, H, L, U, R and D.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is a real number between 0 and 1 inclusive, the probability that Jemma passes the challenge.

y will be considered correct if it is within an absolute or relative error of \(10^{-5}\) of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.

Limits

Time limit: 15 seconds per test set. Memory limit: 1GB. 1 ≤ T ≤ 100. 1 ≤ U ≤ D ≤ H. 1 ≤ L ≤ R ≤ W. Neither the top-left nor bottom-right squares will be missing.

Test set 1

1 ≤ W ≤ 300. 1 ≤ H ≤ 300.

Test set 2

1 ≤ W ≤ \(10^5\). 1 ≤ H ≤ \(10^5\).

Sample

Input

4 3 3 2 2 2 2 5 3 1 2 4 2 1 10 1 3 1 5 6 4 1 3 3 4

Output

Case #1: 0.5 Case #2: 0.0625 Case #3: 0.0 Case #4: 0.3125

题目大意

有个机器人，在地图上移动。机器人从地图的左上角出发，要到地图的右下角去。如果机器人在地图的底边界，那么它一定会向右移动，如果机器人在地图的右边界，那么它一定会向下移动，否则机器人会50%的概率向下移动，50%的概率向右移动。

现在地图里有一个矩形区域的洞，如果机器人掉到洞里就失败了。问机器人有多少的概率可以走到右下角的终点。

分析

看到题目的感觉就是，老动态规划了。如果使用动态规划的思想解题还是比较直观的。

如果在底边界，那么可以100%的概率从左边一格走过来，也可以50%的概率从上面一格走过来，当前概率 = 左边一格的概率 + 0.5 * 上面一格的概率

如果在右边界，那么可以100%的概率从上面一格走过来，也可以50%的概率从左边一格走过来，当前概率 = 上面一格的概率 + 0.5 * 左边一格的概率

如果不在底边界也不在右边界，那么有50%的概率从左边一格走来，已有50%的概率从上面一格走来，当前概率 = 0.5 * 左边一格的概率 + 0.5 * 上面一格的概率

动归代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;

#define ll long long

double solve()
{
    ll w, h, l, u, r, d;
    cin >> w >> h >> l >> u >> r >> d;
    vector<vector<double>> map(h + 1, vector<double>(w + 1, 0));
    map[1][1] = 1;
    for (int j = 2; j <= w; j++)
    {
        if (u == 1 && j == l) break;
        map[1][j] = 0.5 * map[1][j - 1];
    }

    for (int i = 2; i <= h; i++)
    {
        if (l == 1 && i == u) break;
        map[i][1] = 0.5 * map[i - 1][1];
    }

    for (int i = 2; i <= h; i++)
    {
        for (int j = 2; j <= w; j++)
        {
            if (u <= i && i <= d && l <= j && j <= r)
                map[i][j] = 0;
            else if (i == h && j == w)
                map[i][j] = map[i - 1][j] + map[i][j - 1];
            else if (i == h)
                map[i][j] = 0.5 * map[i - 1][j] + map[i][j - 1];
            else if (j == w)
                map[i][j] = map[i - 1][j] + 0.5 * map[i][j - 1];
            else
                map[i][j] = 0.5 * map[i - 1][j] + 0.5 * map[i][j - 1];
        }
    }

    return map[h][w];
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    //freopen("1.txt", "r", stdin);
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        cout << "Case #" << i << ": " << solve() << endl;
    }

    return 0;
}

这个代码第二个数据集会报MLE的错误，也就是内存占用过多。动归有一个经典优化方法，就是数组复用，降低空间复杂度，优化后的代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;

#define ll long long

double solve()
{
    ll w, h, l, u, r, d;
    cin >> w >> h >> l >> u >> r >> d;
    vector<double> map(w + 1, 0);
    if (l == 1 && u == 1)
        return 0;
    if (r == w && d == h)
        return 0;
    map[1] = 1;
    for (int j = 2; j <= w; j++)
    {
        if (u == 1 && j == l)
            break;
        map[j] = 0.5 * map[j - 1];
    }

    for (int i = 2; i <= h; i++)
    {
        if (l == 1 && u <= i && i <= d)
            map[1] = 0;
        else
            map[1] = 0.5 * map[1];

        for (int j = 2; j <= w; j++)
        {

            if (u <= i && i <= d && l <= j && j <= r)
            {
                fill(map.begin() + j, map.begin() + r + 1, 0);
                j = r;
            }
            else if (i == h && j == w)
                map[j] = map[j] + map[j - 1];
            else if (i == h)
                map[j] = 0.5 * map[j] + map[j - 1];
            else if (j == w)
                map[j] = map[j] + 0.5 * map[j - 1];
            else
                map[j] = 0.5 * map[j] + 0.5 * map[j - 1];
        }
    }

    return map[w];
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    //freopen("1.txt", "r", stdin);
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        cout << "Case #" << i << ": " << solve() << endl;
    }

    return 0;
}

这个代码不会报MLE的错误，空间复杂度满足，但是又报TLE的错误，反复折腾几次还是过不去，那就是时间复杂度的问题了，比赛的时候没整出来，结束后查看解答才恍然大悟😂。

官方解答

Test Set 1

We can solve this test set using dynamic programming. Let f(x, y) be the probability Jemma passes the challenge if she is currently in the square (x, y). The base case of this function is f(W, H) = 1. Also, if the square (x, y) has been removed, then f(x, y) = 0.

If there is only one possible square to go to from square (x, y) (i.e. either x = W or y = H), then f(x, y) = f(x', y'), where (x', y') is the possible next square. Otherwise, let (x1', y1') and (x2', y2') be the possible next squares. Since they have the same probability to become the next square, f(x, y) = 0.5 × f(x1', y1') + 0.5 × f(x2', y2').

The running time and space of this solution is O(W × H).

Test Set 2

The first observation to solve this problem is to realize that there are two ways to avoid the hole: either going to the left and the bottom of the hole (illustrated by the red path in the figure below), or going to the top and the right of the hole (illustrated by the blue path in the figure below).

two_paths

It can be seen that the set of paths in the red path and the blue path are disjoint--there is no path that goes both to the left of the hole and to the top of the hole simultaneously. Therefore, we can compute the probability that Jemma passes the challenge by taking the red path and the blue path separately and compute the sum of both probabilities.

Since the probability of passing the challenge by taking the blue path can be computed similarly, we only focus on computing the probability of passing the challenge by taking the red path for the rest of the discussion. The next observation to solve this problem is that we can choose a set of squares diagonally from the bottom-left corner of the hole (illustrated by the green squares below) such that Jemma has to pass exactly one of the squares to pass the challenge by taking the red path. Also, by landing on one of the squares, it is no longer possible that Jemma will fall to the hole, thus passing the challenge by taking the red path is now guaranteed.

critical_points

Therefore, computing the probability of passing the challenge by taking the red path is equivalent to computing the probability that Jemma will land on one of the green squares. Similar to the red and blue paths discussion, since Jemma cannot pass two green squares simultaneously, we can compute the probability that Jemma lands on each square separately and compute the sum of all probabilities.

Let us take square X for an example. Consider all paths that go to the square X. For each move in the path, there is a 0.5 probability that the move will follow the path. Since the number of moves to square X is (L + D - 2), there is a \((0.5)^{(L + D - 2)}\) probability that this path will be taken. This number has to be multiplied with the number of paths to go to square X, which can be computed using a single binomial coefficient. The probability of reaching any particular green square is the same for all but the green square in the last row, which is left to the reader as an exercise.

To handle floating point issues, we can store every huge number in their log representation (i.e. storing \(log_2(x)\) instead of x). We can then compute the value of \(C(n, k) / 2^n\) using \(2^{log_2(n! / (k! × (n - k)!) / 2^n)} = 2^{log_2(n!) - log_2(k!) - log_2((n - k)!) - n}\), which takes constant time to compute if we have precomputed every value of \(log_2(x!)\). Since there can be at most O(N) green squares, where N is the larger length of the grid (i.e. N = max(H, W)), the total running time of this solution is O(N).

题解大意

我们会发现，如果想要从左上角到右下角，而且不掉到洞里去，那么可以大概分成2条路线，从洞的左下角绕过去，或者是从洞的右上角绕过去，如下面图的红蓝线所示。

two_paths

这两个路径概率的求解是对称的，所以想好如何求其中一条路线的概率，另一条路线的概率求解方式类似。

那以求红色路线的概率举例，如果从洞的左下角绕过去，可以进一步细分为，必须经过X点和必须经过Y点两部分路径，因为机器人只能往右或往下走，所以不可能存在一条路径又经过X又经过Y的。

critical_points

如果机器人已经到达了X点，那么他将100%能到达终点，还是因为机器人只能往右或往下走，所以肯定最后会走到终点。到达Y点也是。

所以红色路线的概率等于起点到X的概率+起点到Y的概率，那起点到X的概率又该怎么求。

可以发现从起点到X点需要经过1次向右和6次向下，这两个动作的概率都是0.5，所以总概率应该是\(0.5^{(6 + 1)}\)，然而1次向右和6次向下这些动作没有特定的先后关系，所以还要乘以组合数\(C_{(6 + 1)}^{1}\)，总概率应该等于\(C_{(6 + 1)}^{1} \times 0.5^{(6 + 1)}\)，也就是\(C_{(6 + 1)}^{1} / 2^{(6 + 1)}\)。类似的想法可以计算到Y的概率\(C_{7}^{0} / 2^{7}\)。

如果X和Y不属于底边上的点，那么可以这么算，但是有些时候，从洞的左下角不断往下延伸，会触碰到地图的下边界，而在下边界的概率传递不是0.5，这种情况会比较麻烦。如果需要计算起点到底边上的点，比如要计算起点到Z点的概率，又该如何计算呢？

critical_points2

可以发现Z点可以由A点由50%的概率传递过来，也可以由Z'以100%的概率传递过来，那么我们只需要以之前的方法，计算起点到A的概率再乘以50%，再加上起点到Z'的概率就可以了。

起点到A的概率计算方法和之前一样，而起点到Z'的概率不太好求，因为Z'和Z点一样，在下边界上。但是再想想，已经可以求起点到Z的概率了，起点到Z'的概率可以用相同的方式计算，用P(A)表示起点到A的概率，那么有： \[ P(Z) = 0.5 \times P(A) + P(Z') \]

\[ P(Z') = 0.5 \times P(B) + P(Z'') \]

\[ P(Z'') = 0.5 \times P(Y) \]

只要递归下去找到P(Z''​)的概率，就可以求得P(Z)的概率。

另外还有一点是，为了确保浮点数的计算精确性，本题建议把浮点数计算转为log计算。比如把\(C(n, k) / 2^n\) 用 \(2^{log_2(n! / (k! × (n - k)!) / 2^n)} = 2^{log_2(n!) - log_2(k!) - log_2((n - k)!) - n}\)来代替。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const ll max_n = 1e6 + 10;
double log2x[max_n]; // i-th elem record log2(i!)

void solve()
{
    int w, h, l, u, r, d;
    cin >> w >> h >> l >> u >> r >> d;
    w--, h--, l--, u--, r--, d--;

    double ans = 0.0;

    int x = r, y = u;
    if (x < w)
    {
        double multi = 1.0;
        int n, k;
        while (y > 0)
        {
            y--;
            x++;

            if (x >= w)
            {
                x = w - 1;
                multi = 0.5;  
            }
            n = x + y;
            k = x;
            
            ans += multi * pow(2, log2x[n] - log2x[k] - log2x[n - k] - n);
        }
    }

    swap(w, h);
    swap(u, l);
    swap(d, r);
    x = r, y = u;
    if (x < w)
    {
        double multi = 1.0;
        int n, k;
        while (y > 0)
        {
            y--;
            x++;

            if (x >= w)
            {
                x = w - 1;
                multi = 0.5;
            }
            n = x + y;
            k = x;
            ans += multi * pow(2, log2x[n] - log2x[k] - log2x[n - k] - n);
        }
    }

    cout << ans;
}

int main()
{
    // freopen("1.txt", "r", stdin);

    ios::sync_with_stdio(0);
    cin.tie(0);
    int t, i = 1;
    cin >> t;

    for (int i = 2; i < max_n; i++)
    {
        log2x[i] = log2x[i - 1] + log2(i);
    }

    while (t--)
    {
        cout << "Case #" << i++ << ": ";
        solve();
        cout << "\n";
    }
    return 0;
}
Image