Codeforces 912D

传送门：http://codeforces.com/contest/912/problem/D

本题是一个概率问题——求数学期望。

在一个n×m的方格中，有k个“*”。每个格子里可能有0~1个“*”。现有一个r×r的网，将网随机投入方格中，求解：网内“*”个数的数学期望的最大值。

首先考虑所求的数学期望：

枚举所有的投网方式，则对于方格的任意格子(x,y)，均可以定义其被网覆盖的次数cnt(x,y)。

若第i个“*”的位置为(x_i,y_i)，则此网覆盖第i个“*”的次数为cnt(x_i,y_i)，则所求期望为：$ans=\frac{\sum_{i=1}^{k} {cnt(x_i , y_i)}}{tot}$。其中，tot为投网的方法数，tot=(n-r+1)(m-r+1)。

这个问题的关键在于：求解一种“*”在方格内的放置方法，使得所求期望最大。

于是，可以考虑从方格中间的位置出发，通过BFS，寻找“*”的位置。于是，为BFS构造一个队列。由于本题需要求解最大值，所以每一次，均取cnt值最大的点作为当前步搜索的起点（于是这里用到优先队列std::priority_queue）。一步搜索向周围（U/D/L/R）推进一个格子。同时，应维护vis(x,y)，即点(x,y)是否被访问（根据本题的数据范围，请使用std::map）。进行k步搜索，每一步确定一个“*”的坐标。

参考程序如下：

#include <bits/stdc++.h>

using namespace std;

int n, m, r, k;

priority_queue<pair<int64_t, int64_t> > q;

map<int64_t, bool> vis;

int64_t pair2int(pair<int, int> p)

{

    return 1LL * m * p.first + p.second;

}

pair<int, int> int2pair(int64_t p)

{

    return make_pair(p / m, p % m);

}

int64_t cnt(pair<int, int> p)

{

    int x = p.first;

    int y = p.second;

    int dx = min(n, x + r) - max(r - , x);

    int dy = min(m, y + r) - max(r - , y);

    return 1LL * dx * dy;

}

int main(void)

{

    scanf("%d%d%d%d", &n, &m, &r, &k);

    pair<int, int> s = make_pair(n / , m / );

    q.push(make_pair(cnt(s), pair2int(s)));

    vis[pair2int(s)] = true;

    int64_t sum = 0LL;

    int64_t tot = 1LL * (n - r + ) * (m - r + );

    int dx[] = {-, , , };

    int dy[] = {, , -, };

    while (k--) {

        sum += q.top().first;

        pair<int, int> cur = int2pair(q.top().second);

        q.pop();

        for (int i = ; i < ; i++) {

            int x = cur.first + dx[i];

            int y = cur.second + dy[i];

            if (x <  || x >= n || y <  || y >= m) continue;

            pair<int, int> p = make_pair(x, y);

            if (vis[pair2int(p)]) continue;

            q.push(make_pair(cnt(p), pair2int(p)));

            vis[pair2int(p)] = true;

        }

    }

    double ans = 1.0 * sum / tot;

    printf("%.10f\n", ans);

    return ;

}

巴特西

Codeforces 912D - Fishes

最新文章

热门文章