Codeforces 921D(期望+BFS)

Codeforces 921D
题意:有一个$n \times m$的鱼塘,有一张$r \times r$的渔网,现在往池塘里面放$k$条鱼(每个格子只能放一条鱼), 现在撒网的地方是随机的(必须在池塘内),问能捕的鱼的期望值最大是多少?

原题的期望值为
$$\frac{\sum max_k(f(i,j))}{(n - r + 1)(m - r + 1)}$$
其中$f(i,j)$为$r \times r$的网在鱼塘$(i,j)$点上总共会撒的次数,$max_k$表示最大的$k$个数

然后可以证明从中间开始是最优的,我们可以BFS来模拟这个过程,但是要用一个优先队列保证每次取的都是最大值

代码中的$cal$就是上述公式的$f$函数

Codeforces Submission

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
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<iostream>
using namespace std;
#define ms(i, j) memset(i, j, sizeof i)
#define ll long long
#define db double
#define pr pair<int, int>
#define fir first
#define sec second
#define mp make_pair
const ll dx[4] = {1, 0, -1, 0};
const ll dy[4] = {0, 1, 0, -1};
ll n, m, r, k;
set<pr> s;
struct data {
ll x, y, v;
bool operator < (const data &b) const {
return v < b.v;
}
};
priority_queue<data> q;
ll cal(ll i, ll j) {
return 1ll * (min(i, n - r + 1ll) - max(1ll, i - r + 1ll) + 1ll) * (min(j, m - r + 1ll) - max(1ll, j - r + 1ll) + 1ll);
}
void clean() {
}
int solve() {
clean();
if (n == 1 || m == 1) {
printf("%.10f\n", (db)k / (db)((db)n * (db)m));
return 0;
}
ll fz = 0, fm = (n - r + 1) * (m - r + 1);
q.push((data){(n + 1) / 2, (m + 1) / 2, cal((n + 1) / 2, (m + 1) / 2)});
s.insert(mp((n + 1) / 2, (m + 1) / 2));
while (!q.empty()) {
data p = q.top(); q.pop();
fz += p.v;
k--; if (!k) break;
for (ll i = 0; i < 4; i++) {
ll tx = p.x + dx[i], ty = p.y + dy[i];
if (tx > 0 && ty > 0 && tx <= n && ty <= m && !s.count(mp(tx, ty))) {
q.push((data){tx, ty, cal(tx, ty)});
s.insert(mp(tx, ty));
}
}
}
printf("%.10f\n", (db)fz / (db)fm);
return 0;
}
int main() {
cin >> n >> m >> r >> k, solve();
return 0;
}

------ 本文结束 ------