SnackDown 2016

Question

给定N×M的矩阵A，其中A[1][1]为左上角的元素，A[N][M]为右下角。你需要用下面的伪代码构造另一个N×M的矩阵B。初始时B的各元素均为0。randomInt(a,b)返回一个介于a和b之间（包括a、b）的均匀随机整数，这b−a+1个整数成为返回值的概率是相等的。forx=1toN:fory=1toM:I=randomInt(1,x)J=randomInt(1,y)K=randomInt(x,N)L=randomInt(y,M)给以(I,J)为左上角，(K,L)为右下角的B的子矩阵内的每个元素加上A[x][y]；也即，对于满足I≤p≤K且J≤q≤L的所有B[p][q]，令其+=A[x][y]由此构造一个有N×M个街区的城市。编号为(i,j)的街区的高度是海平面上B[i][j]。在下了一场降雨量为X的雨之后，所有海拔高度不超过X的街区都被水淹没了。请注意，在上述构造过程中，由于随机性的存在，城市中每个街区的高度并不是确定的值，而是会根据伪代码的运行结果而有所变化。你需要回答Q个询问，每个询问中会给出一个整数k(0<k<N×M)。你需要求出最小的X，使得在下了一场降雨量为X的雨后，被水淹没的街区的数量的期望值不小于k。

Answer 1

这是一个比较复杂的问题，需要用到一些数学和算法知识来求解。以下是一个可能的解决方案：

首先，我们可以发现，在一次降雨之后，被水淹没的街区数量是一个随机变量，其期望值可以用线性期望原理来计算。具体而言，每个街区被淹没的概率等于其海拔高度不超过降雨量的概率，即P(h ≤ X)，其中h为该街区的海拔高度。因此，被水淹没的街区数量可以表示为：S = ∑(i,j) [h(i,j) ≤ X]，其中(i,j)遍历所有街区。

根据线性期望原理，期望值E[S]等于每个街区被淹没的期望值之和，即：E[S] = ∑(i,j) E[h(i,j) ≤ X]。因此，我们只需要计算每个街区被淹没的期望值，然后将它们相加即可得到期望的被淹没街区数量。

接下来，我们考虑如何计算E[h(i,j) ≤ X]。由于伪代码中使用了随机数生成器来构造城市的高度分布，因此我们必须先找到这个分布的数学性质，才能进一步计算期望。

假设A[x][y]表示第x行、第y列的街区在伪代码运行结束后的高度，我们可以观察到以下几个性质：

A[x][y]是一个介于0和N×M之间的均匀随机整数；
对于任意的i ≤ x和j ≤ y，A[i][j]都会对A[x][y]产生影响；
一个街区的海拔高度等于其所在的子矩阵中最大的A值；
对于任意的i ≤ x和j ≤ y，B[i][j]都会受到A[x][y]的影响。
基于上述性质，我们可以得到以下结论：

A[x][y]的概率密度函数为：f(z) = 1/(N×M)，其中z属于[0,N×M]；
A[x][y]与其它元素的影响是等价的，即它们对B中每个街区的影响是相同的；
B[i][j]的概率密度函数可以表示为：g(z) = (1-(z/N×M)^k)^(N×M) ，其中z属于[0,N×M]，k为随机变量S的期望值。
注意到这里的k就是题目中给定的参数。我们的目标是要找到最小的X，使得P(S ≥ k) ≥ 0.5。因此，我们可以通过二分查找来逼近X的值。具体而言，我们首先对X进行猜测，然后计算出每个街区被淹没的期望值，相加得到被淹没街区数量的期望值，再与k进行比较。如果期望值大于等于k，则说明当前的X太大，需要缩小；否则说明X太小，需要增大。重复以上步骤，直到找到满足条件的最小X。

综上所述，我们可以通过以下步骤来解决这个问题：

计算出每个街区被淹没的期望值E[h(i,j) ≤ X]，其中X是一个猜测值；
将所有期望值相加，得到被淹没街区数量的期望值E[S]；
3. 如果E[S] >= k，那么将猜测值减小一半，并重复步骤1和2；
4. 如果E[S] < k，那么将猜测值增加一半，并重复步骤1和2；
5. 重复步骤3和4，直到找到一个满足要求的X。

下面是一个可能的Python代码实现：

import random

# 构造城市
def build_city(N, M):
    A = [[random.randint(0, N*M) for j in range(M)] for i in range(N)]
    B = [[0 for j in range(M)] for i in range(N)]
    for x in range(N):
        for y in range(M):
            I = random.randint(0, x)
            J = random.randint(0, y)
            K = random.randint(x, N-1)
            L = random.randint(y, M-1)
            for i in range(I, K+1):
                for j in range(J, L+1):
                    B[i][j] += A[x][y]
    return B

# 计算期望淹没街区数量
def expected_flooded_count(city, X):
    N, M = len(city), len(city[0])
    count = 0
    for i in range(N):
        for j in range(M):
            if city[i][j] <= X:
                p = (1 - (city[i][j] / (N*M))**N*M)**N*M
                count += p
    return count

# 二分查找最小的X，使得被淹没街区数量的期望值不小于k
def find_X(city, k):
    lo, hi = 0, N*M
    while lo < hi:
        mid = (lo + hi) // 2
        count = expected_flooded_count(city, mid)
        if count >= k:
            hi = mid
        else:
            lo = mid + 1
    return lo

# 示例用法
N, M = 10, 10  # 城市大小
k = 30  # 询问参数
city = build_city(N, M)
X = find_X(city, k)
print("最小降雨量为:", X)