1490 ACM 数学

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1490

题意：

给出n*n 的矩阵，选出不同行不同列的n个元素，并求和；

如果所有选法所产生的和相等，则输出 homogeneous 否则输出not homogeneous 。

解析：通过自己在图纸上画，可以知道，实际上n*n的矩阵，符合题意的只有n!种选法。

数学规律：

要使n*n时homogeneous，必须该矩阵中的每一个2*2矩阵都是homogeneous。

证明：显然，我们能发现在n!种方法中，每一种放法都可以由另一种放法 通过对角线移动而得（及交换两坐标的X Y的值），所以移动前后的值必须相等。必须要该矩阵中的每一个2*2矩阵都是homogeneous。

及必须A1+A2==A3+A4

假设空处为a,b

那么如果该矩阵中的每一个2*2矩阵都是homogeneous

及有：

• A1+b==a+A4
• a+A2==b+A3

两式相加得：

A1+A2==A3+A4

如果

• A1+b==a+A4
• a+A2==b+A3

中有一个不成立，就不对

启发：

像这样的任意和全局型的问题，思考时可以从缩小规模的特殊情况开始考虑，如先令n=2，开始思考，从小到大；

code：

#include<cstdio>

#include<iostream>

using namespace std;

int n;

int a[][];

int t;

int main()

{

    int i,j;

    while(cin>>n&&n)

    {

        t=;

        for(i=;i<=n;++i)

            for(j=;j<=n;++j)

                cin>>a[i][j];

        for(i=;t&&i<n;i++)

            for(j=;t&&j<n;j++)

                if(a[i][j]+a[i+][j+]!=a[i][j+]+a[i+][j])

                   {

            t=;

            break;

            }

        if(t)

            cout<<"homogeneous"<<endl;

        else

            cout<<"not homogeneous"<<endl;

    }

    return ;

}