CF912D Fishes
2024-10-09 02:28:36
题目链接:http://codeforces.com/contest/912/problem/D
题目大意:
在一个\(n \times m\)的网格中放鱼(每个网格只能放一条鱼),用一个\(r \times r\)的网随机地捕一次鱼,问如何放置鱼能使得捕到的鱼的期望值最大,求最大值。
知识点: 优先队列、概率与期望
解题思路:
要使捕到鱼的期望值最大,就应该往最有可能被渔网捞到的格子里放鱼。
\(P(某个格子被捞到)= N_1(渔网能捞到这个格子的放置方案数)/N_2(渔网总放置方案数),\)
\(N(渔网总放置方案数) = (n-r+1)\times(m-r+1)\)
而要求\(N_1\),我们可以先算出最左边一列和最上边一行的各个格子对应的\(N_1\),\(N_1(x,y) = N_1(x,0) \times N_1(0,y)\)。于是我们可以从最中间的格子开始(直觉告诉我们:最中间的格子总是最有可能被捞到),用一个优先队列维护,每次都往上下左右四个方向拓展,找出前 \(k\) 个最有可能被捞到的位置所对应的期望值,加起来所得到的总和即为答案。
AC代码:
#include <bits/stdc++.h> using namespace std;
const int maxn = 1e5+;
const int cx[]={,-,,},cy[]={,,,-}; int line[maxn],col[maxn];
struct node{
int x,y;
double z;
friend bool operator <(const node &a,const node &b){
return a.z<b.z;
}
};
map<pair<int,int>,int> vis;
priority_queue<node> q; int main(){
int n,m,r,k;
scanf("%d%d%d%d",&n,&m,&r,&k);
for(int i=;i<=(n+)/;i++){
if(i<=n-r+) line[i]=min(i,r);
else line[i]=line[i-];
}
for(int i=n,j=;i>(n+)/;i--,j++)
line[i]=line[j]; for(int i=;i<=(m+)/;i++){
if(i<=m-r+) col[i]=min(i,r);
else col[i]=col[i-];
}
for(int i=m,j=;i>(m+)/;i--,j++)
col[i]=col[j]; double tot=(double)(n-r+)*(m-r+),ans=0.0;
node now,next;
now.x=(n+)/,now.y=(m+)/;
now.z=(double)line[now.x]*col[now.y]/tot;
q.push(now);
vis[make_pair(now.x,now.y)]=;
while(k--){
now=q.top();
q.pop();
ans+=now.z;
for(int i=;i<;i++){
int nx=now.x+cx[i],ny=now.y+cy[i];
if(nx>&&nx<=n&&ny>&&ny<=m&&!vis[make_pair(nx,ny)]){
next.x=nx,next.y=ny,next.z=(double)line[next.x]*col[next.y]/tot;
q.push(next);
vis[make_pair(nx,ny)]=;
}
}
}
printf("%.10lf\n",ans); return ;
}
最新文章
- JAVA中的正则表达式
- Native wifi API使用
- NYOJ题目611练练
- 【JAVA、C++】LeetCode 004 Median of Two Sorted Arrays
- .NET两种常见上传下载文件方法
- 2016多校第六场题解(hdu5793&;hdu5794&;hdu5795&;hdu5800&;hdu5802)
- HW3.19
- 为 Joomla 而生的 Kunena 论坛安装手册
- 转: Linux C 动态内存分配 malloc及相关内容 .
- c++中类模版中的static数据成员的定义
- Android4.0设置界面改动总结(三)
- 阿里CEO张勇公开信:把眼光从股市回到客户身上
- 201521123030《Java程序设计》第4周学习总结
- 【OpenCV学习】Kmean均值聚类对图片进行减色处理
- linux中date命令显示
- Python_oldboy_自动化运维之路_面向对象2(十)
- 2cmd 窗口 javac 错误:编码GBK的不可映射字符
- PHP中CGI,FastCGI,PHP-CGI与PHP-FPM对比
- ArcMap概化之消除真曲线
- 关于ASP.NET 中 Global.asax 文件的后台事件处理程序