1997年全国联赛复赛试题（初中组第1题）解答.
[问题描述]
   设有一个n*m的方格的棋盘（1<=m,n<=100),求该棋盘中包含有多少个正方形，多少个长方形（不包括正方形）。
   例如：当n=3,m=2时
正方形的个数有8个；即边长为1的正方形有6个；边长为2的正方形有2个；
长方形的个数有10个；即2*1的长方形有4个；1*2的长方形有3个；3*1的长方形有2个；3*2的长方形有1个。

程序要求：输入n和m，输出正方形个数与长方形的个数。
如上例题输入：3 2
        输出：8 ，10

[问题分析]
   首先对于n*m方格的棋盘中的任意的正方形而言，只要确定了左上角的位置和边长后，该正方形就完全确定了，如果两个正方形的左上角位置不同或左上角位置相同但边长不同，则这两个正方形显然不相同，因此只要穷举出最下面和最右边之外的所有格点（两条边的交叉点），算出以它们作为正方形的左上角位置时边长不同的正方形个数，然后累加起来即得到全部的正方形个数。同样地，以某一个格点为长方形的左上角位置的长方形（包括正方形）个数也可以类似地算出来，然后累加起来即得到全部的长方形个数，再去掉前面算出的正方形个数即为程序中要求的长方形个数了。

[算法分析]
   为了求出以某一个格点为正方形的左上角位置时的正方形个数，我们对所有的边进行编号，将从上到下的m+1条横向边定为第0行道第m行，将从左到右的n+1条纵向边定位第0列到第n列，这样以第i行与第j列的交叉点为正方形的左上角位置的正方形边长最大只能为m-i与n-j中的最小值，因此以第i行与第j列的交叉点为正方形的左上角位置的正方形个数为min(m-i,n-j),类似地以第i行与第j列的交叉点为正方形的左上角位置的长方形个数（包括正方形）(m-i)*(n-j)个，因为长方形的高可以取1到m-i中的任一值，长方形的宽可以取1到n-j中的任一值。


[程序清单]
program lt;
var i,j,m,n:longint;
    s:longint;
begin
  write('input n,m:');
  readln(n,m);
  s:=0;
  for i:=0 to n-1 do
  for j:=0 to m-1 do
    if n-i<m-j
     then s:=s+n-i
     else s:=s+m-j;
  write(s,' , ');
  s:=-s;
  for i:=0 to n-1 do
    for j:=0 to m-1 do s:=s+(n-i)*(m-j);
  writeln(s);
end.


希望大家支持支持下!如果有更好的方法,请立即告诉我!谢谢大家![em11]