题目链接 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;
}