题解 P1548 【棋盘问题】

· · 题解

说说公式是怎么推导的吧

找规律:

正方形:

边长为1的正方形个数为n*m

边长为2的正方形个数为(n-1)*(m-1) （自己动手想想）

边长为3的正方形为个数(n-2)*(m-2)

边长为min(n,m)的正方形为个数s1=(n-min(n,m)+1)*(m-min(n,m)+1)

然后从边长为1到min（m，m）的正方形个数全部加起来；

长方形:(包括正方形，好像正方形属于长方形来着？)

长为1的长方形（包括正方形）有n个

长为2的长方形（包括正方形）有n-1个

长为n的长方形（包括正方形）有1个

长为1到n的长方形1+2+...+n个

同理 宽为1的长方形（包括正方形）有m个

宽为2的长方形（包括正方形）有m-1个

宽为m的长方形（包括正方形）有1个

宽为1-m的长方形1+2+...+m个

然后把它们乘起来，根据乘法原理，总数s2=((1+n)*(1+m)*n*m)/4;

题目要求的是“非正方形的长方形”，因此要减去s1;

#include"cstdio"
#include"iostream"
using namespace std;
int main()
{
 int n,m,s1=0,s2;
 cin>>n>>m;
 s2=((m+1)*(n+1)*m*n)/4;
 for(;m>=1&&n>=1;m--,n--)
  s1+=m*n;                       
 cout<<s1<<" "<<s2-s1;
return 0;
}