传送门：

本题是一个概率问题——求数学期望。

在一个n×m的方格中，有k个“*”。每个格子里可能有0~1个“*”。现有一个r×r的网，将网随机投入方格中，求解：网内“*”个数的数学期望的最大值。

首先考虑所求的数学期望：

枚举所有的投网方式，则对于方格的任意格子(x,y)，均可以定义其被网覆盖的次数cnt(x,y)。

若第i个“*”的位置为(x_i,y_i)，则此网覆盖第i个“*”的次数为cnt(x_i,y_i)，则所求期望为：$ans=\frac{\sum_{i=1}^{k} {cnt(x_i , y_i)}}{tot}$。其中，tot为投网的方法数，tot=(n-r+1)(m-r+1)。

这个问题的关键在于：求解一种“*”在方格内的放置方法，使得所求期望最大。

于是，可以考虑从方格中间的位置出发，通过BFS，寻找“*”的位置。于是，为BFS构造一个队列。由于本题需要求解最大值，所以每一次，均取cnt值最大的点作为当前步搜索的起点（于是这里用到优先队列std::priority_queue）。一步搜索向周围（U/D/L/R）推进一个格子。同时，应维护vis(x,y)，即点(x,y)是否被访问（根据本题的数据范围，请使用std::map）。进行k步搜索，每一步确定一个“*”的坐标。

参考程序如下：

#include 
     
      using namespace std;int n, m, r, k;priority_queue
      
       
         > q;map
        
          vis;int64_t pair2int(pair
         
           p){    return 1LL * m * p.first + p.second;}pair
          
            int2pair(int64_t p){ return make_pair(p / m, p % m);}int64_t cnt(pair
           
             p){ int x = p.first; int y = p.second; int dx = min(n, x + r) - max(r - 1, x); int dy = min(m, y + r) - max(r - 1, y); return 1LL * dx * dy;}int main(void){ scanf("%d%d%d%d", &n, &m, &r, &k); pair
            
              s = make_pair(n / 2, m / 2); q.push(make_pair(cnt(s), pair2int(s))); vis[pair2int(s)] = true; int64_t sum = 0LL; int64_t tot = 1LL * (n - r + 1) * (m - r + 1); int dx[] = {-1, 1, 0, 0}; int dy[] = { 0, 0, -1, 1}; while (k--) { sum += q.top().first; pair
             
               cur = int2pair(q.top().second); q.pop(); for (int i = 0; i < 4; i++) { int x = cur.first + dx[i]; int y = cur.second + dy[i]; if (x < 0 || x >= n || y < 0 || y >= m) continue; pair
              
                p = make_pair(x, y); if (vis[pair2int(p)]) continue; q.push(make_pair(cnt(p), pair2int(p))); vis[pair2int(p)] = true; } } double ans = 1.0 * sum / tot; printf("%.10f\n", ans); return 0;}