首页 > ACM题库 > HDU-杭电 > Hdu 1490 Homogeneous squares-数学题[解题报告] C++
2013
12-11

Hdu 1490 Homogeneous squares-数学题[解题报告] C++

Homogeneous squares

问题描述 :

Assume you have a square of size n that is divided into n×n positions just as a checkerboard. Two positions (x1,y1) and (x2,y2), where 1 ≤ x1,y1,x2,y2 ≤ n, are called “independent” if they occupy different rows and different columns, that is, x1≠x2 and y1≠y2. More generally, n positions are called independent if they are pairwise independent. It follows that there are n! different ways to choose n independent positions.

Assume further that a number is written in each position of such an n×n square. This square is called “homogeneous” if the sum of the numbers written in n independent positions is the same, no matter how the positions are chosen. Write a program to determine if a given square is homogeneous!

输入:

The input contains several test cases.
The first line of each test case contains an integer n (1 ≤ n ≤ 1000). Each of the next n lines contains n numbers, separated by exactly one space character. Each number is an integer from the interval [-1000000,1000000].
The last test case is followed by a zero.

输出:

For each test case output whether the specified square is homogeneous or not. Adhere to the format shown in the sample output.

样例输入:

2
1 2
3 4
3
1 3 4
8 6 -2
-3 4 0
0

样例输出:

homogeneous
not homogeneous


比较有意思的数学题
题意:给个N×N的棋盘,定义了一个叫做独立的点集(包含N个点,每两个点都不在同一行,同一列),棋盘上有数字,判断是全部的N!个独立点集的和都相同。
Idea:
1. 搜索?N!的空间(N=1000),不行
2. 数学规律了(我直接去搜题解了),下面是copy的:
一个矩阵“Homogeneous” <==> 其所有2*2子矩阵都是“Homogeneous”
证明如下:
首先看一个2*2矩阵a[2][2],只要a[0][0]+ a[1][1] == a[1][0] + a[0][1]也就是a[0][1] – a[0][0] == a[1][1] – a[1][0]即可。
<== 对于n*n(n>=2)的矩阵,如果所有的2*2子矩阵都为“Homogeneous ”,那么可以得到a[i-1][j]- a[i-1][j-1] == a[i][j] – a[i][j-1] == kj(n > j > 0, n > i > 0),也就是说这个差是与i无关,那么,原始矩阵a可以写成两个矩阵b,c的和。b[i][0]= a[i][0](n > i >= 0),其他元素为0; c[i][j] = sum(kj),(n > j > 0).这样c的每一行元素都一样,每次取a的一个序列(index_0,index_1…index_(n-1))时,它们的和必然相同,因为这个和衡等于sum(b[i][0])+sum(ki) (n > i >= 0)。
==>
如果一个矩阵”Homogeneous “,b的定义和上面一样,c = a – b;显然c[i][0]= 0(n > i >= 0) 那么如果c[i1][j]!= c[i2][j] (n > i1, i2 >= 0, n > j > 0, i1 != i2),那么在选择a的0,j两列的元素时候,第一次选择a[i1][0],a[i2][j],第二次选择a[i2][0],a[i1][j],其他列元素不变,显然矛盾(因为a[i1][0]== a[i2][0] == 0). 所以c[i1][j]== c[i2][j]。

―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――
其实证明画个图就好理解了,还是很有意思的数学题~

#include <cstdio>
#include <iostream>
#include <fstream>
#include <cstring>
#include <string>
#define OP(s) cout<<#s<<"="<<s<<" ";
#define PP(s) cout<<#s<<"="<<s<<endl;
using namespace std;

int main()
{
    freopen("test.txt","r",stdin);
    static int a[1010],b[1010];
    static char s[3010];
    int N;
    while (scanf("%d",&N),N)
    {
        a[0] = 0;
        for (int i = 1; i <= N; i++)
        {
            scanf("%d",&a[i]);
            b[i] = a[i] - a[i-1];
        }

        bool ans = true;
        for (int i = 2; i <= N; i++)
        {
            if (ans)
                for (int j = 1; j <= N; j++)
                {
                    scanf("%d",&a[j]);
                    if (j != 1)
                    {
                        if (a[j] - a[j-1] != b[j]) ans = false;
                    }
                }
            else {getchar();gets(s);}
        }

        if (ans) printf("homogeneous\n");
        else printf("not homogeneous\n");
    }

    return 0;
}

转自:http://blog.csdn.net/xdu_truth/article/details/8262451