首页 > 试题广场 >

小美的平衡矩阵

[编程题]小美的平衡矩阵

热度指数：7475 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

输入描述:

第一行输入一个正整数，代表矩阵大小。
接下来的行，每行输入一个长度为的 01 串，用来表示矩阵。

输出描述:

输出行，第行输出的完美矩形区域的数量。

示例1

输入

输出

算法知识视频讲解

Python

牛客710227026号

n = int(input())
ma = []
sum1 = []
for i in range(0,n):
    ma.append([int(x) for x in str(input())])
    sum1.append([0 for _ in range(n)])
for i in range(0,n):
    for m in range(0,n):
        if m-1>=0 and i-1>=0:
            sum1[i][m] = (sum1[i][m-1]+sum1[i-1][m]-sum1[i-1][m-1])+ma[i][m]
        elif m-1>=0 and i-1<0:
            sum1[i][m] = (sum1[i][m-1])+ma[i][m]
        elif m-1<0 and i-1>=0:
            sum1[i][m] = (sum1[i-1][m])+ma[i][m]
        else:
            sum1[i][m] = ma[i][m]
# print(sum1)

for i in range(1,n+1):
    res = 0
    t= i*i
    if i%2==1:
        print(0)
        continue
    for j in range(i-1,n):
        for k in range(i-1,n):
            a=sum1[j][k-i] if k-i>=0 else 0
            b=sum1[j-i][k] if j-i>=0 else 0
            c=sum1[j-i][k-i]  if k-i>=0 and j-i>=0 else 0
            if sum1[j][k]-a-b+c==t/2:
                res+=1
    print(res)

python倒数第三行如果直接写

if sum1[j][k]-a-b+c==i**2/2:

会超时逆天大坑

发表于 2025-04-25 17:40:55 回复(0)

Python

偶就要搞开发

二维前缀和，mark

n = int(input().strip())
input_arr = []
for _ in range(n):
    input_arr.append([int(i) for i in input().strip()])

if n == 1:
    print(0)
else:
    preffix_sum_arr = [[0] * (n + 1) for _ in range(n + 1)]
    preffix_sum_arr[1][1] = input_arr[0][0]
    for i in range(2, n + 1):
        preffix_sum_arr[1][i] = input_arr[0][i - 1] + preffix_sum_arr[1][i - 1]
        preffix_sum_arr[i][1] = input_arr[i - 1][0] + preffix_sum_arr[i - 1][1]
    for i in range(2, n + 1):
        for j in range(2, n + 1):
            preffix_sum_arr[i][j] = preffix_sum_arr[i - 1][j] + preffix_sum_arr[i][j - 1] - preffix_sum_arr[i - 1][j - 1] + input_arr[i - 1][j - 1]
    for i in range(1, n + 1):
        if i % 2 == 1:
            print(0)
            continue
        sum = 0
        for j in range(i, n + 1):
            for k in range(i, n + 1):
                if (preffix_sum_arr[j][k] - preffix_sum_arr[j - i][k] - preffix_sum_arr[j][k - i] + preffix_sum_arr[j - i][k - i] == i * i // 2):
                    sum += 1
        print(sum)

编辑于 2024-07-22 17:30:02 回复(0)

Python

侯普琳

def count_perfect_matrices(matrix, n):
    prefix_diff = [[0] * (n + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, n + 1):
            current_val = 1 if matrix[i - 1][j - 1] == '1' else -1
            prefix_diff[i][j] = (prefix_diff[i - 1][j] + prefix_diff[i][j - 1] - 
                                 prefix_diff[i - 1][j - 1] + current_val)

    results = []
    for size in range(1, n + 1):
        perfect_count = 0
        for i in range(size, n + 1):
            for j in range(size, n + 1):
                total_diff = (prefix_diff[i][j] - prefix_diff[i - size][j] -
                              prefix_diff[i][j - size] + prefix_diff[i - size][j - size])
                if total_diff == 0:
                    perfect_count += 1
        results.append(perfect_count)
    
    return results

n = int(input().strip())
matrix = [input().strip() for _ in range(n)]

result = count_perfect_matrices(matrix, n)
for count in result:
    print(count)

将0处理为-1，直接前缀和计算

编辑于 2024-04-30 17:33:17 回复(0)

提交观点

问题信息

难度：

3条回答 365收藏 829浏览

小美的平衡矩阵

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题