矩形的个数
时间限制：1000 ms  |  内存限制：65535 KB
难度：1
描述
在一个3*2的矩形中，可以找到6个1*1的矩形，4个2*1的矩形3个1*2的矩形，2个2*2的矩形，2个3*1的矩形和1个3*2的矩形，总共18个矩形。

给出A，B,计算可以从中找到多少个矩形。
输入
本题有多组输入数据（<10000），你必须处理到EOF为止

输入2个整数A,B(1<=A,B<=1000)

输出
输出找到的矩形数。
样例输入
1 2
3 2
样例输出
3
18


求代码

经分析：矩阵的结果有如下规律
                                      8
                                      4
                                  6   6
                                  4   3
                             4    3   4
                             2    2   2
                        2    2    2   2
                        1    1    1   1
                       1x2  2x2  3x2 4x2
因此我猜测结果应该是(2----n*m) * 3 / 2这个公式不难推出，以下是我的代码

#include <stdio.h>
int main() {
    int n, m, i, sum;
    while(scanf("%d%d", &n, &m) == 2) {
        sum = 0;
        for(i = 2; i <= n * m; i += 2) {
            sum += i;
        }
        printf("%d\n", sum / 2 * 3);
    }
    return 0;
}

 

[ 本帖最后由 Susake 于 2013-4-5 11:42 编辑 ]

呵呵，你这公式有误。

正确的公式应该是

f(a,b) = a * (a + 1) * b * (b + 1) / 4

这是通项式，我是从它的递推式展开得到的

f(0,i) = f(i,0) = 0

f(1,i) = f(1,i-1) + i
       = i * (i + 1) / 2

f(i,j) = f(i-1,j) + f(1,j)*i
       = f(1,j) * i * (i + 1) / 2

这组递推式可以直接写成递归函数，也可以写成动规算法，由于数据范围并不大，估计用哪种方法都应该可以AC。

真是见多识广啊！记得起几天也有个也是画矩形

题目还是挺有意义的，但楼主没什么诚意，除了题目描述自己的话就三个字“求代码”。

要不是看到Susake参与进来，我懒得理这种贴子。各位要是有兴趣，不妨理解一下这个递推式的含意。

呵呵，B版，好像您多了f(0,i) = 0 这个，因为题目要求输入的a>=1, 当然这也无关大碍...昨晚1点多做的这题，确实做得有点仓促，我本来的公式应该是

for(i = 2; i <= n * m; i += 2) {
            sum += i;
        }

再*3/2  呵呵,确实因为楼主没有给出验证的地址，当时就把考虑了给出的测试结果....

[ 本帖最后由 Susake 于 2013-4-5 12:11 编辑 ]

f(0,i) = 0 是我做的扩展，是边界条件，并不影响结果。如果不习惯也可以换成f(1,1) = 1

你的式子与我的并不等价，我也无法理解其中的3是什么含意。

用 1 1、3 3这两组数据验证你的算法结果也是不正确的。

南阳理工206题就是这个题目，小广可以去试试。下面是我的AC代码

#include<stdio.h>
int main()
{
    int a, b;
    while(scanf("%d%d", &a, &b) != EOF)
        printf("%lld\n", (long long)a * (a + 1) * b * (b + 1) / 4);
    return 0;
}

嗯嗯....是啊，看了你的分析，我重新看了下我的分析，但同时出现奇数的时候就会开始错....,多谢

[ 本帖最后由 Susake 于 2013-4-5 12:28 编辑 ]

呵呵，原来是如此...矩形的个数＝行线段数×列线段数   如4x4=(1+2+3+4) * (1+2+3+4) == 100

高中数学有的，就是个排列组合题。

长选两条，宽选两条。

F(m, n) = Cm2 * Cn2 = (m+1) * m / 2 * (n+1) * n / 2 = mn * (m+1)(n+1) / 4