Codeforces 912D Fishes （概率&期望，优先队列的应用）

题目链接 Fishes

题意在一个$n*m$的矩阵中，随机选择一个$r * r$的区域覆盖。

一开始我们可以在这个$n*m$的矩阵中选择$k$个点标记为$1$。

我们要选择一个最佳的标记策略，使得覆盖这个$r * r$的区域之后，被覆盖的$1$的个数的期望值最大。

求这个期望值。

$1 <= n, m <= 10^{5}, 1 <= k <= min(n*m, 10^{5})$

太笨了，比赛的时候并没有做出这道题

否则大概可以好好上一波分了？

结果只是勉强回到紫名

首先我们要推出若某个点$(x, y)$被标记为$1$了，那么这个点被覆盖的期望值。

我们所要做的，就是选出所有$n*m$的点中期望值前$k$大的并累加。

首先计算点$(x, y)$被标记的话这个点被覆盖的期望值。

inline double solve(int x, int y){

	double x1 = min(1.00 * x, n - x + 1.00); x1 = min(x1, n - 1.00 * r + 1); x1 = min(x1, 1.00 * r);

	double y1 = min(1.00 * y, m - y + 1.00); y1 = min(y1, m - 1.00 * r + 1); y1 = min(y1, 1.00 * r);

	return x1 * y1 / 1.00 / (n - r + 1) / (m - r + 1);

}

然后我们找一个显然是所有点中期望最大的点$(r, r)$，把他塞入优先队列。

因为期望是从中间往旁边递减，那么把这个点弹出来之后，把他周围的$4$个点再扔进去。

经过$k$次操作之后就得到了答案。

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

#define	MP		make_pair

const int dx[] = {1, 0, -1, 0};

const int dy[] = {0, 1, 0, -1};

struct node{

	int x, y;

	double z;

	friend bool operator < (const node &a, const node &b){

		return a.z < b.z;

	}

};

int n, m, r, k;

double ans = 0;

priority_queue <node> q;

map <pair <int, int>, int> mp;

inline bool check(int x, int y){

	return x >= 1 && x <= n && y >= 1 && y <= m && mp.count(MP(x, y)) == 0;

}

inline double solve(int x, int y){

	double x1 = min(1.00 * x, n - x + 1.00); x1 = min(x1, n - 1.00 * r + 1); x1 = min(x1, 1.00 * r);

	double y1 = min(1.00 * y, m - y + 1.00); y1 = min(y1, m - 1.00 * r + 1); y1 = min(y1, 1.00 * r);

	return x1 * y1 / 1.00 / (n - r + 1) / (m - r + 1);

}

int main(){

	cin >> n >> m >> r >> k;

	q.push({r, r, solve(r, r)});

	mp[MP(r, r)] = 1;

	while (k--){

		node now = q.top();

		int x = now.x, y = now.y;

		double z = now.z;

		ans += z;

		q.pop();

		rep(i, 0, 3){

			int nx = x + dx[i];

			int ny = y + dy[i];

			if (check(nx, ny)){

				mp[MP(nx, ny)] = 1;

				q.push({nx, ny, solve(nx, ny)});

			}

		}

	}

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

	return 0;

}

巴特西

Codeforces 912D Fishes （概率&期望，优先队列的应用）

最新文章

热门文章