Codeforces Round #456 (Div. 2) 912D D. Fishes

题：

　　OvO http://codeforces.com/contest/912/problem/D

解：

　　枚举每一条鱼，每放一条鱼，必然放到最优的位置，而最优位置即使钓上的概率最大的位置，即最多的r*r矩形覆盖住的点

　　可以把这个鱼塘分为田字型4个相同的部分（可重叠），

　　取其中一个部分，显然最开始的最优位置是最靠近中心的位置，

　　维护一个优先队列，优先度为点出现在多少个r*r的矩形中，

　　每次从优先队列中取出一个点，则可以求出在其他部分上有多少不重叠的点和这个点对称，则可以同时进行计算。

　　枚举到k个点结束

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <queue>

#include <map>

#define double long double

using namespace std;

typedef long long ll;

const ll bas=1e9+44;

struct node

{

	int a,b;

	ll c;

	friend bool operator<(node x,node y)

	{

		return x.c<y.c;

	}

};

map<ll,bool>mp;

priority_queue<node> que;

int n,m,r,k,nc,mc,nw,mw;

int getNum(int a,int b)

{

	if((a==(n+1)/2 && (n&1)) && (b==(m+1)/2 && (m&1))) return 1;

	if((a==(n+1)/2 && (n&1)) || (b==(m+1)/2 && (m&1))) return 2;

	return 4;

}

double getPsi(ll c)

{

	return 1.0*c/nw/mw;

}

void solve()

{

	mp.clear();

	node tmp,now;

	double psi,ans=0;

	int num;

	while(!que.empty())

		que.pop();

	now.a=(n+1)/2,now.b=(m+1)/2,now.c=1ll*min(nc,now.a)*min(mc,now.b);

	que.push(now),mp[bas*now.a+now.b]=1;

	while(k>0)

	{

		now=que.top(),que.pop();

		num=getNum(now.a,now.b),num=min(num,k);

		psi=getPsi(now.c);

//		cout<<now.a<<' '<<now.b<<' '<<now.c<<' '<<num<<' '<<psi<<endl;

		ans+=psi*num;

		k-=num;

		tmp.a=now.a-1,tmp.b=now.b,tmp.c=1ll*min(nc,tmp.a)*min(mc,tmp.b);

		if(tmp.a>0 && tmp.b>0 && mp[bas*tmp.a+tmp.b]==0) que.push(tmp),mp[bas*tmp.a+tmp.b]=1;

		tmp.a=now.a,tmp.b=now.b-1,tmp.c=1ll*min(nc,tmp.a)*min(mc,tmp.b);

		if(tmp.a>0 && tmp.b>0 && mp[bas*tmp.a+tmp.b]==0) que.push(tmp),mp[bas*tmp.a+tmp.b]=1;

	}

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

}

int main()

{

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

	nw=nc=n-r+1,mw=mc=m-r+1;

	nc=min(r,nc),mc=min(r,mc);

	solve();

	return 0;

}

/*

10 10 1 100

*/

巴特西

Codeforces Round #456 (Div. 2) 912D D. Fishes

最新文章

热门文章