首页 > 代码库 > P2241 统计方形(数据加强版)
P2241 统计方形(数据加强版)
题目背景
1997年普及组第一题
题目描述
有一个n*m方格的棋盘,求其方格包含多少正方形、长方形
输入输出格式
输入格式:n,m因为原来数据太弱,现规定m小于等于5000,n小于等于5000(原来是100,100)
输出格式:方格包含多少正方形、长方形
输入输出样例
输入样例#1:
2 3
输出样例#1:
8 10
正方形个数
边长为1 个数n*m
边长为2 个数(n-1)*(m-1)
边长为3 个数(n-2)*(m-2)
所以 边长为min{n,m} 个数(m-min{n,m}+1)*(n-min{n,m}+1)
长方形加正方形个数
total=(1+2+3+…+n)*(1+2+3+…+m)
=((1+n)*(1+m)*n*m)/4
长方形个数
上面两式相减即可得出
所以思路就是 先算出正方形个数 然后用公式得出长方形和正方形个数总和 最后得到长方形个数
代码很短
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 int main() 7 { 8 long long n,m; 9 long long ans1=1,ans2=0;10 cin>>n>>m;11 ans1=n*m;12 long long p=(((1+n)*(1+m))*(n*m))/4;13 while(n--&&m--)14 {15 ans1+=(n*m);16 }17 cout<<ans1<<" "<<p-ans1;18 }
P2241 统计方形(数据加强版)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。