统计方形(数据加强版)#洛谷

发布时间:2024年01月17日

题目背景

1997年普及组第一题

题目描述

有一个 n × m n \times m n×m 方格的棋盘,求其方格包含多少正方形、长方形(不包含正方形)。

输入格式

一行,两个正整数 n , m n,m n,m n ≤ 5000 , m ≤ 5000 n \leq 5000,m \leq 5000 n5000,m5000)。

输出格式

一行,两个正整数,分别表示方格包含多少正方形、长方形(不包含正方形)。

样例 #1

样例输入 #1

2 3

样例输出 #1

8 10
n,m=map(int,input().split())
flag=True
x_step=1
y_step=1
value_1=0
value_2=0
while flag:
    for i in range(x_step,n+1):
        for j in range(y_step,m+1):
            xx=i-x_step
            yy=j-y_step
            if xx==yy:
                value_1+=1
            else:
                value_2+=1
    y_step+=1
    if x_step==n and y_step==m+1:
        flag=False
    if y_step>m:
        y_step-=m
        x_step+=1
print(value_1,value_2)

请添加图片描述
本来以为枚举的第一题直接暴力搞就行。但是还是TLE了,这里暴力枚举的主要思想就是,挨个点遍历,对于每个点都与自身右下方的区域进行比较,然后求一求,对应两点之间横纵坐标的距离之差。如果距离相等,那就是正方形,如果不等,那就是长方形。这里还是要用到数学的思想:

n,m=map(int,input().split())
key=min(n,m)
value1=0
value2=0
for item in range(1,n+1):
    value1+=item
for item in range(1,m+1):
    value2+=item
total_sum=value1*value2
total_zheng=0
for item in range(key):
    total_zheng+=(n-item)*(m-item)
print(total_zheng,total_sum-total_zheng)

请添加图片描述
这里是先求出给出矩阵中所有矩形的数量,求个数的公式为:(1+2+3+…+n)(1+2+3+…+m)
而求正方形的数量的公式为:
n
m+(n-1)(m-1)+(n-2)(m-2)+…
这里一直减到n和m之中的最小值

文章来源:https://blog.csdn.net/KLSZM/article/details/135643090
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。