美团2024年春招第一场笔试【算法策略】题解

美团第一场机考

平衡矩阵

小美拿到了一个n∗nn∗n的矩阵，其中每个元素是 0 或者 1。
小美认为一个矩形区域是完美的，当且仅当该区域内 0 的数量恰好等于 1 的数量。
现在，小美希望你回答有多少个i∗ii∗i的完美矩形区域。

python较慢，注意以下几点，否则就会超时。

• 不能使用任何判断，可以通过空间换时间，比如此题在矩阵行和列前补0
• 简单操作尽量不要定义函数，降低调用开销
• 预计算所有重复的变量
• 不要计算已知的结果

import sys
N = int(sys.stdin.readline())
arr = [[0 for i in range(N+1)] for j in range(N+1)]
sum_arr = [[0 for i in range(N+1)] for j in range(N+1)]
count_arr = [0 for i in range(N)]
test_arr = [(i+1)**2/2 for i in range(N)]
for i_l, line in enumerate(sys.stdin):
    i = i_l + 1
    for j in range(1, N+1):
        arr[i][j] = int(line[j-1])
        # print(sum_u, sum_l, sum_ul)
        sum_arr[i][j] = sum_arr[i][j-1] + sum_arr[i-1][j] - sum_arr[i-1][j-1] + arr[i][j]
for k_l in range(1, N, 2):
    k = k_l + 1
    for i in range(k, N+1):
        for j in range(k, N+1):
            count = -sum_arr[i][j-k] - sum_arr[i-k][j] + sum_arr[i-k][j-k] + sum_arr[i][j]
            if count == test_arr[k_l]:
                count_arr[k_l] += 1
# print(arr)
# print(sum_arr)
for i in range(N):
    print(count_arr[i])