首页 > 代码库 > POJ_2941_矩阵

POJ_2941_矩阵

题目描述:

  每组数据给定一个n*n的矩阵,选定不同行不同列的n个元素,求和,若所有选法所产生的和相等,则输出 homogeneous,否则输出not homogeneous。

 

描述:

  数据挺大,爆搜肯定超时,于是有下面的递推的规律。

 

当n为3时,有这么一个矩阵,数字表示编号。

123
456
789

 

 

 

我们只需要让它的每个2阶的子矩阵符合题目条件,则它必然符合条件。

12
45

   

 

23
56

 

 

45
78

 

 

56
89

 

 

然后就可以发现一个规律,对于任意一个n阶矩阵,只要它的所有n-1阶子矩阵是homogeneous的,则它便是homogeneous的,进一步可得,只要它所有的2阶子矩阵符合两对角线相乘相等即可。

 

这样,问题便解决了。最后,我提交程序的时候却是一直超时!一个O(n^2)的程序,不至于啊= =。然后修改了无数遍,最终发现了问题所在,iostream库中的cin和cout在与stdin同步的情况下,效率比scanf和printf相差很大,最大可达十几倍,可怕!改成scanf和printf之后再提交便AC了。可见,对于含有大量数据的题目,慎用cin和cout啊= =!

 

#include<iostream>#include<cstdio>using namespace std;int a[1005][1005];int main(){    int n;    while(~scanf("%d",&n) && n)    {        int flag = 1;        for(int i = 1;i <= n;i++)        {            for(int j = 1;j <= n;j++)   scanf("%d",&a[i][j]);        }        for(int i = 1;i < n;i++)        {            for(int j = 1;j < n;j++)            {                if(a[i][j]+a[i+1][j+1] != a[i][j+1]+a[i+1][j])                {                    flag = 0;                    goto there;                }            }        }        there:        if(flag)    printf("homogeneous\n");        else        printf("not homogeneous\n");    }    return 0;}

 

POJ_2941_矩阵